1974 . 十字射擊（Cross）

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

89.9% (62/69)

Submission's AC Ratio

35.6% (149/418)

Tags

TOI 2017-TOI-2nd data-structures

Description

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

Input Format

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

子任務（測資） 額外限制 分數
1 (0~4) M≤105,n≤100 11
2 (0~9) M≤105,n≤103 18
3 (0~14) M≤105,n≤105 23
4 (0~19) M≤109,n≤105 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