729 . 防禦塔

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

75.0% (9/12)

Tags

apcsc apcsc-greedy

Description

小風正在玩一個塔防遊戲，和一般的塔防遊戲不同，這款遊戲是要藉由建造塔本身來進行防禦。在一個關卡中會提供 N 件材料讓玩家建造塔，第 i 件材料有三種屬性：重量 wi、耐久值 si、以及防禦度 vi。建造塔的方式就是從這些材料選一些出來從上至下排列蓋成一座塔，蓋塔需要滿足一個重要的條件：

  • 在塔中的每一件材料 i，其耐久度 si 不小於在該材料上方的所有材料重量總和。

小風希望能蓋出防禦度總和最高的塔，請你幫小風計算防禦度最高可以達到多少。

Input Format

輸入第一行有一個正整數 N(1≤N≤1000)，代表材料的數量。
接下來的 N 行，第 i 行有三個整數 wi,si,vi(1≤wi,si≤10000,1≤vi≤109)，分別代表第 i 件材料的三種屬性。

Output Format

請輸出一個整數，代表防禦度總和的最大值。

Sample Input 1

3
2 2 20
2 1 30
3 1 40

Sample Output 1

50

Sample Input 2

4
1 2 10
3 1 10
2 4 10
1 6 10

Sample Output 2

40

Sample Input 3

5
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000

Sample Output 3

5000000000

Sample Input 4

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

Sample Output 4

22

Hints

Problem Source

AtCoder

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測資 0
2 0~22 無額外限制 100

Testdata and Limits

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