问题2396--窗内的星星(stars)

2396: 窗内的星星(stars)

时间限制: 1 Sec  内存限制: 128 MB
提交: 35  解决: 18
[提交] [状态] [讨论版] [命题人:]

题目描述

在一个天空中有很多星星(看作平面直角坐标系),已知每颗星星的坐标和亮度(都是整数)。
求用宽为W、高为H的矩形窗户(W,H为正整数)能圈住的星星的亮度总和最大是多少。(矩形边界上的星星不算)。

输入

输入包含多组测试用例。
每个用例的第一行包含3个整数:n,W,H,表示星星的数量,矩形窗口的宽和高。
然后是n行,每行有3个整数:x,y,c,表示每个星星的位置(x,y)和亮度。1≤n≤10000, 1≤W,H≤1000000, 0≤x,y<2^31,1<=c<=100, 没有两颗星星在同一点上。

输出

每个测试用例输出一个亮度总和最大值。
每个结果占一行。

样例输入 Copy

3 5 4
1 2 3
2 3 2
6 3 1
3 5 4
1 2 3
2 3 2
5 3 1

样例输出 Copy

5
6

来源/分类