Overview

This is a problem where, in the 0-1 knapsack problem, we need to determine whether each item can possibly be included in an optimal solution.

Analysis

Essence of the Problem

In the standard knapsack problem, we simply find the “maximum value” and we’re done. However, in this problem, we need to determine “whether each item can be part of some optimal solution.”

Naive Approach and Its Issues

For each item \(k\), we can compute “the maximum value when item \(k\) is necessarily selected” and check whether it matches the overall maximum value.

However, naively recomputing the DP each time results in \(O(N^2 M)\), which may TLE under the constraints (\(N \leq 1000, M \leq 3000\)).

Solution: Splitting Using Prefix and Suffix

When considering the case where item \(k\) is necessarily selected, the remaining items can be divided into “items before \(k\) (\(0\) to \(k-1\))” and “items after \(k\) (\(k+1\) to \(N-1\)).”

Therefore, we precompute: - prefix[i][w]: the maximum value when selecting from items \(0\) to \(i-1\) with weight exactly \(w\) - suffix[i][w]: the maximum value when selecting from items \(i\) to \(N-1\) with weight exactly \(w\)

Then, the maximum value when item \(k\) (weight \(a\), value \(b\)) is necessarily selected is: $\(\max_{w_1 + a + w_2 \leq M} \left( \text{prefix}[k][w_1] + b + \text{suffix}[k+1][w_2] \right)\)$

Further Optimization

In the above computation, iterating over both \(w_1\) and \(w_2\) in a double loop costs \(O(M^2)\).

To address this, we precompute suffix_max[i][w] = \(\max_{0 \leq j \leq w} \text{suffix}[i][j]\) (prefix maximum over weights).

Then, for a fixed \(w_1\), the maximum suffix value satisfying \(w_2 \leq M - a - w_1\) can be retrieved in \(O(1)\).

Algorithm

1. Compute prefix DP: Process items from front to back, recording the maximum value for each weight
2. Compute suffix DP: Process items from back to front, recording the maximum value for each weight
3. Compute suffix_max: Calculate the cumulative maximum of suffix
4. Find the overall maximum value: The maximum value of prefix[N]
5. Determine for each item:
   • Compute the maximum value when item \(k\) is necessarily selected
   • If it matches the overall maximum value, output Yes; otherwise, output No

Complexity

• Time complexity: \(O(NM)\)
  • Computing prefix and suffix: \(O(NM)\) each
  • Computing suffix_max: \(O(NM)\)
  • Checking each item: \(O(M)\) × \(N\) items = \(O(NM)\)
• Space complexity: \(O(NM)\)
  • Arrays for prefix, suffix, and suffix_max

Implementation Details

1. Handling -INF: Negative infinity is used to represent “this weight is unachievable.” Initially, only prefix[0][0] = suffix[N][0] = 0 are achievable.

2. “Exactly w” DP: In the standard knapsack, we maximize over “at most w,” but in this problem, since we combine prefix and suffix, we need to compute for “exactly w.”

3. Using cumulative maximum: By using suffix_max, we eliminate the loop over \(w_2\), keeping the check for each item at \(O(M)\).

4. Be careful with weight limits: Since item \(k\) is selected, the maximum weight usable on the prefix side is at most \(M - a\) (due to the constraint \(w_1 + a + w_2 \leq M\)).

   Source Code

