bzoj1218【HNOI2003】激光炸彈

bzoj1218【HNOI2003】激光炸彈

Description

一種新型的激光炸彈，可以摧毀一個邊長為R的正方形內的所有的目標。現在地圖上有n(N<=10000)個目標，用整數Xi,Yi(其值在[0,5000])表示目標在地圖上的位置，每個目標都有一個價值。激光炸彈的投放是通過衛星定位的，但其有一個缺點，就是其爆破范圍，即那個邊長為R的正方形的邊必須和x，y軸平行。若目標位於爆破正方形的邊上，該目標將不會被摧毀。 0

Input

輸入文件的第一行為正整數n和正整數R，接下來的n行每行有3個正整數，分別表示

Output

輸出文件僅有一個正整數，表示一顆炸彈最多能炸掉地圖上總價值為多少的目標（結果不會超過32767）。

Sample Input

Sample Output

HINT

Source

Dp

這是一道大水題，暴力枚舉+二維前綴和。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 5005
using namespace std;
int n,r,x,y,z,ans=0;
int s[maxn][maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	n=read();r=read();
	F(i,1,n)
	{
		x=read()+1;y=read()+1;z=read();
		s[x][y]+=z;
	}
	F(i,1,5001) F(j,1,5001) s[i][j]+=s[i][j-1];
	F(i,1,5001) F(j,1,5001) s[i][j]+=s[i-1][j];
	F(i,r,5001) F(j,r,5001)
	{
		int tmp=s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r];
		ans=max(ans,tmp);
	}
	printf("%d\n",ans);
}