結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    items = []
    for i in range(N):
        c_i = int(data[idx])
        v_i = int(data[idx+1])
        idx +=2
        items.append((c_i, v_i))
    
    INF = -10**18
    dp = [ [INF]*(N+2) for _ in range(N+2) ]
    dp[0][0] = 0
    
    for item_idx in range(N):
        c_i, v_i = items[item_idx]
        weight = item_idx + 1
        
        # For each possible remainder r = w_prev - weight * k_prev
        # We process each remainder group separately
        groups = {}
        for k_prev in range(N+1):
            for w_prev in range(N+1):
                if dp[k_prev][w_prev] == INF:
                    continue
                r = w_prev - weight * k_prev
                if r not in groups:
                    groups[r] = []
                groups[r].append((k_prev, dp[k_prev][w_prev]))
        
        new_dp = [row.copy() for row in dp]
        
        for r in groups:
            group = groups[r]
            group.sort()
            q = deque()
            k_new_max = min((N - r) // weight, N)
            if weight == 0:
                continue
            k_new_max = min(k_new_max, N)
            
            ptr = 0
            for k_new in range(k_new_max + 1):
                current_max = INF
                w_new = weight * k_new + r
                if w_new < 0 or w_new > N:
                    continue
                
                window_l = k_new - c_i
                while ptr < len(group) and group[ptr][0] <= k_new:
                    k_prev, val = group[ptr]
                    if k_prev >= window_l:
                        current = val - v_i * k_prev
                        while q and q[-1][1] <= current:
                            q.pop()
                        q.append((k_prev, current))
                    ptr +=1
                
                while q and q[0][0] < window_l:
                    q.popleft()
                
                if q:
                    best = q[0][1] + v_i * k_new
                    if best > new_dp[k_new][w_new]:
                        new_dp[k_new][w_new] = best
        
        dp = new_dp
    
    for k in range(1, N+1):
        max_val = INF
        for w in range(k, N+1):
            if dp[k][w] > max_val:
                max_val = dp[k][w]
        print(max_val)

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