前缀和与差分1:激光炸弹
作者:
总打瞌睡的天天啊
,
2024-08-04 14:02:08
,
所有人可见
,
阅读 3
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5010;
int s[N][N];
int main()
{
int n,m;
cin>>n>>m;
m=min(m,5001);
for (int i = 0; i < n; i++) {
int x, y, w;
cin >> x >> y >> w;
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=m;i<=5001;i++)
for(int j=m;j<=5001;j++)
res=max(res,s[i][j]-s[i-m][j]-s[i][j-m]+s[i-m][j-m]);
cout<<res<<endl;
return 0;
}