-
Notifications
You must be signed in to change notification settings - Fork 9
/
10360-Rat Attack.cpp
34 lines (32 loc) · 1.02 KB
/
10360-Rat Attack.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t,d,n;
int x,y,s;
cin >> t;
while(t--){
cin >> d >> n;
vector<vector<int>> dpSum(1026,vector<int>(1026));
for(int i=0;i<n;i++){
cin >> x >> y >> s;
dpSum[x+1][y+1] += s;
}
int bestCount = 0;
pair<int,int> coord = {0,0};
for(int i=0;i<1025;i++){
for(int j=0;j<1025;j++){
dpSum[i+1][j+1] += (dpSum[i][j+1] + dpSum[i+1][j] - dpSum[i][j]);
int xoffset = i-2*d < 0 ? 0 : i-2*d;
int yoffset = j-2*d < 0 ? 0 : j-2*d;
// perform query from 2d length from current point
int res = dpSum[i+1][j+1]-dpSum[xoffset][j+1]-dpSum[i+1][yoffset]+dpSum[xoffset][yoffset];
if(res>bestCount){
bestCount = res;
coord = {i-d,j-d}; //middle point
}
}
}
printf("%d %d %d\n", coord.first,coord.second,bestCount);
}
}