链接：https://ac.nowcoder.com/acm/problem/20032 来源：牛客网

一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。 现在地图上有n(N ≤ 10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。 激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x，y轴平行。 若目标位于爆破正方形的边上，该目标将不会被摧毁。 输入描述: 输入文件的第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示 xi，yi ，vi 。 输出描述: 输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标。

思路：首先要理解位于正方形边上的目标不会被摧毁。我们可以在草稿纸上画一个边长为2的正方形的图（注意边长为二的正方形每一条边上有三个点！）此时若不略微移动正方形只能炸到一个点，所以我们把正方形向上（或下)微移，再向左（或右）微移。这时这个正方形区域就完全囊括进了四个点。

alt

注：图片来源于网络

这就是在为最后一步计算炸掉目标的总价值做好铺垫了。如上图，其中a=c-r;b=d-r;算前缀和的时候刚好就可以把上边和右边两条边上的点给剔除了（即实现了微移，符合题目要求）

现在可以开始考虑如何计算右下正方形区域内的价值和了： 类比一维数组的前缀和，这是平面中的点，我们应该考虑二维数组的前缀和。定义一个数组point[5005][5005]，为了让后面的二位前缀和计算方便（算第一个一个前缀和时不让数组计算越界），我们把坐标的x与y都加一再存入；由于我们之后计算完前缀和之后不用再用到这个记录价值的数组了，我们就没必要再开一个新的数组记录前缀和，直接在原数组上进行修改即循环point[i][j]+=point[i-1][j]+point[i][j-1]-point[i-1][j-1] (这是二维前缀和公式)。 这时，我们想想要计算哪个范围的前缀和，总不能全都算吧。难道是最远计算到我们取得坐标的最大值？对了一半，要是炸弹比我们所有目标的范围还大怎么办？我们算的前缀和范围还没炸弹要的大，那在后面计算上图右下角那个矩形就会遇到我们没算过的前缀和，结果就不对了。所以我们定义两个变量，分别计算最远的x和y坐标（记得各自已经加过1了），但是我们要让他们俩的初始值为r，后面没遇到比r大的，他俩的值就是r，这样就不会遇到没算过的前缀和了（注意没记录过的点初始值就是0）。再让c，d的初始值为r（防止减去r后越界。定义一个res记录最大的炸毁价值res=max(res,g[i][j]-g[i-r][j]-g[i][j-r]+g[i-r][j-r]);其中g[i-r][j-r]即上图中的（a,b），因为被减去了两次所以要加回来。

代码：

using namespace std;
int g[5005][5005];
int main()
{
    ios::sync_with_stdio(false);
    int n,r;cin>>n>>r;
    int mx=r;int my=r;
    int x,y,v;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y>>v;
        g[++x][++y]+=v;mx=max(x,mx);my=max(y,my);
    }
    for(int i=1;i<=mx;i++)
    {
        for(int j=1;j<=my;j++)
        {
            g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];   
        }
    }
    int res=0;
    for(int i=r;i<=mx;i++)
    {
        for(int j=r;j<=my;j++)
        {
            res=max(res,g[i][j]-g[i-r][j]-g[i][j-r]+g[i-r][j-r]);
        }
    }
    cout<<res;
    
    return 0;
}