AcWing 99. 激光炸弹
原题链接
简单
作者:
P__sR
,
2021-12-06 10:27:06
,
所有人可见
,
阅读 252
#include <algorithm>
using namespace std;
const int N = 5010;
int s[N][N];
int main()
{
int n, r;
scanf("%d%d", &n, &r);
r = min(r, 5001);
for (int i = 0; i < n; i++)
{
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
x++, y++;
s[x][y] += w;
}
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];
}
int res = 0;
for (int i = r; i <= 5001; i++)
for (int j = r; j <= 5001; j++)
{
res = max(res, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);
}
printf("%d\n", res);
return 0;
}