Гарна решітка!#12209

Гарна решітка! (Розбір)

Автор проблеми:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редаговано:	Хасан Салех (MathModel)

Рішення

Обчисліть суму кожного рядка і стовпця за $O (n^{2})$ \mathcal{O}(n^2) і зіставте їх з $map$ , а потім для кожної діагоналі перевірте всі суми підмасивів кожної діагоналі і перевірте, чи вже обчислено в $map$ . Це можна зробити за допомогою префіксної суми або просто оновлюючи суми та зберігаючи їх під час обчислення.

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()

Складність $O (n^{2})$ \mathcal{O}(n^2)