1976 . 區間的線段（Rangehit）
TopCoder
Tags
Description
有 $n$ 個線段，每個線段以左右兩端點$ L_i $與$ R_i $表示，其中 $0 \le 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 1
3
0 2 -5
1 4 10
3 5 -2
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
0 2 -5
1 5 10
4 6 -2
Sample Output 2
10
Sample Input 3
2
1 9 -3
2 8 -7
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 |