TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

97.6% (41/42)

Submission's AC Ratio

32.7% (101/309)

Description

平面上有 n 個矩形目標,這些矩形可能彼此重疊。每個矩形有一個價值$w_i$。現在想選擇一點 P,通過此點發射出一條水平與一條垂直的射擊線,這兩條線所經過所有矩形價值總和就是本次射擊的得分,本題要計算出一次射擊的最高得分。所謂直線通過矩形是指兩者至少交集一點,也就是說若射擊線有碰到矩形四個邊之中的任何一個邊,就算直線通過矩形了。

Input Format

第一行是一個正整數$2\leq n$,接下來有$n$行,每行五個整數表示一個矩形,依序是$x_1, y_1, x_2, y_2, w_i$,$(x_1, y_1) $和$ (x_2, y_2) $是矩形中一條對角線兩端點的座標,其中$ 0 ≤ x_1 < x_2 < M, 0≤ y_1 < y_2 < M $代表矩形的水平與垂直座標範圍,而$w_i$是不超過 100 的非負整數代表此矩形的價值。

子任務(測資) 額外限制 分數
1 (0~4) $M\leq 10^ 5, n\leq 100$ 11
2 (0~9) $M\leq 10^ 5, n\leq 10^ 3$ 18
3 (0~14) $M\leq 10^ 5, n\leq 10^ 5$ 23
4 (0~19) $M\leq 10^ 9, n\leq 10^ 5$ 48

Output Format

輸出一次射擊的最高得分。

Sample Input

#Sample Input 1
3
0 2 5 4 1
5 4 7 6 2
8 7 9 9 3
#Sample Input 2
4
1 1 2 2 2
3 1 4 2 3
1 3 2 4 4
3 3 4 4 5

Sample Output

#Sample Output 1
6
#Sample Output 2
12

Hints

Problem Source

題目取自2017 TOI選訓第二次模擬考pD
Problem set by Yihda Yol

Subtasks

No. Testdata Range Score
1 0~4 11
2 0~9 18
3 0~14 23
4 0~19 48

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1 2 3 4
1 1000 262144 262144 1 2 3 4
2 1000 262144 262144 1 2 3 4
3 1000 262144 262144 1 2 3 4
4 1000 262144 262144 1 2 3 4
5 1000 262144 262144 2 3 4
6 1000 262144 262144 2 3 4
7 1000 262144 262144 2 3 4
8 1000 262144 262144 2 3 4
9 1000 262144 262144 2 3 4
10 1000 262144 262144 3 4
11 1000 262144 262144 3 4
12 1000 262144 262144 3 4
13 1000 262144 262144 3 4
14 1000 262144 262144 3 4
15 1000 262144 262144 4
16 1000 262144 262144 4
17 1000 262144 262144 4
18 1000 262144 262144 4
19 1000 262144 262144 4