結果

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

ソースコード

diff # 

import sys
import math
from itertools import accumulate

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr +=1
    items = []
    v1 = 0
    for i in range(1, N+1):
        c_i = int(input[ptr])
        v_i = int(input[ptr+1])
        ptr +=2
        if i ==1:
            v1 = v_i
        else:
            items.append( (i, c_i, v_i) )
    
    max_m = N//2  # since i >=2, each contributes at least 2 weight per item
    INF = -10**18
    dp = [ [INF]*(N+1) for _ in range(max_m+1) ]
    dp[0][0] = 0
    
    for (i, c_i, v_i) in items:
        # Binary splitting
        k = 1
        remaining = c_i
        while remaining >0:
            take = min(k, remaining)
            # Update DP in reverse order
            for m in range(max_m, -1, -1):
                for w in range(N, -1, -1):
                    if dp[m][w] == INF:
                        continue
                    new_m = m + take
                    new_w = w + i * take
                    if new_m > max_m or new_w > N:
                        continue
                    if dp[new_m][new_w] < dp[m][w] + v_i * take:
                        dp[new_m][new_w] = dp[m][w] + v_i * take
            remaining -= take
            k *=2
    
    # Precompute max_val[m][w] = max(dp[m][0..w])
    max_val = [ [INF]*(N+1) for _ in range(max_m+1) ]
    for m in range(max_m+1):
        current_max = INF
        for w in range(N+1):
            if dp[m][w] > current_max:
                current_max = dp[m][w]
            max_val[m][w] = current_max
    
    for k in range(1, N+1):
        best = INF
        max_possible_m = min(k, max_m)
        for m in range(0, max_possible_m+1):
            remaining = k - m
            allowed_w = N - remaining
            if allowed_w <0:
                continue
            allowed_w = min(allowed_w, N)
            current_val = max_val[m][allowed_w]
            if current_val == INF:
                continue
            total = current_val + remaining * v1
            if total > best:
                best = total
        print(best)
    
if __name__ == '__main__':
    main()
0