Overview

We compute the optimal value of the 0/1 knapsack using DP, then determine “which treasure boxes are included in at least one optimal solution” by tracing back through all optimal solutions simultaneously in reverse.

Analysis

This problem is a classic 0/1 knapsack, but what we want to find is not the maximum value itself, but rather:

• For each treasure box \(i\): “Does there exist an optimal solution that includes treasure box \(i\)?”

The key point is that there may be multiple optimal solutions, so simply reconstructing one optimal solution and checking what it contains is insufficient.

Why naive approaches are too slow

• Fixing each treasure box as “must include” and re-solving the knapsack, or “excluding” it and re-solving, would require running the DP \(N\) times, resulting in \(O(N^2M)\) which is too heavy (\(1000^2 \cdot 3000\) is not practical).
• Enumerating all optimal solutions is obviously exponential and infeasible.

Solution approach

First, compute the “optimal value” for all \(i,w\) using standard DP (forward DP table). Then, on the DP table, trace back only the “transitions corresponding to optimal solutions,” managing all states that can be part of an optimal solution collectively.

The DP table can be viewed as a directed acyclic graph (DAG): - From state \((i,w)\) to \((i-1,w)\) (not including treasure box \(i\)) - From state \((i,w)\) to \((i-1,w-A_i)\) (including treasure box \(i\))

Whichever of these (or both) preserves the optimal value is an “optimal transition.”

By tracing these “optimal transitions” in reverse, any treasure box for which the “include transition” appears even once on some optimal solution path is answered as Yes.

Algorithm

1. Compute maximum value with DP

Define \(dp[i][w]\) as: - “The maximum value obtainable using only the first \(i\) treasure boxes with capacity at most \(w\).”

The transitions are the standard 0/1 knapsack:

• Don’t include: \(dp[i][w] = dp[i-1][w]\)
• Include (if \(w \ge A_i\)): \(dp[i][w] = \max(dp[i][w],\ dp[i-1][w-A_i] + B_i)\)

The optimal value is \(dp[N][M]\).

2. Simultaneously trace back all “states that can be part of an optimal solution” in reverse

Since there may be multiple optimal solutions, instead of reconstructing a single one, we maintain the set of reachable states.

• Let reach[w] = 1 mean “the current state \((i,w)\) is reachable from \((N,M)\) by following only optimal transitions.”
• Initially, only \((N,M)\) is reachable, so reach[M]=1.

For \(i=N,N-1,\dots,1\), from each reachable state \((i,w)\), extend only “optimal transitions” to \((i-1,*)\):

• If the “don’t include” transition is optimal:
  • Condition: \(dp[i][w] = dp[i-1][w]\)
  • Next reachable state: \((i-1,w)\)
• If the “include” transition is optimal:
  • Condition: \(w\ge A_i\) and \(dp[i][w] = dp[i-1][w-A_i] + B_i\)
  • Next reachable state: \((i-1,w-A_i)\)
  • Furthermore, “an optimal solution including treasure box \(i\) exists,” so set included[i]=True

This way, we trace all “optimal solution paths starting from \((N,M)\)” collectively, allowing us to determine without omission whether each treasure box is included in some optimal solution.

Complexity

• Time complexity: \(O(NM)\)
  
  • DP construction is \(O(NM)\), and the reverse reachability check is also \(O(NM)\)
• Space complexity: \(O(NM)\)
  
  • The full \(dp\) table must be stored for reconstruction, requiring \(O(NM)\)

Implementation Notes

• The total value can be up to \(1000 \cdot 10^9 = 10^{12}\), so 64-bit integers are required (in Python, the standard int works fine, but array('q') can be used for speedup).

• The reachability set reach for the reverse search can be implemented as a bytearray of length \(M+1\) for speed and memory efficiency.

• In the reverse pass, we check “equality” to determine whether a transition is optimal:

  • \(dp[i][w] == dp[i-1][w]\) (not including is also optimal)

  • \(dp[i][w] == dp[i-1][w-A_i] + B_i\) (including is optimal) Both conditions may hold simultaneously, and in that case it is important to keep both transitions (because the optimal solutions branch).

    Source Code

import sys
from array import array

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]

    A = [0] * (N + 1)
    B = [0] * (N + 1)
    p = 2
    for i in range(1, N + 1):
        A[i] = data[p]
        B[i] = data[p + 1]
        p += 2

    # dp[i][w] = max value using first i items with capacity w
    dp = [array('q', [0]) * (M + 1)]
    for i in range(1, N + 1):
        a = A[i]
        b = B[i]
        prev = dp[i - 1]
        cur = array('q', prev)  # exclude by default
        for w in range(a, M + 1):
            v = prev[w - a] + b
            if v > cur[w]:
                cur[w] = v
        dp.append(cur)

    included = [False] * (N + 1)

    # reachable capacities at step i (state (i, w)) along some optimal path from (N, M)
    reach = bytearray(M + 1)
    reach[M] = 1

    for i in range(N, 0, -1):
        a = A[i]
        b = B[i]
        cur = dp[i]
        prev = dp[i - 1]
        next_reach = bytearray(M + 1)

        r = reach
        nr = next_reach
        for w in range(M + 1):
            if not r[w]:
                continue
            v = cur[w]
            if v == prev[w]:
                nr[w] = 1
            if w >= a and v == prev[w - a] + b:
                included[i] = True
                nr[w - a] = 1

        reach = next_reach

    out = []
    for i in range(1, N + 1):
        out.append("Yes" if included[i] else "No")
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.