結果

問題 No.1947 質より種類数
ユーザー gew1fw
提出日時 2025-06-12 20:56:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,361 bytes
コンパイル時間 361 ms
コンパイル使用メモリ 82,656 KB
実行使用メモリ 104,124 KB
最終ジャッジ日時 2025-06-12 20:59:34
合計ジャッジ時間 8,279 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 TLE * 2 -- * 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))
    
    INF = float('-inf')
    dp = [[INF] * (N + 1) for _ in range(V + 1)]
    dp[0][0] = 0
    
    for v, w in items:
        # Step 1: Include exactly one item of this type
        for j in range(V, v - 1, -1):
            for k in range(N, -1, -1):
                if dp[j - v][k] != INF:
                    if dp[j][k + 1] < dp[j - v][k] + w:
                        dp[j][k + 1] = dp[j - v][k] + w
        # Step 2: Include any number of items (including zero) of this type
        for j in range(v, V + 1):
            for k in range(N + 1):
                if dp[j - v][k] != INF:
                    if dp[j][k] < dp[j - v][k] + w:
                        dp[j][k] = dp[j - v][k] + w
    
    max_satisfaction = 0
    for j in range(V + 1):
        for k in range(N + 1):
            if dp[j][k] != INF:
                satisfaction = dp[j][k] + C * k
                if satisfaction > max_satisfaction:
                    max_satisfaction = satisfaction
    print(max_satisfaction)

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