839 . 黃金魔法師

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

dnda
Burn chicken everyday...

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

27.3% (3/11)

Tags

apcsc apcsc-exam2

Description

小樂是一名魔法師，他可以藉由使用一些咒語，來獲得黃金。

具體來說，小樂現在有 $10^ 9$ 個魔法元素，依序編號為 $1$ 到 $10^ 9$ ，每個魔法元素恰好各有一個。同時，小樂也學會了 $N$ 個咒語，第 $i$ 咒語需要使用編號 $l_i, l_i + 1, \dots, r_i$ 的魔法元素，每個魔法元素都需要恰好一個。如果成功蒐集到這些元素後，小樂可以施展魔法，變出 $w_i$ 個黃金。

現在，小樂希望變出盡量多的黃金，現在請你告訴他，最多可以變出多少黃金。

注意到可以變出的黃金數量有可能超過 int 整數儲存的範圍！

Input Format

輸入的第一行包含一個正整數 $N$，代表小樂學會的咒語數量。

接下來的 $N$ 行，每行包含三個正整數 $l_i, r_i, w_i$，代表第 $i$ 個咒語需要用到魔法元素 $l_i, l_i + 1, \dots, r_i$，並且可以獲得 $w_i$ 個黃金。

  • $1 \leq N \leq 2 \times 10^ 5$
  • $1 \leq l_i \leq r_i \leq 10^ 9$
  • $1 \leq w_i \leq 10^ 9$

Output Format

輸出一個整數，代表小樂可以最多可以變出的黃金數量。

Sample Input 1

4
1 4 1
2 6 1
2 3 1
4 7 1

Sample Output 1

2

Sample Input 2

6
1 5 8
4 9 2
3 8 5
6 12 5
3 7 10
7 9 12

Sample Output 2

20

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~11 $M = 1, N \leq 1000$ 20
3 0~21 $M \leq 2$ 30
4 0~30 無額外限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 3 4
1 2000 524288 65536 1 3 4
2 2000 524288 65536 2 3 4
3 2000 524288 65536 2 3 4
4 2000 524288 65536 2 3 4
5 2000 524288 65536 2 3 4
6 2000 524288 65536 2 3 4
7 2000 524288 65536 2 3 4
8 2000 524288 65536 2 3 4
9 2000 524288 65536 2 3 4
10 2000 524288 65536 2 3 4
11 2000 524288 65536 2 3 4
12 2000 524288 65536 3 4
13 2000 524288 65536 3 4
14 2000 524288 65536 3 4
15 2000 524288 65536 3 4
16 2000 524288 65536 3 4
17 2000 524288 65536 3 4
18 2000 524288 65536 3 4
19 2000 524288 65536 3 4
20 2000 524288 65536 3 4
21 2000 524288 65536 3 4
22 2000 524288 65536 4
23 2000 524288 65536 4
24 2000 524288 65536 4
25 2000 524288 65536 4
26 2000 524288 65536 4
27 2000 524288 65536 4
28 2000 524288 65536 4
29 2000 524288 65536 4
30 2000 524288 65536 4
Submit
Back to Top