（前缀和）激光炸弹

题目链接

根据题意画出格点，观察到到当正方形恰好和图形的边框重合时，设小正方形的边长为R，

那么此时圈中的点组成的方形的长度为（R-1)*(R-1)，也就是(R - 1）* ( R - 1)个点，而假

如将大的方形稍微挪动一点到第二张图片所示位置，那么就能圈中R * R个点。

还有需要注意的一点就是由于题目给的正方形长度为1e9，而点的最大值为5000，所以需要

求出点的最大值并将其作为新的正方形的长和宽。

另外，本体主要是考察二维前缀和算法，对于二位前缀和，

假如有二维数组 a 以及二维前缀和数组 sum， 那么 sum[ i ] [ j ] = sum[ i - 1][ j ] + sum[ i ] [ j - 1] + a [ i ] [ j ] - sum[ i  - 1] [ j - 1]

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int n, cnt, r, m;
int sum[5010][5010];
int main(){
    cin >> cnt >> r;
    int x, y, v;
    r = min(5001, r);
    n = m = r;
    for (int i = 1; i <= cnt; i ++) {
        scanf("%d %d %d", &x, &y, &v);
        x++, y++;
        n = max(n, x), m = max(m, y);
        sum[x][y] += v;
    }
    for (int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
             sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
    int maxn = -1;
    for(int i = r; i <= n; i ++){
        for(int j = r; j <= m; j ++){
            maxn = max(sum[i][j] - sum[i - r][j] - sum[i][j - r] + sum[i - r][j - r], maxn);
        }
    }
    cout << maxn << endl;
    return 0;
}