本文最后更新于 727 天前,其中的信息可能已经有所发展或是发生改变。
Original Link
思想:
- 二维前缀和。
- 注意空间,数组不要开
long long
。
- 注意给出的坐标的下标是从 0 开始的。
- 循环遍历前缀和数组,维护一个最大价值即可。
代码:
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N = 5100; |
| |
| int v[N][N]; |
| |
| int l, r; |
| |
| void solve(){ |
| int n, k; cin >> n >> k; |
| k = min(k, 5001); |
| l = r = k; |
| for(int i = 1; i <= n; i ++){ |
| int a, b, c; cin >> a >> b >> c; |
| v[a + 1][b + 1] += c; |
| l = max(a + 1, l), r = max(b + 1, r); |
| } |
| for(int i = 1; i <= l; i ++){ |
| for(int j = 1; j <= r; j ++){ |
| v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1]; |
| } |
| } |
| int res = 0; |
| for(int i = k; i <= l; i ++){ |
| for(int j = k; j <= r; j ++){ |
| res = max(res, v[i][j] - v[i - k][j] - v[i][j - k] + v[i - k][j - k]); |
| } |
| } |
| cout << res << endl; |
| } |
| |
| int main(){ |
| solve(); |
| return 0; |
| } |