結果

問題 No.2026 Yet Another Knapsack Problem
ユーザー gew1fw
提出日時 2025-06-12 15:36:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,107 bytes
コンパイル時間 185 ms
コンパイル使用メモリ 82,188 KB
実行使用メモリ 94,684 KB
最終ジャッジ日時 2025-06-12 15:38:14
合計ジャッジ時間 71,642 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    items = []
    for i in range(1, N+1):
        c_i = int(input[idx]); idx +=1
        v_i = int(input[idx]); idx +=1
        items.append((i, c_i, v_i))
    
    # Separate item 1
    item1 = items[0]
    other_items = items[1:]
    v1 = item1[2]
    
    # Preprocess other items: g[m][s] is the max value for m items, s = sum (i-1)*t_i
    max_m = N
    max_s = N
    g = [[-float('inf')] * (max_s + 1) for _ in range(max_m + 1)]
    g[0][0] = 0
    
    for (i, c_i, v_i) in other_items:
        t = 1
        remaining = c_i
        while remaining > 0:
            cnt = min(t, remaining)
            # This 'item' represents choosing cnt times
            # weight per item is (i-1)*cnt, value is v_i * cnt, count is cnt
            for m in range(max_m, cnt - 1, -1):
                for s in range(max_s, (i-1)*cnt -1, -1):
                    if g[m - cnt][s - (i-1)*cnt] != -float('inf'):
                        if g[m][s] < g[m - cnt][s - (i-1)*cnt] + v_i * cnt:
                            g[m][s] = g[m - cnt][s - (i-1)*cnt] + v_i * cnt
            remaining -= cnt
            t *= 2
    
    # For each k, compute the answer
    for k in range(1, N+1):
        max_val = -float('inf')
        # t1 is the number of item1 chosen
        for t1 in range(0, k+1):
            m = k - t1
            if m < 0:
                continue
            # s can be up to N -k
            max_s_possible = N - k
            if max_s_possible < 0:
                continue
            # Find the maximum value in g[m][0..max_s_possible]
            current_max = -float('inf')
            for s in range(0, max_s_possible +1):
                if s > max_s:
                    continue
                if g[m][s] > current_max:
                    current_max = g[m][s]
            if current_max != -float('inf'):
                total = t1 * v1 + current_max
                if total > max_val:
                    max_val = total
        print(max_val)

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