結果

問題 No.2026 Yet Another Knapsack Problem
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:39:59
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,401 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 82,556 KB
実行使用メモリ 78,716 KB
最終ジャッジ日時 2025-03-31 17:41:11
合計ジャッジ時間 25,126 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    c = []
    v = []
    index = 1
    for _ in range(N):
        ci = int(data[index])
        vi = int(data[index + 1])
        c.append(ci)
        v.append(vi)
        index += 2
    
    # Initialize DP table
    INF = -10**18
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    
    # Process each item using binary decomposition for bounded knapsack
    for i in range(N):
        ci = c[i]
        vi = v[i]
        weight = i + 1  # since items are 1-based in the problem
        
        remaining = ci
        x = 1
        while remaining > 0:
            curr = min(x, remaining)
            # Process adding curr copies
            for k in range(N, curr - 1, -1):
                for w in range(N, curr * weight - 1, -1):
                    if dp[k - curr][w - curr * weight] != INF:
                        if dp[k][w] < dp[k - curr][w - curr * weight] + curr * vi:
                            dp[k][w] = dp[k - curr][w - curr * weight] + curr * vi
            remaining -= curr
            x <<= 1
    
    # Compute the maximum for each k
    for k in range(1, N + 1):
        max_val = INF
        for w in range(k, N + 1):
            if dp[k][w] > max_val:
                max_val = dp[k][w]
        print(max_val)

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