1974 . 十字射擊（Cross）

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

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

User's AC Ratio

89.7% (61/68)

Submission's AC Ratio

35.0% (144/412)

Tags

TOI 2017-TOI-2nd data-structures

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

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

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 (VSS, 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
Submit
Back to Top