AI017. 显存装箱

# 0-1 背包:dp[c]=占用不超 c 的最大收益,容量维倒序防同一模型重复部署
# w=0 的模型只赚不亏,收益单独累加,不进背包循环
import sys


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    cap = int(next(it))
    dp = [0] * (cap + 1)
    for _ in range(n):
        w = int(next(it))
        v = int(next(it))
        if v <= 0:
            continue
        if w == 0:
            dp = [x + v for x in dp]
        elif w <= cap:
            old = dp[: cap + 1 - w]
            dp[w:] = [b + v if b + v > a else a for a, b in zip(dp[w:], old)]
    print(dp[cap])


if __name__ == "__main__":
    solve()