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

구간 합 구하기
분명히 무작정 해결하면 시간 초과가 날 것을 알고 있었지만 DP를 이용해 해결하지못해 결국 시간초과 제출이라도 하였고 정답을 찾아보았다. 풀이

#include <iostream>
#include <deque>
#include <sstream>
#include <vector>
#include <string>

int ary[1027][1027];
int dp[1027][1027];
using namespace std;

int n, m, result;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> ary[i][j];
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + ary[i][j];
		}
	}

	while (m--) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		
		result = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];

		cout << result << "\n";
		result = 0;
	}

	return 0;
}