結果

問題 No.1947 質より種類数
ユーザー gew1fw
提出日時 2025-06-12 20:52:13
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,785 bytes
コンパイル時間 199 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 80,288 KB
最終ジャッジ日時 2025-06-12 20:56:39
合計ジャッジ時間 6,415 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    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))

    # Initialize DP table
    INF = -1
    dp = [[INF] * (V + 1) for _ in range(N + 1)]
    dp[0][0] = 0  # 0 types, 0 cost, 0 value

    for i in range(N):
        v_i, w_i = items[i]
        # First, handle the case where we take at least one of the current item
        # We need to iterate backwards to avoid overwriting the dp array prematurely
        for k in range(N - 1, -1, -1):
            for v in range(V, -1, -1):
                if dp[k][v] == INF:
                    continue
                new_v = v + v_i
                if new_v > V:
                    continue
                new_k = k + 1
                if dp[new_k][new_v] < dp[k][v] + w_i:
                    dp[new_k][new_v] = dp[k][v] + w_i
        # Then, apply the unbounded knapsack for additional items of the same type
        # This does not increase the type count k
        for k in range(N + 1):
            for v in range(V + 1 - v_i):
                if dp[k][v] == INF:
                    continue
                if dp[k][v + v_i] < dp[k][v] + w_i:
                    dp[k][v + v_i] = dp[k][v] + w_i

    max_satisfaction = 0
    for k in range(N + 1):
        max_val = max([val for val in dp[k] if val != INF], default=-1)
        if max_val == -1:
            continue
        satisfaction = max_val + k * C
        if satisfaction > max_satisfaction:
            max_satisfaction = satisfaction

    print(max_satisfaction)

if __name__ == '__main__':
    main()
0