¡Hermosa cuadrícula!#12209

¡Hermosa cuadrícula! (Editorial)

Autor del problema:	Hasan Saleh (MathModel)
Preparado por:	Hasan Saleh (MathModel)
Editado por:	Hasan Saleh (MathModel)

Solución

Calcula la suma de cada fila y columna en $O (n^{2})$ \mathcal{O}(n^2) y mapea con un $map$ y luego para cada diagonal verifica todas las sumas de subarreglos de cada diagonal y verifica si ya está calculado en $map$ , esto se puede hacer con suma prefija o simplemente actualizando las sumas y almacenándolas mientras se calcula.

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("SÍ")
                    return
            except:
                pass
            try:
                if(mp[d2[j]-d2[i]+a[i][n-i-1]]):
                    print("SÍ")
                    return
            except:
                pass
    print("NO")
for _ in range(int(input())):
    solve()

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