TopCoder

Thumb 343jksfld
ltf0501
願與最重要之人能再次相會。

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

58.3% (7/12)

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

For Testdata: 0 ~ 4, Score: 11
For Testdata: 0 ~ 9, Score: 18
For Testdata: 0 ~ 14, Score: 23
For Testdata: 0 ~ 19, Score: 48
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 262144 65536
1 1000 262144 65536
2 1000 262144 65536
3 1000 262144 65536
4 1000 262144 65536
5 1000 262144 65536
6 1000 262144 65536
7 1000 262144 65536
8 1000 262144 65536
9 1000 262144 65536
10 1000 262144 65536
11 1000 262144 65536
12 1000 262144 65536
13 1000 262144 65536
14 1000 262144 65536
15 1000 262144 65536
16 1000 262144 65536
17 1000 262144 65536
18 1000 262144 65536
19 1000 262144 65536