TopCoder

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

User's AC Ratio

90.9% (10/11)

Submission's AC Ratio

61.1% (22/36)

Description

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

Input Format

第一行有一個正整數 n,代表線段的數量。接下來有 n 行,每行以三個整數表示一個線
段,分別是$L_i$、$R_i $與$ W_i$。

子任務(測資) 額外限制 分數
1 (0~3) $M\leq 100, n\leq 10$ 9
2 (0~7) $M\leq 10^ 6, n\leq 100$ 13
3 (0~11) $M\leq 10^ 6, n\leq 1000$ 15
4 (12~15) $M\leq 10^ 6, n\leq 5\times 10^ 4$,每個線段$L_i=R_i$ 14
5 (0~19) $M\leq 10^ 6, n\leq 5\times 10^ 4$ 24
6 (0~23) $M\leq 10^ 9, n\leq 10^ 5$ 25

Output Format

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

Sample Input

#Sample Input 1
3
0 2 -5
1 4 10
3 5 -2
#Sample Input 2
3
0 2 -5
1 5 10
4 6 -2
#Sample Input 3
2
1 9 -3
2 8 -7

Sample Output

#Sample Output 1
8
#Sample Output 2
10
#Sample Output 3
0

Hints

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

Problem Source

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

Subtasks

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