結果

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

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    
    # Read type 1 separately (though we handle other types first)
    type1_c = N
    type1_v = int(input[ptr+1])
    ptr += 2
    # Read other types (2..N)
    others = []
    for i in range(2, N+1):
        c_i = int(input[ptr])
        v_i = int(input[ptr+1])
        ptr += 2
        others.append( (i, c_i, v_i) )
    
    # Initialize DP_other[k_off][w_off]
    INF = -1 << 60
    dp_other = [ [INF]*(N+1) for _ in range(N+1) ]
    dp_other[0][0] = 0
    
    # Process other types using binary decomposition
    for (i, c_i, v_i) in others:
        # Binary decomposition
        m = c_i
        parts = []
        power = 1
        while m > 0:
            if m >= power:
                parts.append(power)
                m -= power
                power <<=1
            else:
                parts.append(m)
                m = 0
        # Process each part
        for part in parts:
            add_k = part
            add_w = part * i
            add_v = part * v_i
            # Reverse iteration to prevent overcounting
            for k_off in range(N, -1, -1):
                for w_off in range(N, -1, -1):
                    if dp_other[k_off][w_off] != INF:
                        new_k = k_off + add_k
                        new_w = w_off + add_w
                        if new_k > N or new_w > N:
                            continue
                        if dp_other[new_k][new_w] < dp_other[k_off][w_off] + add_v:
                            dp_other[new_k][new_w] = dp_other[k_off][w_off] + add_v
    
    # Build prefix_max for each k_off
    prefix_max = [ [INF]*(N+2) for _ in range(N+1) ]  # prefix_max[k_off][s] is max up to s
    for k_off in range(N+1):
        max_val = INF
        for w_off in range(N+1):
            if dp_other[k_off][w_off] > max_val:
                max_val = dp_other[k_off][w_off]
            prefix_max[k_off][w_off] = max_val
    
    # Compute answer for each k from 1 to N
    for k in range(1, N+1):
        ans = INF
        max_k_off = min(k, N)
        for k_off in range(0, max_k_off+1):
            m = k - k_off
            # Required w_off <= N - m
            s = N - m
            if s < 0:
                continue
            s = min(s, N)
            current_max = prefix_max[k_off][s]
            if current_max == INF:
                continue
            current = current_max + m * type1_v
            if current > ans:
                ans = current
        print(ans)
    
if __name__ == "__main__":
    main()
0