結果

問題 No.2026 Yet Another Knapsack Problem
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:20:59
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,378 bytes
コンパイル時間 242 ms
コンパイル使用メモリ 81,772 KB
実行使用メモリ 90,280 KB
最終ジャッジ日時 2025-04-15 22:23:15
合計ジャッジ時間 69,824 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

    v1 = int(input[ptr + 1])
    ptr += 2  # skip c1 which is N

    non_type1 = []
    for i in range(2, N + 1):
        ci = int(input[ptr])
        vi = int(input[ptr + 1])
        ptr += 2
        non_type1.append((ci, vi, i))

    # Initialize value_non[m][w]
    value_non = [[-float('inf')] * (N + 1) for _ in range(N + 1)]
    value_non[0][0] = 0

    for ci, vi, i in non_type1:
        # Binary decomposition of ci
        cnt = ci
        parts = []
        current = 1
        while cnt > 0:
            part = min(current, cnt)
            parts.append(part)
            cnt -= part
            current <<= 1
        for part in parts:
            part_val = part * vi
            part_weight = part * i
            part_count = part
            # Update DP in reverse
            for m in range(N, part_count - 1, -1):
                for w in range(N, part_weight - 1, -1):
                    if value_non[m - part_count][w - part_weight] != -float('inf'):
                        if value_non[m - part_count][w - part_weight] + part_val > value_non[m][w]:
                            value_non[m][w] = value_non[m - part_count][w - part_weight] + part_val

    # Post-process to invalidate w < 2m
    for m in range(N + 1):
        for w in range(N + 1):
            if w < 2 * m:
                value_non[m][w] = -float('inf')

    # Precompute prefix_max[m][w]
    prefix_max = [[-float('inf')] * (N + 1) for _ in range(N + 1)]
    for m in range(N + 1):
        current_max = -float('inf')
        for w in range(N + 1):
            current_max = max(current_max, value_non[m][w])
            prefix_max[m][w] = current_max

    # Compute answers for each k_total
    for k_total in range(1, N + 1):
        m_max = min(k_total, N - k_total)
        max_val = -float('inf')
        for m in range(0, m_max + 1):
            W_max = N - k_total + m
            if W_max < 0:
                continue
            if W_max > N:
                W_max = N
            current_max = prefix_max[m][W_max]
            if current_max == -float('inf'):
                continue
            total = current_max + (k_total - m) * v1
            if total > max_val:
                max_val = total
        print(max_val)

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