激光炸弹

链接：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 。
输出描述:
输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。
示例1
输入
2 1
0 0 1
1 1 1

1
首先创建5010*5010的大数组存数据，因为规模较大，必然不可能建立多个超大数组，否则会超时。
同时，空出数组的第0行第0列，全部为0，方便后面计算减少判断。
对于从一块(1->x)(1->y)的区域轰炸价值，可以用二维的前缀和来构造
val[i][j]=val[i][j]+val[i-1][j]+val[i][j-1]-val[i-1][j-1]。
给定半径r后，对于每一个正方形，都能用
val[i][j]-val[i-r][j]-val[i][j-r]+val[i-r][j-r]表出，容易求得最大值

代码块#include<iostream>
#include <algorithm>
using namespace std;        
const int range = 5010;    
int val[range][range];
int main()
{
    int n, r,temp;                
    int x,y,value;
    while (cin >> n, cin >> r)
    {
        for (int i = 0; i < n; i++)
        {
                cin >> x >> y>> value;
                val[x+1][y+1] = value;
        }
        for (int i = 1; i < range; i++)
        {
            for (int j = 1; j < range; j++)
            {
                        val[i][j] = val[i][j]+val[i-1][j]+val[i][j-1]-val[i-1][j-1];//前缀和
            }
        }
        int maxi=0;
        for (int i = r; i < range; i++)
        {
            for (int j = r; j < range; j++)
            {
                temp = val[i][j] - val[i][j - r] - val[i - r][j] + val[i - r][j - r];
                if (temp > maxi)
                    maxi = temp;
            }
        }
        cout << maxi;

    }
    return 0;

}