Maximizing Security Level with Non-intersecting Laser Beams

In the secret facility of KOI country, the area is represented as a square in the coordinate plane with the bottom-left corner at \( (0, 0) \) and the top-right corner at \( (N+1, N+1) \). The walls of the facility are the four sides of the square.

Inside the facility, there are \(N\) laser sensors (numbered \(0\) to \(N-1\)) placed at \( (X[i], Y[i]) \) with \(1 \le X[i], Y[i] \le N\). When activated, each sensor emits a laser beam in one of four directions: up (\(1\)), right (\(2\)), down (\(3\)), or left (\(4\)). The beam extends from the sensor to the corresponding wall. Thus, for example, a sensor with coordinates \( (x, y) \) emitting upward (\(1\)) creates a vertical segment from \(y\) to \(N+1\) at \(x\), and a sensor emitting rightward (\(2\)) creates a horizontal segment from \(x\) to \(N+1\) at \(y\).

You can freely choose which sensors to activate. However, if two activated sensors have beams that intersect (even at an endpoint), a detection error occurs. In particular:

• Vertical sensors: A sensor emitting upward (\(1\)) produces a beam covering \( [Y, N+1] \); one emitting downward (\(3\)) covers \( [0, Y] \). Two vertical sensors placed on the same \(x\)-coordinate conflict if their beam segments overlap. Specifically, if both sensors have the same direction (both up or both down), they always conflict. If one sensor is upward and the other downward, they conflict if the upward sensor's \(y\)-coordinate is no higher than the downward sensor's \(y\)-coordinate.
• Horizontal sensors: A sensor emitting rightward (\(2\)) produces a beam covering \( [X, N+1] \); one emitting leftward (\(4\)) covers \( [0, X] \). Two horizontal sensors on the same \(y\)-coordinate conflict if, when one is rightward and the other leftward, the rightward sensor's \(x\)-coordinate is no larger than the leftward sensor's \(x\)-coordinate (and sensors with the same direction always conflict).
• Vertical and horizontal sensors: Let the vertical sensor be at \( (x_v, y_v) \) and the horizontal sensor at \( (x_h, y_h) \). The vertical beam covers \( [y_v, N+1] \) if upward or \( [0, y_v] \) if downward, and the horizontal beam covers \( [x_h, N+1] \) if rightward or \( [0, x_h] \) if leftward. They conflict if \( x_v \) lies within the horizontal beam's \(x\)-interval and \( y_h \) lies within the vertical beam's \(y\)-interval (inclusive).

Each sensor has an importance value \(W[i]\). The overall safety level is the sum of the importance values of all activated sensors. Your task is to choose a set of sensors to activate such that no two laser beams intersect, and the total importance is maximized.

You need to implement the following function:

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

Function Parameters:

• X, Y, D, W: integer arrays of length \(N\). The \(i\)th sensor is located at \( (X[i], Y[i]) \), emits a laser in the direction indicated by \(D[i]\) (\(1\): up, \(2\): right, \(3\): down, \(4\): left), and has importance value \(W[i]\).

Return: The maximum possible safety level (sum of \(W[i]\) for the activated sensors) such that no two sensor beams intersect.

inputFormat

The function receives four arrays of integers X, Y, D, and W of equal length \(N\). The arrays satisfy:

• \(1 \le X[i], Y[i] \le N\)
• \(D[i] \in \{1, 2, 3, 4\}\)

Note: The submitted code should not perform any input/output operations. You only need to implement the function.

outputFormat

The function should return an integer representing the maximum safety level (i.e. the maximum sum of \(W[i]\) values) achievable without any of the activated laser beams intersecting.

sample

X = [1]
Y = [1]
D = [1]
W = [5]

5