1976 . 區間的線段（Rangehit）

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

77.6% (52/67)

Submission's AC Ratio

31.6% (85/269)

Tags

TOI 2017-TOI-3rd sorting

Description

　　有 n 個線段，每個線段以左右兩端點Li與Ri表示，其中 0≤i<n。此外，每個線段還附有一個權重 Wi，這個權重可能是正的也可能是負的。現在要挑選一個區間 [S,T] 使得與此區間有重疊的所有線段的權重總和為最大。一個線段如果與此區間的交集至少包含一點就稱為兩者重疊。
請你寫一個程式，算出最大的權重總和。
　　每一個線段的端點都是不大於 M 的非負整數，每個線段的權重 Wi 是一個介於 –1000 與 1000 之間的整數。所挑選的區間兩端 S 與 T 必須是整數，但沒有範圍限制，也就是說，可以 S=T；也可能挑與所有線段都不相交的區間，此時的權重總和則是 0。

Input Format

第一行有一個正整數 n，代表線段的數量。接下來有 n 行，每行以三個整數表示一個線
段，分別是 Li、Ri 與 Wi。

子任務（測資） 額外限制 分數
1 (0~3) M≤100,n≤10 9
2 (0~7) M≤106,n≤100 13
3 (0~11) M≤106,n≤1000 15
4 (12~15) M≤106,n≤5×104，每個線段Li=Ri 14
5 (0~19) M≤106,n≤5×104 24
6 (0~23) M≤109,n≤105 25

Output Format

請輸出所求的最大權重總和。

Sample Input 1

3
0 2 -5
1 4 10
3 5 -2

Sample Output 1

8

Sample Input 2

3
0 2 -5
1 5 10
4 6 -2

Sample Output 2

10

Sample Input 3

2
1 9 -3
2 8 -7

Sample Output 3

0

Hints

本題在考試時測資錯誤（最後一個測資有 L>R 的情況）。

Problem Source

題目取自2017 TOI選訓第三次模擬考pB

Subtasks

No. Testdata Range Score
1 0~3 9
2 0~7 13
3 0~11 15
4 12~15 14
5 0~19 24
6 0~23 25

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1 2 3 5 6
1 1000 262144 262144 1 2 3 5 6
2 1000 262144 262144 1 2 3 5 6
3 1000 262144 262144 1 2 3 5 6
4 1000 262144 262144 2 3 5 6
5 1000 262144 262144 2 3 5 6
6 1000 262144 262144 2 3 5 6
7 1000 262144 262144 2 3 5 6
8 1000 262144 262144 3 5 6
9 1000 262144 262144 3 5 6
10 1000 262144 262144 3 5 6
11 1000 262144 262144 3 5 6
12 1000 262144 262144 4 5 6
13 1000 262144 262144 4 5 6
14 1000 262144 262144 4 5 6
15 1000 262144 262144 4 5 6
16 1000 262144 262144 5 6
17 1000 262144 262144 5 6
18 1000 262144 262144 5 6
19 1000 262144 262144 5 6
20 1000 262144 262144 6
21 1000 262144 262144 6
22 1000 262144 262144 6
23 1000 262144 262144 6
Submit
Back to Top