题目传送门
题目思路
用到二维前缀和，表示S(i,j)就是i,j上面的这个矩形的和。
因此可以这样求：
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];同时也可以这样切出一个边长为m的正方形的和。
坑：需要考虑m大于整个部分的情况。
坑：坐标还可能重合。。。
巨坑：妈的，0,0的坐标出问题了。。。以后要从1开始打了，
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
int a[5005][5005];
int s[5005][5005];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
int x, y, v;
cin >> x >> y >> v;
a[x + 1][y + 1] += v;
}
for (int i = 1; i < 5002; i++)
for (int j = 1; j < 5002; j++)
s[i][j] = s[i - 1 >= 0 ? i - 1 : 0][j] + s[i][j - 1 >= 0 ? j - 1 : 0] - s[i - 1 >= 0 ? i - 1 : 0][j - 1 >= 0 ? j - 1 : 0] + a[i][j];
int ans = 0;
for (int i = m; i < 5002; i++)
for (int j = m; j < 5002; j++)
ans = max(ans, s[i][j] - s[i - m][j] - s[i][j - m] + s[i - m][j - m]);
cout << ans << endl;
return 0;
}