def solve():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    items = []
    for _ in range(N):
        a, b = map(int, input().split())
        items.append((a, b))
    
    INF = float('inf')
    
    # prefix[i][w] = items[0..i-1]から重さちょうどwで得られる最大価値（不可能なら-INF）
    # suffix[i][w] = items[i..N-1]から重さちょうどwで得られる最大価値（不可能なら-INF）
    
    # prefixの計算
    prefix = [[-INF] * (M + 1) for _ in range(N + 1)]
    prefix[0][0] = 0
    for i in range(N):
        a, b = items[i]
        for w in range(M + 1):
            if prefix[i][w] == -INF:
                continue
            # 選ばない
            if prefix[i + 1][w] < prefix[i][w]:
                prefix[i + 1][w] = prefix[i][w]
            # 選ぶ
            if w + a <= M:
                if prefix[i + 1][w + a] < prefix[i][w] + b:
                    prefix[i + 1][w + a] = prefix[i][w] + b
    
    # suffixの計算
    suffix = [[-INF] * (M + 1) for _ in range(N + 1)]
    suffix[N][0] = 0
    for i in range(N - 1, -1, -1):
        a, b = items[i]
        for w in range(M + 1):
            if suffix[i + 1][w] == -INF:
                continue
            # 選ばない
            if suffix[i][w] < suffix[i + 1][w]:
                suffix[i][w] = suffix[i + 1][w]
            # 選ぶ
            if w + a <= M:
                if suffix[i][w + a] < suffix[i + 1][w] + b:
                    suffix[i][w + a] = suffix[i + 1][w] + b
    
    # 全体の最大価値
    max_value = max(prefix[N][w] for w in range(M + 1))
    
    # 各アイテムについて判定
    results = []
    for k in range(N):
        a, b = items[k]
        # items[k]を必ず選ぶ場合の最大価値
        # prefix[k][w1] + b + suffix[k+1][w2] where w1 + a + w2 <= M
        can_include = False
        for w1 in range(M + 1 - a):
            if prefix[k][w1] == -INF:
                continue
            # w1 + a + w2 <= M => w2 <= M - a - w1
            max_w2 = M - a - w1
            # suffix[k+1][0..max_w2]の最大値が必要
            # これを高速化するために、suffix_maxを事前計算
            for w2 in range(max_w2 + 1):
                if suffix[k + 1][w2] == -INF:
                    continue
                total = prefix[k][w1] + b + suffix[k + 1][w2]
                if total == max_value:
                    can_include = True
                    break
            if can_include:
                break
        
        results.append("Yes" if can_include else "No")
    
    print('\n'.join(results))

# 高速化版
def solve_optimized():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    items = []
    for _ in range(N):
        a, b = map(int, input().split())
        items.append((a, b))
    
    INF = float('inf')
    
    # prefixの計算
    prefix = [[-INF] * (M + 1) for _ in range(N + 1)]
    prefix[0][0] = 0
    for i in range(N):
        a, b = items[i]
        for w in range(M + 1):
            if prefix[i][w] == -INF:
                continue
            if prefix[i + 1][w] < prefix[i][w]:
                prefix[i + 1][w] = prefix[i][w]
            if w + a <= M:
                if prefix[i + 1][w + a] < prefix[i][w] + b:
                    prefix[i + 1][w + a] = prefix[i][w] + b
    
    # suffixの計算
    suffix = [[-INF] * (M + 1) for _ in range(N + 1)]
    suffix[N][0] = 0
    for i in range(N - 1, -1, -1):
        a, b = items[i]
        for w in range(M + 1):
            if suffix[i + 1][w] == -INF:
                continue
            if suffix[i][w] < suffix[i + 1][w]:
                suffix[i][w] = suffix[i + 1][w]
            if w + a <= M:
                if suffix[i][w + a] < suffix[i + 1][w] + b:
                    suffix[i][w + a] = suffix[i + 1][w] + b
    
    # suffix_max[i][w] = max(suffix[i][0], suffix[i][1], ..., suffix[i][w])
    suffix_max = [[-INF] * (M + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        curr_max = -INF
        for w in range(M + 1):
            if suffix[i][w] > curr_max:
                curr_max = suffix[i][w]
            suffix_max[i][w] = curr_max
    
    # 全体の最大価値
    max_value = max(prefix[N][w] for w in range(M + 1))
    
    # 各アイテムについて判定
    results = []
    for k in range(N):
        a, b = items[k]
        can_include = False
        for w1 in range(M + 1 - a):
            if prefix[k][w1] == -INF:
                continue
            max_w2 = M - a - w1
            best_suffix = suffix_max[k + 1][max_w2]
            if best_suffix == -INF:
                continue
            total = prefix[k][w1] + b + best_suffix
            if total == max_value:
                can_include = True
                break
        
        results.append("Yes" if can_include else "No")
    
    print('\n'.join(results))

solve_optimized()

---

This editorial was generated by claude4.5opus.