1974 . 十字射擊（Cross）
TopCoder
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 1
3
0 2 5 4 1
5 4 7 6 2
8 7 9 9 3
0 2 5 4 1
5 4 7 6 2
8 7 9 9 3
Sample Output 1
6
Sample Input 2
4
1 1 2 2 2
3 1 4 2 3
1 3 2 4 4
3 3 4 4 5
1 1 2 2 2
3 1 4 2 3
1 3 2 4 4
3 3 4 4 5
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 |