题目背景

请使用 C++17 或 C++20 提交本题

你需要在程序开头加入如下代码：

#include <vector>

int max_level (std::vector<int> X, std::vector<int> Y, std::vector<int> D, std::vector<int> W);
  

题目译自 2022년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T2「 보안 시스템」

题目描述

KOI 国的机密设施可以表示为一个在坐标平面上的正方形，其左下角顶点为 $(0,0)$，右上角顶点为 $(N+1, N+1)$，边与坐标轴平行。正方形的每条边代表机密设施的外壁。

在机密设施内有 $N$ 个激光传感器，每个传感器从 $0$ 到 $N-1$ 编号。我们需要设计一个安全系统，通过这些激光传感器来检测入侵者。

每个激光传感器可以表示为坐标平面上的一个点。当激光传感器启动时，它会向上（$+y$ 轴方向）、向右（$+x$ 轴方向）、向下（$-y$ 轴方向）或向左（$-x$ 轴方向）发射激光。激光会一直延伸到碰到墙壁为止，因此激光的路径可以表示为从传感器位置到墙壁上的某个点的线段。

激光发射的方向用 $1$ 到 $4$ 表示。$1$ 表示向上，$2$ 表示向右，$3$ 表示向下，$4$ 表示向左。下图依次展示了激光传感器向 $1$、$2$、$3$、$4$ 方向发射激光的示例。黑点表示激光传感器，红线表示激光。

第 $i (0 \leq i \leq N-1)$ 个激光传感器位于 $(X[i], Y[i])$，启动时会向 $D[i]$ 方向发射激光。不同的激光传感器位于不同的位置。$X[i]$ 和 $Y[i]$ 是 $1$ 到 $N$ 之间的整数。

你可以自由决定每个激光传感器是否启动。但如果不同的激光传感器发射的激光相遇，会导致检测错误，因此激光不能相交，包括端点。下图展示了激光相交的示例，激光可以在一个点相交，也可以在一条线段上相交。

第 $i (0 \leq i \leq N-1)$ 个激光传感器的重要性为 $W[i]$，表示启动该传感器的贡献值。整个安全系统的安全级别是启动的激光传感器的贡献值之和。

请编写一个函数，在确保激光不相交的前提下，决定哪些激光传感器启动，使得安全级别最大。

你需要实现以下函数：

int max_level(vector<int> X, vector<int> Y, vector<int> D, vector<int> W);

• X, Y, D, W：长度为 $N$ 的整数数组。对于每个 $i (0 \leq i \leq N-1)$，第 $i$ 个激光传感器的坐标为 $(X[i], Y[i])$，启动时向 $D[i]$ 方向发射激光，重要性为 $W[i]$。
• 该函数返回在确保激光不相交的前提下，最大可能的安全级别。

注意，提交的代码中不应包含任何输入输出操作。

输入格式

示例评测程序的输入格式如下：

• 第 $1$ 行：$N$
• 第 $2+i (0 \leq i \leq N-1)$ 行：$X[i]\,Y[i]\,D[i]\,W[i]$

输出格式

示例评测程序的输出格式如下：

第 $1$ 行：max_level 函数返回的值。

4
1 1 1 1
2 2 1 1
3 3 4 1
4 4 4 1

2

10
5 10 1 127
7 9 1 130
5 6 3 22
8 10 2 60
7 6 3 43
9 6 2 23
8 6 3 9
5 8 2 27
6 7 2 175
8 9 2 57

673

10
4 3 2 90
1 3 4 122
9 8 2 105
5 10 2 106
9 1 2 125
8 1 4 72
4 8 4 142
9 6 4 78
8 9 2 68
4 10 4 99

1007

10
8 8 1 38
10 6 3 11
1 4 1 150
3 7 2 91
5 3 4 30
8 9 2 147
5 1 4 164
3 4 2 6
4 1 3 104
5 4 1 19

593

提示

样例解释 #1

考虑 $N=4, X=[1,2,3,4], Y=[1,2,3,4], D=[1,1,4,4], W=[1,1,1,1]$ 的情况。评测程序将调用如下函数：

max_level({1, 2, 3, 4}, {1, 2, 3, 4}, {1, 1, 4, 4}, {1, 1, 1, 1});

下图展示了机密设施、传感器和传感器发射的激光。启动 $0$ 号和 $1$ 号传感器，或启动 $2$ 号和 $3$ 号传感器，激光不会相交，安全级别为 $2$。没有比这更高的安全级别的方案。

因此，函数应返回 2。

数据范围

对于所有输入数据，满足：

• $1 \leq N \leq 1500$
• 对于所有 $i (0 \leq i \leq N-1)$，$1 \leq X[i], Y[i] \leq N$
• $D[i] \in \{1,2,3,4\}$ (对于所有 $0 \leq i \leq N-1$)
• 对于所有 $i (0 \leq i \leq N-1)$，$1 \leq W[i] \leq 10^5$
• 每个传感器的位置都不同。

详细子任务附加限制及分值如下表所示。

Subtask	分值	约束
$1$	$5$	$N \leq 18$
$2$	$8$	$N \leq 36$
$3$	$21$	$N \leq 100$
$4$	$15$	$N \leq 500$
$5$	$11$	对于所有 $i (0 \leq i \leq N-1)$，$D[i] \in \{1,2,3\}$
$6$	$17$	对于所有 $i,j (0 \leq i < j \leq N-1)$，$X[i] \neq X[j]$ 且 $Y[i] \neq Y[j]$
$7$	$23$	无附加限制