[백준 11660번] [구간 합] 구간 합 구하기 5

Approach

s.p.s dp[x][y] : $\sum \limits_x \sum \limits_y v(x_i, y_i)$ for $1 \le x_i \le x , 1 \le y_i \le y$

(It is defined to be 0 if x or y are less than 1)

Therefore dp[x][y] = dp[x - 1][y] + dp[x][y - 1] - dp[x - 1][y - 1].

 

So, Summation (x1, y1) to (x2, y2) equal to dp[x2, y2] - dp[x2, y1 - 1] - dp[x1 - 1, y2] + dp[x1 - 1, y1 - 1]

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int dp[1025][1025];

int dp_value(int x, int y){
    if(x < 1 || y < 1) return 0;
    else return dp[x][y];
}
int sum(int x, int y){
    return dp_value(x, y - 1) + dp_value(x - 1, y) - dp_value(x - 1,y - 1);
}

int main(void){
    fastio;
    memset(dp, sizeof(dp), 0);
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int v;
            cin >> v;
            dp[i][j] = sum(i, j) + v;   
        }
    }

    for(int i = 0; i < m; i++){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp_value(x2, y2) - dp_value(x1 - 1, y2) - dp_value(x2, y1 - 1) + dp_value(x1 - 1, y1 - 1) << "\n";
    }
    return 0;
}