蓝桥杯备考----＞激光炸弹（二维前缀和）
本题我们可以构造二维矩阵，然后根据题意，枚举所有边长为m的正方形，找到消灭价值最多的炸弹
#include <iostream>
using namespace std;
const int N = 1e4;
int a[N][N];
int n,m;
int f[N][N];
int main()
{
cin >> n >> m;
while(n--)
{
int x,y,value;cin >> x >> y >> value;
//为了避免越界，我们必须让矩阵整体向右下移动一步
x++,y++;
a[x][y] += value;
}
n = 5010;
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=n;j++)
{
f[i][j] = f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
}
}
int ret = 0;
m = min(m,n);
//枚举边长为m的正方形
for(int x2 = m;x2<=n;x2++)
{
for(int y2=m;y2<=n;y2++)
{
int x1 = x2-m+1;
int y1 = y2-m+1;
ret = max(ret,f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]+f[x1-1][y1-1]);
}
}
cout << ret << endl;
return 0;
}