結果

問題 No.2026 Yet Another Knapsack Problem
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:52:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,265 bytes
コンパイル時間 155 ms
コンパイル使用メモリ 81,824 KB
実行使用メモリ 78,428 KB
最終ジャッジ日時 2025-04-16 00:55:08
合計ジャッジ時間 22,410 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    
    type_1_value = 0
    c = []
    v = []
    for i in range(N):
        ci = int(input[idx])
        vi = int(input[idx+1])
        idx +=2
        if i ==0:
            type_1_value = vi
        else:
            c.append(ci)
            v.append(vi)
    
    items = []
    for i in range(2, N+1):
        ci = c[i-2]
        vi = v[i-2]
        current_ci = ci
        s = 1
        while current_ci >0:
            s = min(s, current_ci)
            items.append( (s, i*s, vi*s) )
            current_ci -= s
            s *=2
    
    max_t = 1250
    max_w = N
    dp = [ [ -float('inf') ] * (max_w +1) for _ in range(max_t +1) ]
    dp[0][0] = 0
    
    for s, s_i, s_v in items:
        for t in range(max_t, -1, -1):
            for w in range(max_w, -1, -1):
                if dp[t][w] == -float('inf'):
                    continue
                new_t = t + s
                new_w = w + s_i
                if new_t > max_t or new_w > max_w:
                    continue
                if dp[new_t][new_w] < dp[t][w] + s_v:
                    dp[new_t][new_w] = dp[t][w] + s_v
    
    max_prefix = [ [ -float('inf') ] * (max_w +1) for _ in range(max_t +1) ]
    for t in range(max_t +1):
        current_max = -float('inf')
        for x in range(max_w +1):
            if x >=0:
                if dp[t][x] > current_max:
                    current_max = dp[t][x]
                max_prefix[t][x] = current_max
    
    for k in range(1, N+1):
        max_val = -float('inf')
        max_t_possible = min(k, max_t)
        for t in range(0, max_t_possible +1):
            remaining = k - t
            if remaining <0:
                continue
            x = N - remaining
            if x <0:
                continue
            if t > max_t:
                continue
            current_max = max_prefix[t][x] if x <= max_w else -float('inf')
            if current_max == -float('inf'):
                continue
            current_val = current_max + remaining * type_1_value
            if current_val > max_val:
                max_val = current_val
        print(max_val)
    
if __name__ == "__main__":
    main()
0