結果

問題 No.1947 質より種類数
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0