16. 직사각형의 합

직사각형의 합

문제

---

N x M 의 직사각형이 주어지며, 각 칸에는 정수가 들어있다. 이제 Q개의 질문에 대하여 답을 해야 하며, 각각의 질문은 (a, b)부터 (c, d)까지의 직사각형에 들어있는 정수의 합을 묻는다. 예를 들어, 다음과 같이 5 x 5 의 직사각형이 주어질 때, (1, 2) 부터 (3, 3) 까지의 직사각형에 들어있는 정수의 합은 26 이다.

 

입력

---

첫 번째 줄에 N, M, Q가 주어진다. ( 1 ≤ N, M ≤ 1,000, 1 ≤ Q ≤ 1,000,000 ) 두 번째 줄부터 N x M 직사각형이 주어진다. 직사각형 안의 숫자 S는 -100이상 100이하이다. 그 후 Q개의 질문이 주어진다. 각각의 질문은 “a b c d” 로 이루어 져 있으며, 이는 (a, b) 부터 (c, d) 까지의 직사각형에 들어있는 정수의 합을 묻는다. (0 ≤ a ≤ c < N, 0 ≤ b ≤ d < M)  

출력

---

각 질문에 대한 답을 출력한다.

 

예제 입력

5 5 3

1 -2 3 2 8

-8 -9 3 4 5

2 4 7 8 2

1 4 3 1 4

-1 2 5 -6 3

1 2 3 4 

0 0 1 1

2 0 2 1

예제 출력

37

-18

6

 

#include <stdio.h>

int main() {

  int n,m,q;
  scanf("%d %d %d",&n,&m,&q);
  
  int arr[1010][1010];
  int t[1010][1010];
  
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      scanf("%d",&arr[i][j]);
    }
  }
  
  t[0][0] = arr[0][0];
  
  //더하는 부분
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(i==0&&j==0){
        continue;
      }
      
      if(i==0){
        t[i][j] = t[i][j-1] + arr[i][j];
      }
      else if(j==0){
        t[i][j] = t[i-1][j] + arr[i][j];
      }
      else{
        t[i][j] = t[i][j-1] + t[i-1][j] - t[i-1][j-1] + arr[i][j];
      }
    }
  }
  
  int a,b,c,d;
  int sum = 0;
    
  //값구하는 부분
  for(int i=0;i<q;i++){
    
    scanf("%d %d %d %d",&a,&b,&c,&d);
    
    sum = t[c][d] - t[c][b-1] - t[a-1][d] + t[a-1][b-1];
 
    printf("%d\n",sum);
  }
  return 0;
}