题目描述

算法1

(二维前缀和) $O(n^2)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, r,t,m;
int s[5010][5010];
int main()
{

    cin >> t >> r;
    r = min(5001,r);
    m = n = r;
    int a, b, c;
    for (int i = 1; i <= t; i++) {
        cin >> a >> b >> c;
        a++;
        b++;
        n = max(n, a);
        m = max(m, b);
        s[a][b] +=c;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i-1][j-1];
        }
    }
    int res = 0;
    for (int i = r; i <= n; 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;
    return 0;
}