AcWing 99. 激光炸弹
原题链接
简单
作者:
TonyBryant
,
2024-02-20 22:50:21
,
所有人可见
,
阅读 26
#include <bits/stdc++.h>
using namespace std;
const int N = 5009;
int mp[N][N];//二位前缀和数组
int n, r, ans = 0;
int main()
{
cin >> n >> r;
r = min(r, 5001);
for(int i = 1, x, y, w;i <= n;++ i)
{
cin >> x >> y >> w;
mp[x + 1][y + 1] += w;//此时 mp 数组的含义就是初始地图
}
for(int i = 1;i <= 5001;++ i)//坐标最多 5000
for(int j = 1;j <= 5001;++ j)//按顺序枚举坐标
mp[i][j] = mp[i - 1][j] + mp[i][j - 1] - mp[i - 1][j - 1] + mp[i][j];
//注意顺序
for(int i = r;i <= 5001;++ i)
for(int j = r;j <= 5001;++ j)//状态计算
ans = max(ans, mp[i][j] - mp[i - r][j] - mp[i][j - r] + mp[i - r][j - r]);
cout << ans << endl;
return 0;
}