AcWing 99. 激光炸弹
原题链接
简单
作者:
因是因非
,
2022-02-23 20:05:18
,
所有人可见
,
阅读 125
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int s[N][N];
int main()
{
int n, r;
cin >> n >> r;
for(int i = 1; i <= n; i ++ )
{
int x, y, v;
scanf("%d%d%d", &x, &y, &v);
s[x + 1][y + 1] += v;
}
for(int i = 1; i <= 5001; i ++ )
for(int j = 1; j <= 5001; j ++ )
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];
int ans = 0;
for(int x1 = 1; x1 <= 5001; x1 ++ )
for(int y1 = 1; y1 <= 5001; y1 ++ )
{
int x2 = min(5001, x1 + r - 1);
int y2 = min(5001, y1 + r - 1);
ans = max(ans, s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}
cout << ans;
}