URL: 洛谷

题面描述：现在地图上有N个目标，用整数$x_i$,$y_i$表示目标在地图上的位置，每个目标都有一个价值Wi。求一颗炸弹最多能炸掉地图上总价值为多少的目标。

思路：求地图的前缀和，对每个点枚举，注意坐标中有0

代码：

#include<bits/stdc++.h>
using namespace std;
int n,r,s[5005][5005],ans=0;
int main(){
    cin>>n>>r;
    for(int i=1;i<=n;i++){
        int a,b,w;
        cin>>a>>b>>w;
        s[a+1][b+1]=w;
    }
    for(int i=1;i<=5002;i++){
        for(int j=1;j<=5002;j++){
            s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    for(int i=r;i<=5002;i++){
        for(int j=r;j<=5002;j++){
            ans=max(ans,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]);
        }
    }
    cout<<ans;
    return 0;
}