結果
問題 |
No.1947 質より種類数
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:45:58 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 947 bytes |
コンパイル時間 | 496 ms |
コンパイル使用メモリ | 82,192 KB |
実行使用メモリ | 79,920 KB |
最終ジャッジ日時 | 2025-04-15 23:48:39 |
合計ジャッジ時間 | 25,833 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 TLE * 5 |
ソースコード
N, V, C = map(int, input().split()) items = [tuple(map(int, input().split())) for _ in range(N)] dp = [-float('inf')] * (V + 1) dp[0] = 0 for v_i, w_i in items: # Step 1: 0-1 knapsack for buying at least one item (increase kind count) temp = dp.copy() for v_prev in range(V, -1, -1): if v_prev + v_i <= V and dp[v_prev] != -float('inf'): new_v = v_prev + v_i temp[new_v] = max(temp[new_v], dp[v_prev] + C + w_i) # Merge temp into dp for v in range(V + 1): if temp[v] > dp[v]: dp[v] = temp[v] # Step 2: Unbounded knapsack for buying more of the same item (no kind count increase) for v_prev in range(V - v_i + 1): if dp[v_prev] != -float('inf'): new_v = v_prev + v_i if new_v <= V and dp[new_v] < dp[v_prev] + w_i: dp[new_v] = dp[v_prev] + w_i max_value = max(dp) print(max_value if max_value != -float('inf') else 0)