結果

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

ソースコード

diff # 

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