题目描述

一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。
现在地图上有n(N ≤ 10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x，y轴平行。
若目标位于爆破正方形的边上，该目标将不会被摧毁。 

输入描述: 

输入文件的第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示 xi，yi ，vi 。

输出描述: 

输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。
示例1

输入 

2 1
0 0 1
1 1 1

输出

1

思路

二维前缀和，找(r-1) * (r-1)区域的最大值，暴力搜索即可

代码 


//[HNOI2003]激光炸弹(二维前缀和)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5010;

int n , r;
int x , y , v;
int s[N][N];

int main()
{
	scanf("%d %d" , &n , &r);
	
	while(n--)
	{
		scanf("%d %d %d" , &x , &y , &v);
		s[x + 1][y + 1] = max(s[x + 1][y + 1] , v); 
	}
	
	for(int i = 1 ; i < N ; i++)
	{
		for(int j = 1 ; j < N ; j++)
			s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
	}
	
	int ans = 0;
	for(int i = r ; i < N ; i++)
	{
		for(int j = r ; j < N ; j++)
			ans = max(ans , s[i][j] - s[i - r][j] 
			- s[i][j - r] + s[i - r][j - r]);
	}
	
	printf("%d\n" , ans);
	return 0;	
}