AcWing 99. 激光炸弹
原题链接
简单
作者:
zscale
,
2023-02-07 12:52:35
,
所有人可见
,
阅读 127
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5010;
int mp[N][N];
int row, col;
int main()
{
int n,r;
cin>>n>>r;
r = min(r,5001); //为什么一定是5001,x,y最大是5001,0没有使用,地图是从1开始算的
/* error with 5010
2 1000000000
0 0 1
1 1 1
*/
row = col = 5001; //最大是5001 这里需要有一个初始化,不然后面循环可能从0开始
for(int i=0;i<n;i++)
{
int x,y,w;
cin>>x>>y>>w;
x++,y++;
row = max(row,x);
col = max(col,y);
mp[x][y] += w;
}
//求前缀和
for(int i=1;i<=row;i++)
{
for(int j=1;j<=col;j++)
{
mp[i][j] = mp[i-1][j] + mp[i][j-1]-mp[i-1][j-1]+mp[i][j];
}
}
//求子矩阵的和
int res = 0;
for(int i=r;i<=row;i++)
{
for(int j=r;j<=col;j++)
{
res = max( mp[i][j]-mp[i-r][j]-mp[i][j-r]+mp[i-r][j-r],res );
}
}
cout<<res;
return 0;
}