Overview

For each treasure chest, this problem asks us to determine whether the maximum value of a knapsack problem — under the constraint that this particular chest must be selected — equals the overall maximum value.

Analysis

First, if we only need to find the overall maximum value, we can solve it in \(O(NM)\) using the well-known “knapsack DP.” However, in this problem, we need to find “the maximum value when treasure chest \(i\) is necessarily selected” for each chest \(i\). A naive approach would involve re-running the knapsack DP \(N\) times, once for each chest being forced (or equivalently, excluded), resulting in a time complexity of \(O(N^2 M)\). Given the constraints \(N \leq 1{,}000, M \leq 3{,}000\), this would exceed the time limit (TLE).

To solve this, we use a technique called “DP from both directions (prefix and suffix DP).” When treasure chest \(i\) is selected, the remaining chests are divided into two groups: “chests \(1\) through \(i-1\)” and “chests \(i+1\) through \(N\).” By precomputing a DP table built by adding items from the front and another DP table built by adding items from the back, we can efficiently compute the maximum value when chest \(i\) is selected.

Algorithm

1. Prefix DP (dp_pref) Define dp_pref[i][w] as “the maximum value obtainable by selecting from chests \(1\) through \(i\) such that the total weight is at most \(w\).” Compute this the same way as standard knapsack DP.
2. Suffix DP (dp_suff) Define dp_suff[i][w] as “the maximum value obtainable by selecting from chests \(i\) through \(N\) such that the total weight is at most \(w\).” Compute this similarly, but from back to front.
3. Overall Maximum Value The maximum value considering all treasure chests, MAX_V, is dp_pref[N][M].
4. 判定 for Each Treasure Chest Suppose treasure chest \(i\) is necessarily selected. This consumes weight \(A_i\) and gains value \(B_i\). The remaining capacity is \(rem\_w = M - A_i\). We distribute this remaining capacity between the prefix chests and suffix chests. If we allocate weight \(w\) to the prefix side, we can allocate weight \(rem\_w - w\) to the suffix side. Therefore, the maximum value including chest \(i\) is given by: $\( \max_{0 \leq w \leq rem\_w} (dp\_pref[i-1][w] + dp\_suff[i+1][rem\_w - w]) + B_i \)$ If this value equals MAX_V, output Yes; if it is smaller, output No.

Complexity

• Time complexity: \(O(NM)\)
  • Building the prefix DP and suffix DP each takes \(O(NM)\).
  • For the determination of each treasure chest, trying all capacity distributions takes \(O(M)\), so the total is \(O(NM)\).
• Space complexity: \(O(NM)\)
  • We maintain two DP tables with \((N+2) \times (M+1)\) states, using \(O(NM)\) memory.

Implementation Notes

• In scripting languages such as Python, execution time can be tight when there are many nested loops. For the \(\max\) computation in each chest’s determination, we use operator.add and map to perform element-wise addition of list slices (pref[:rem_w+1] and suff[rem_w::-1]) in a single batch at the C language level, achieving speedup.

• suff[rem_w::-1] is a slice operation that retrieves the array in reverse order from index rem_w down to \(0\). This allows us to compute the sum of pairs \((w, rem\_w - w)\) concisely and efficiently without writing explicit loops.

  Source Code

import sys
import operator

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    A = [0] * (N + 1)
    B = [0] * (N + 1)
    
    idx = 2
    for i in range(1, N + 1):
        A[i] = int(input_data[idx])
        B[i] = int(input_data[idx+1])
        idx += 2
        
    dp_pref = [[0] * (M + 1) for _ in range(N + 2)]
    for i in range(1, N + 1):
        w_i = A[i]
        v_i = B[i]
        prev = dp_pref[i-1]
        curr = prev[:]
        for w in range(w_i, M + 1):
            val = prev[w-w_i] + v_i
            if val > curr[w]:
                curr[w] = val
        dp_pref[i] = curr
        
    dp_suff = [[0] * (M + 1) for _ in range(N + 2)]
    for i in range(N, 0, -1):
        w_i = A[i]
        v_i = B[i]
        nxt = dp_suff[i+1]
        curr = nxt[:]
        for w in range(w_i, M + 1):
            val = nxt[w-w_i] + v_i
            if val > curr[w]:
                curr[w] = val
        dp_suff[i] = curr
        
    MAX_V = dp_pref[N][M]
    
    ans = []
    for i in range(1, N + 1):
        w_i = A[i]
        v_i = B[i]
        rem_w = M - w_i
        if rem_w < 0:
            ans.append("No")
            continue
            
        pref = dp_pref[i-1]
        suff = dp_suff[i+1]
        
        max_val = max(map(operator.add, pref[:rem_w+1], suff[rem_w::-1])) + v_i
        
        if max_val == MAX_V:
            ans.append("Yes")
        else:
            ans.append("No")
            
    sys.stdout.write('\n'.join(ans) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.