Beautiful Grid! (Editorial)

Beautiful Grid!#12209

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

Compute the sum of each grid and column in $O (n^{2})$ \mathcal{O}(n^2) and map them with a $map$ and then for each diagonal check all subarray sum of each diagonal and check if it's already calculated in $map$ this can be done with prefix sum or just updating sums and storing them while calculating.

def solve():
    n=int(input())
    a = [[0]*n for _ in range(n)]
    mp={}
    for i in range(n):
        a[i]=list(map(int,input().split()))
    for i in range(n):
        sum,sum2=0,0
        for j in range(n):
            sum+=a[i][j]
            sum2+=a[j][i]
        mp[sum]=1
        mp[sum2]=1
    d1,d2=[],[]
    sd1,sd2=0,0
    for i in range(n):
        sd1+=a[i][i]
        sd2+=a[i][n-i-1]
        d1+=[sd1]
        d2+=[sd2]
    for i in range(n):
        for j in range(i,n):
            try:
                if(mp[d1[j]-d1[i]+a[i][i]]):
                    print("YES")
                    return
            except:
                pass
            try:
                if(mp[d2[j]-d2[i]+a[i][n-i-1]]):
                    print("YES")
                    return
            except:
                pass
    print("NO")
for _ in range(int(input())):
    solve()

Complexity $O (n^{2})$ \mathcal{O}(n^2)