Day 167-Q3 — 2026-10-01 | 個数制限付きナップサック（余りの類ごとの単調キューで O(NW)。k·v のずらしを忘れない）

📋 コピーimport sys
from collections import deque
def solve(W, items):
    dp = [0] * (W + 1)            # dp[j] = 重さ j 以下で達成できる最大価値
    for w, v, c in items:
        new = dp[:]
        for r in range(min(w, W + 1)):
            dq = deque()          # (k, f) 単調減少の f = dp[r+k*w] - k*v
            k = 0
            j = r
            while j <= W:
                f = dp[j] - k * v
                while dq and dq[-1][1] <= f: dq.pop()
                dq.append((k, f))
                if dq[0][0] < k - c: dq.popleft()     # 使う個数は k-c..k
                new[j] = dq[0][1] + k * v
                k += 1; j += w
        dp = new
    return dp[W]
def main():
    data = sys.stdin.read().split()
    n, W = int(data[0]), int(data[1])
    items = [(int(data[2+3*i]), int(data[3+3*i]), int(data[4+3*i])) for i in range(n)]
    print(solve(W, items))
if __name__ == "__main__": main()