結果
問題 |
No.1947 質より種類数
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:44:04 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,868 bytes |
コンパイル時間 | 515 ms |
コンパイル使用メモリ | 82,004 KB |
実行使用メモリ | 93,160 KB |
最終ジャッジ日時 | 2025-04-15 23:46:57 |
合計ジャッジ時間 | 6,085 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 11 TLE * 1 -- * 25 |
ソースコード
import sys def main(): input = sys.stdin.read().split() idx = 0 N = int(input[idx]); idx +=1 V = int(input[idx]); idx +=1 C = int(input[idx]); idx +=1 items = [] for _ in range(N): v = int(input[idx]); idx +=1 w = int(input[idx]); idx +=1 items.append((v, w)) # dp[k][v] = max sum of w, -inf if not reachable dp = [[-1]*(V+1) for _ in range(N+1)] dp[0][0] = 0 # 0 types, 0 yen for vi, wi in items: # First, handle adding this item as a new type (k+1) # We need to process k in reverse to avoid reusing the same item multiple times in this step for k in range(N-1, -1, -1): for v in range(V, -1, -1): if dp[k][v] == -1: continue # Buy at least one, so new_v = v + x*vi where x >=1 # We first buy one, then see how many more we can buy new_v = v + vi if new_v > V: continue new_sum = dp[k][v] + wi if new_sum > dp[k+1][new_v]: dp[k+1][new_v] = new_sum # Now, for each k+1, perform the unbounded knapsack (buy more of the same item) for k in range(N): current_k = k +1 for v in range(vi, V+1): prev_v = v - vi if dp[current_k][prev_v] == -1: continue if dp[current_k][v] < dp[current_k][prev_v] + wi: dp[current_k][v] = dp[current_k][prev_v] + wi max_result = 0 for k in range(N+1): for v in range(V+1): if dp[k][v] != -1: current = k * C + dp[k][v] if current > max_result: max_result = current print(max_result) if __name__ == "__main__": main()