CF1517G Starry Night Camping

在鲤鱼山脚下，将精心布置 $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. 对于所有 $j \in \{1, 2, 3\}$，都有 $|x'_j-x| \leq 1$ 且 $|y'_j - y| \leq 1$； 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$ 个帐篷的坐标和权值。任意两个帐篷不会位于同一个点。

输出一个整数，表示未被移除帐篷的最大权值和。

下面是第二个样例的示意图。黑色三角形表示重要帐篷。该示例还展示了所有 $8$ 种被禁止的模式。  由 ChatGPT 4.1 翻译