結果

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

ソースコード

diff # 

import sys
import math

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    
    items = []
    for i in range(1, N+1):
        c_i = int(input[ptr])
        v_i = int(input[ptr + 1])
        ptr += 2
        items.append((i, c_i, v_i))
    
    # Initialize DP
    dp = [[-math.inf] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    
    for (i, c_i, v_i) in items:
        if c_i == 0:
            continue
        m_list = []
        cnt = c_i
        power = 1
        while cnt > 0:
            take = min(power, cnt)
            m_list.append(take)
            cnt -= take
            power *= 2
        
        for m in m_list:
            for k in range(N, m-1, -1):
                w_min = m * i
                for w in range(N, w_min-1, -1):
                    prev_k = k - m
                    prev_w = w - (m * i)
                    if prev_w < 0 or prev_k < 0:
                        continue
                    if dp[prev_k][prev_w] != -math.inf:
                        if dp[k][w] < dp[prev_k][prev_w] + m * v_i:
                            dp[k][w] = max(dp[k][w], dp[prev_k][prev_w] + m * v_i)
    
    # Compute answers for each k
    for k in range(1, N+1):
        max_val = -math.inf
        for w in range(k, N+1):
            max_val = max(max_val, dp[k][w])
        print(max_val)

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