結果

問題 No.2026 Yet Another Knapsack Problem
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:30:02
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,955 bytes
コンパイル時間 449 ms
コンパイル使用メモリ 81,156 KB
実行使用メモリ 82,228 KB
最終ジャッジ日時 2025-04-16 00:32:29
合計ジャッジ時間 31,996 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 35 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    
    v1 = 0
    items = []
    for i in range(1, N+1):
        c = int(input[ptr])
        v = int(input[ptr+1])
        ptr += 2
        if i == 1:
            v1 = v
        else:
            items.append((i, c, v))
    
    m_max = N // 2
    INF = float('-inf')
    dp = [[INF] * (N + 1) for _ in range(m_max + 1)]
    dp[0][0] = 0
    
    for (i, c, v) in items:
        max_t = min(c, N // i)
        remaining = max_t
        t = 1
        while remaining > 0:
            current_t = min(t, remaining)
            for m in range(m_max, -1, -1):
                for w in range(N, -1, -1):
                    if dp[m][w] == INF:
                        continue
                    new_m = m + current_t
                    new_w = w + current_t * i
                    if new_m > m_max or new_w > N:
                        continue
                    if dp[new_m][new_w] < dp[m][w] + current_t * v:
                        dp[new_m][new_w] = dp[m][w] + current_t * v
            remaining -= current_t
            t <<= 1
    
    max_val = [[-INF] * (N + 1) for _ in range(m_max + 1)]
    for m in range(m_max + 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):
        ans = -INF
        max_m = min(k, m_max)
        for m in range(0, max_m + 1):
            remaining = k - m
            upper_w = N - remaining
            lower_w = 2 * m
            if upper_w < lower_w or upper_w < 0:
                continue
            if upper_w > N:
                upper_w = N
            current_val = max_val[m][upper_w] + remaining * v1
            if current_val > ans:
                ans = current_val
        print(ans)

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