← 返回题目列表

Codeforces · 1517/G

G. 星夜露营

中文机器翻译题面 查看原题

鲤鱼山脚下,会精心布置$$$n$$$帐篷,为愿意体验亲近自然的愉悦、夜晚的宁静、璀璨星空的人们提供住宿。

第 $$$i$$$ 帐篷位于 $$$(x_i, y_i)$$$ 点,重量为 $$$w_i$$$。当且仅当 $$$x_i$$$ 和 $$$y_i$$$ 都是偶数时,帐篷才重要。您需要移除一些帐篷,以便对于每个剩余的重要帐篷 $$$(x, y)$$$,不存在 $$$3$$$ 其他帐篷 $$$(x'_1, y'_1)$$$、$$$(x'_2, y'_2)$$$ 和 $$$(x'_3, y'_3)$$$,这样两个条件都成立:

1. $$$|x'_j-x|, |y'_j - y|\leq 1$$$ 对于 \{1, 2, 3\}$$$ 中的所有 $$$j,并且
2. 这四个帐篷形成一个平行四边形(或矩形),其一条边平行于 $$$x$$$ 轴。

请最大化未拆除的帐篷的重量总和。打印最大值。

输入

第一行包含一个整数$$$n$$$ ($$$1\leq n\leq 1\,000$$$),代表帐篷的数量。

接下来的 $$$n$$$ 行包含三个整数 $$$x_i$$$、$$$y_i$$$ 和 $$$w_i$$$ ($$$-10^9\leq x_i,y_i \leq 10^9$$$, $$$1\leq w_i\leq 10^9$$$),表示第 $$$i$$$ 个帐篷及其重量。没有两个帐篷位于同一地点。

输出

单个整数 — 剩余帐篷重量的最大总和。

示例

输入 #1

5
0 0 4
0 1 5
1 0 3
1 1 1
-1 1 2

输出 #1

12

输入 #2

32
2 2 1
2 3 1
3 2 1
3 3 1
2 6 1
2 5 1
3 6 1
3 5 1
2 8 1
2 9 1
1 8 1
1 9 1
2 12 1
2 11 1
1 12 1
1 11 1
6 2 1
7 2 1
6 3 1
5 3 1
6 6 1
7 6 1
5 5 1
6 5 1
6 8 1
5 8 1
6 9 1
7 9 1
6 12 1
5 12 1
6 11 1
7 11 1

输出 #2

24

注意

这是第二个示例的说明。黑色三角形表示重要的帐篷。此示例还指示所有 $$$8$$$ 禁止的模式。