python/TangDou/AcWing_TiGao/T6/QianZuiHeChaFen/99.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 5010, M = 5001;
// 前缀和数组
int s[N][N];

int main() {
    // n:点的数量，r:边长
    int n, r;
    cin >> n >> r;

    // 这里本题数据有些坑，r有时输入会比我们整个矩阵大，所以这里设置输入的r过大，就直接取M
    r = min(r, M); // r太大，对于我们来说没有意义，因为它>5001时，就把所有位置全部摧毁掉~

    for (int i = 1; i <= n; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        // 因为每题的(x,y)是默认下标从0开始，与前缀和的习惯不太相符，所以，这里直接将原坐标x+1,y+1，映射到下标从(1,1)开始
        x++, y++;     // 0≤Xi,Yi≤5000
        s[x][y] += w; // 不同目标可能在同一位置,s数组同时也充当了a数组
    }

    // 二维前缀和公式
    for (int i = 1; i <= M; i++)
        for (int j = 1; j <= M; j++)
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    // 枚举所有边长为r的正方形(枚举右下角)，取最大值就OK了
    int res = 0;
    for (int i = r; i <= M; i++)
        for (int j = r; j <= M; j++) // 二维前缀和应用
            res = max(res, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);

    // 输出结果
    cout << res << endl;
    return 0;
}