알고리즘
백준 16507번 어두운 건 무서워 C++
영춘권의달인
2023. 6. 22. 13:28
https://www.acmicpc.net/problem/16507
16507번: 어두운 건 무서워
첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사
www.acmicpc.net
누적합
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>
using namespace std;
using int64 = long long;
int r, c, q;
vector<vector<int>> accSum;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> r >> c >> q;
accSum = vector<vector<int>>(r + 1, vector<int>(c + 1, 0));
for (int i = 1; i <= r; i++) {
int sum = 0;
for (int j = 1; j <= c; j++) {
int k;
cin >> k;
sum += k;
accSum[i][j] = sum;
}
}
for (int i = 0; i < q; i++) {
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
int cnt = (r2 - r1 + 1) * (c2 - c1 + 1);
int sum = 0;
for (int j = r1; j <= r2; j++) {
sum += accSum[j][c2] - accSum[j][c1 - 1];
}
cout << sum / cnt << "\n";
}
};