99 激光炸弹
一道二位前缀和问题
二位前缀和+暴力代码如下
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Inf 0x3f3f3f
#define ll long long
using namespace std;
int n,r;
int ta,tb;
int x,y,w;
int sum[5005][5005];
int ans;
int main()
{
scanf("%d%d",&n,&r);
ta=r;
tb=r;
for(int i=0;i<n;i++)
{
scanf("%d%d%d",&x,&y,&w);
x++;
y++;
sum[x][y]+=w;
ta=max(ta,x);
tb=max(tb,y);
}
for(int i=1;i<=ta;i++)
for(int j=1;j<=tb;j++)
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
for(int i=r;i<=ta;i++)
for(int j=r;j<=tb;j++)
ans=max(ans,sum[i][j]-sum[i-r][j]-sum[i][j-r]+sum[i-r][j-r]);
printf("%d\n",ans);
return 0;
}