글 읽기 - [python3] 시간초과 질문드립니다.

coinchuu 5년 전 1

O(n^2+m) 아닌가요...

n,m=map(int,input().split())
n+=1
a=[0]*n
d=[0]*n
for i in range(1,n):
    a[i]=[0]+list(map(int,input().split()))
    d[i]=[0]*n
a[0]=d[0]=[0]*n
for i in range(1,n):
    for j in range(1,n):
        d[i][j]=a[i][j]+d[i-1][j]+d[i][j-1]-d[i-1][j-1]
for t in range(m):
    q,w,e,r=map(int,input().split())
    print(d[e][r]-d[e][w-1]-d[q-1][r]+d[q-1][w-1])