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

기말끝나고 개오랜만에 백준을...

 

구간합은 dp로 가능함. 따로 dp배열 만들어놓고 기존 배열에 들어올때마다 해당 칸 dp도 최신화 시켜주면 됨

 

N이 최대 1024니까 dp까지 해주면 1024*1024

구해야하는 횟수 M 최대가 100,000이니까

 

백만 몇번 == 1초안에 충분히 돌릴 수 있다.

 

---

 

#include <iostream>
#define SIZE 1025

using namespace std;

int arr[SIZE][SIZE], dp[SIZE][SIZE];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int N, M; cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) {
			cin >> arr[i][k];
			dp[i][k] = dp[i - 1][k] + dp[i][k - 1] - dp[i - 1][k - 1] + arr[i][k];
		}
	}

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