acwing99. 激光炸弹(蓝桥杯)

题目：99. 激光炸弹

思路：用二维前缀和

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N=1e4+10;
int n,r;
int sum[5050][5050];
int main(){
    scanf("%d%d",&n,&r);
    int x,y,w;
    for(int i=0;i<n;i++){
        scanf("%d%d%d",&x,&y,&w);
        sum[x+1][y+1]+=w;

    }
    for(int i=1;i<=5001;i++){
        for(int j=1;j<=5001;j++){
            sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    }
    int R=min(5001,r);
    int res=0;
    for(int i=R;i<=5001;i++){
        for(int j=R;j<=5001;j++){
            int t=sum[i][j]-sum[i-R][j]-sum[i][j-R]+sum[i-R][j-R];
            res=max(res,t);
        }
    }
    printf("%lld",res);
    return 0;
}