记录编号	558477	评测结果	AAAAAAAAAA
题目名称	[HNOI 2003]激光炸弹	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	1.708 s
提交时间	2021-01-03 11:23:29	内存使用	78.03 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 5005;
int s[maxn][maxn],n,r,nx,ny;
int sum(int x1,int y1,int x2,int y2) {
	int ans = s[x2][y2];
	if(x1 >= 0) {
		ans -= s[x1][y2];
	}                                
	if(y1 >= 0) {        
		ans -= s[x2][y1];                                                     
	}                 
	if(x1 >= 0&&y1 >= 0) {
		ans += s[x1][y1];
	}
	return ans;
//	return s[x2][y2] - s[x2][y1] - s[x1][y2] + s[x1][y1];
}                               
int main() {
	freopen("boom.in","r",stdin);
	freopen("boom.out","w",stdout);
	scanf("%d%d",&n,&r);
	nx = r;
	ny = r;
	for(int i = 1;i <= n;++ i) {
		int w,x,y;
		scanf("%d%d%d",&x,&y,&w);
		nx = max(x , nx);
		ny = max(y , ny);
		s[x][y] += w;
	}
	for(int i = 0;i <= nx;++ i) {
		for(int j = 0;j <= ny;++ j) {
			if(i > 0) {
				s[i][j] += s[i - 1][j];
			}
 			if(j > 0) {
 				s[i][j] += s[i][j - 1];
 			}
 			if(i > 0&&j > 0) {
 				s[i][j] -= s[i - 1][j - 1];
 			}
		}
	}
//	for(int i = 0;i <= nx;++ i) {
//		for(int j = 0;j <= ny;++ j) {
//			printf("%d ",s[i][j]);
//		}
//		putchar('\n');
//	}
	int ans = 0;
	for(int i = r - 1;i <= nx;++ i) {
		for(int j = r - 1;j <= ny;++ j) {
			ans = max(ans , sum(i - r,j - r,i,j));
		}
	}                                                        
	printf("%d",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}