problem-11660

과정
1. dp 2차원 테이블을 만든다.
2. dp[a][b]에서 a는 board의 행, b는 board의 열, 그리고 dp[a][b]의 값은 board[a][0]~board[a][b]까지의 합이다.
3. dp 값을 할당한 후, a,b,c,d 인풋을 받을 때마다 a부터 c까지 ans+=dp[][d]-dp[][b-1]을 통해 b부터 d까지의 합을 구한다.

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
board=[]
dp=[[0 for i in range(n+1)] for j in range(n+1)]

for i in range(n):
    board.append(list(map(int,input().split())))
    for k in range(len(board[i])):
        dp[i+1][k+1] = dp[i+1][k]+board[i][k]


result=[]
for i in range(m):
    a,b,c,d=map(int,input().split())
    ans=0

    for j in range(a,c+1):
        ans+=dp[j][d]-dp[j][b-1]

    result.append(ans)
    
for r in result:
    print(r)

time:40분