1407 . Striker的秘密 - EXTREME

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

85.8% (97/113)

Submission's AC Ratio

34.4% (208/605)

Tags

CKsum 2008-CKsum-4th DP 背包問題

Description

請參考 TIOJ 1387 Striker的秘密

隨著時代在進步，Striker的載重上限以及"櫻石"開採技術有重大突破，你原本的程式已經無法計算了。

請寫一個新的程式解決這個問題吧！

Input Format

本題只有一筆測試資料

第一行有一個數字n，代表博士有n種”櫻石”(1<=n<=100,000)

第二行開始有n行，每行有三個數字Wi,Mi,Ci以空白隔開，代表此種櫻石的重量、魔力增幅值、數量(1<=Wi,Mi,Ci<=1000)

最後一行有一個數字T，代表Striker所能搭載的最大上限。(1<=T<=1,000,000，但是n*T<=10,000,000)

Output Format

請輸出一個數字k代表能達到的最大魔力增幅值

Sample Input 1

5
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
15

Sample Output 1

15

Hints

Problem Source

原TIOJ1407 / 快樂暑假營第四次練習比賽。Problem Setter：Tmt。

Subtasks

No. Testdata Range Score
1 0 3
2 1 3
3 2 3
4 3 3
5 4 3
6 5 3
7 6 3
8 7 3
9 8 3
10 9 3
11 10 3
12 11 3
13 12 3
14 13 3
15 14 3
16 15 3
17 16 3
18 17 3
19 18 3
20 19 3
21 20 3
22 21 3
23 22 3
24 23 3
25 24 3
26 25 3
27 26 3
28 27 3
29 28 3
30 29 3
31 30 3
32 31 7

Testdata and Limits

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