TopCoder

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

User's AC Ratio

73.7% (14/19)

Submission's AC Ratio

56.4% (31/55)

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

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 (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