結果

問題 No.2026 Yet Another Knapsack Problem
ユーザー lam6er
提出日時 2025-03-31 17:53:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,794 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 82,472 KB
実行使用メモリ 87,108 KB
最終ジャッジ日時 2025-03-31 17:55:29
合計ジャッジ時間 44,584 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

    c1 = N
    v1 = int(input[ptr+1])
    ptr += 2  # first line is type 1

    other_items = []
    for i in range(2, N+1):
        ci = int(input[ptr])
        vi = int(input[ptr+1])
        ptr +=2
        other_items.append( (i, ci, vi) )  # i is the weight, ci is count, vi is value per item

    # Precompute DP_other[j][m], j <=1250, m <=2500
    max_j_other = N // 2  # since other items have weight >=2, j <= m//2 and m <=N. max_j is N//2 for N even
    dp_other = [ [ -float('inf') ] * (N+1) for _ in range(max_j_other + 1) ]
    dp_other[0][0] = 0

    for (weight, cnt, val) in other_items:
        # Decompose cnt into binary components
        s = 1
        components = []
        remaining = cnt
        while remaining > 0:
            current = min(s, remaining)
            components.append(current)
            remaining -= current
            s *= 2

        for s_part in components:
            # For each component, process 0-1
            # We need to update dp_other, but in reverse order
            for j in reversed(range(max_j_other + 1 - s_part)):
                for m in reversed(range(N + 1 - s_part * weight)):
                    if dp_other[j][m] == -float('inf'):
                        continue
                    new_j = j + s_part
                    new_m = m + s_part * weight
                    if new_j > max_j_other or new_m > N:
                        continue
                    new_val = dp_other[j][m] + s_part * val
                    if new_val > dp_other[new_j][new_m]:
                        dp_other[new_j][new_m] = new_val

    # Compute prefix max for each j
    max_prefix = [ [ -float('inf') ] * (N+1) for _ in range(max_j_other +1) ]
    for j in range(max_j_other + 1):
        current_max = -float('inf')
        for m in range(N+1):
            if dp_other[j][m] > current_max:
                current_max = dp_other[j][m]
            max_prefix[j][m] = current_max

    # Now compute each k's answer
    for k in range(1, N+1):
        max_val = -float('inf')
        # j can be from 0 to min(k, max_j_other)
        max_possible_j = min(k, max_j_other)
        for j in range(0, max_possible_j +1):
            s = k - j
            if s <0:
                continue
            m_max_allowed = N - k + j
            if m_max_allowed <0:
                continue
            m_max_allowed = min(m_max_allowed, N)
            current_other = max_prefix[j][m_max_allowed]
            if current_other == -float('inf'):
                continue
            total = current_other + s * v1
            if total > max_val:
                max_val = total
        print(max_val)

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