Overview

This problem asks us to find the maximum number of boxes that can be stacked from \(N\) cardboard boxes while respecting the weight capacity limits. We need to optimize both the selection of boxes and the stacking order.

Analysis

Finding the Optimal Stacking Order

First, let’s consider “given a fixed set of boxes, in what order should they be stacked?”

The condition for box \(i\) not to be crushed is: “the total weight of boxes above box \(i\) \(\leq D_i\).” If we let \(U_i\) denote the weight above where box \(i\) is placed, then \(U_i \leq D_i\) must hold.

We use an Exchange Argument on two adjacent boxes. Consider a situation where box \(B\) (weight \(W_B\), capacity \(D_B\)) is on top of box \(A\) (weight \(W_A\), capacity \(D_A\)). The load on box \(A\) is \(W_B + X\) (where \(X\) is the weight above \(B\)), and the load on box \(B\) is \(X\).

• In this order (\(A\) on bottom): \(W_B + X \leq D_A\) and \(X \leq D_B\)
• In reverse order (\(B\) on bottom): \(W_A + X \leq D_B\) and \(X \leq D_A\)

Analyzing the condition under which placing \(A\) on the bottom is more advantageous, we find that \(A\) should be placed below when \(W_A + D_A \geq W_B + D_B\). In other words, boxes with larger \(W_i + D_i\) should be placed lower (sort in ascending order of \(W_i + D_i\) and arrange from top to bottom = arrange from top in ascending order). This is the optimal strategy.

Issues with the Naive Approach

Exhaustively searching all subsets of \(N\) boxes would take \(O(2^N)\), which is far too slow for \(N \leq 2 \times 10^5\).

Solving with a Greedy Approach

Sort the boxes in ascending order of \(W_i + D_i\) and examine them in order. The \(k\)-th box in sorted order has the largest \(W+D\) among all currently selected boxes, so it goes at the very bottom. The constraint for the bottom box is: “total weight of selected boxes \(\leq W_k + D_k\)” (the weight on top = total \(- W_k \leq D_k\), i.e., total \(\leq W_k + D_k\)). As long as this constraint is satisfied, boxes with smaller \(W+D\) have even more capacity margin, so their constraints are automatically satisfied.

When the constraint is exceeded, removing the heaviest box among those selected so far maximally reduces the total weight while minimizing the loss in count.

Algorithm

1. Sort the boxes in ascending order of \(W_i + D_i\).
2. Prepare a max-heap (to manage the weights of selected boxes) and a variable \(\text{total\_w}\) for the total weight of selected boxes.
3. Process each box \((W_i, D_i)\) in sorted order:
   • Add the box to the heap and add \(W_i\) to \(\text{total\_w}\).
   • If \(\text{total\_w} > W_i + D_i\), extract the heaviest box from the heap and subtract its weight from \(\text{total\_w}\).
4. The final number of elements in the heap is the answer.

Concrete example: For boxes \((W=3, D=1), (W=1, D=3), (W=2, D=2)\), \(W+D\) is \(4, 4, 4\). Add them in order, and whenever the total exceeds \(W+D\), remove the heaviest box.

Complexity

• Time complexity: \(O(N \log N)\) (sorting and heap operations)
• Space complexity: \(O(N)\) (heap storage)

Implementation Notes

• Python’s heapq is a min-heap, so store weights with negated signs to use it as a max-heap.

• Check for constraint violations immediately after adding a box; when violated, removing just one heaviest box is sufficient. If the box just added is the heaviest, it may be the one removed (corresponding to the case where it’s better not to select that box).

• The key insight is that by sorting in ascending order of \(W+D\), the box currently being processed is always the bottleneck (at the very bottom), so we only need to check this box’s constraint.

  Source Code

import heapq

def solve():
    import sys
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    
    boxes = []
    for i in range(N):
        w = int(input_data[idx]); idx += 1
        d = int(input_data[idx]); idx += 1
        boxes.append((w, d))
    
    # Greedy approach:
    # Sort by W_i + D_i in ascending order.
    # This is the classic "scheduling" style greedy for stacking problems.
    # 
    # Key insight: If we place boxes in order of increasing (W_i + D_i) from bottom to top,
    # this is optimal. W_i + D_i represents the maximum total weight (including itself)
    # that can be at or below this box's position.
    #
    # We greedily pick boxes sorted by W+D ascending. We maintain a max-heap of weights
    # of selected boxes. For each box, we add it. If the current total weight minus
    # the top box's own weight exceeds its durability (i.e., the stack isn't feasible),
    # we check if removing the heaviest box helps - effectively we simulate and remove
    # the heaviest selected box if it improves things.
    #
    # Actually, let me think more carefully. The condition for a valid stacking when
    # sorted by W+D ascending (placed bottom to top) is:
    # For box at position k (0-indexed from bottom), the weight above it = sum of W of boxes above.
    # 
    # Greedy: sort by W+D ascending. Process in this order (bottom to top placement).
    # Maintain selected set. Add current box. If total weight of selected exceeds
    # current box's W+D (since current box is the one with largest W+D so far, and
    # the total weight on top of it is totalW - W_current, we need totalW - W_current <= D_current,
    # i.e., totalW <= W_current + D_current), then we need to remove some box to reduce total weight.
    # Remove the heaviest box from selected set.
    
    boxes.sort(key=lambda x: x[0] + x[1])
    
    max_heap = []  # max-heap using negative values
    total_w = 0
    
    for w, d in boxes:
        heapq.heappush(max_heap, -w)
        total_w += w
        
        # Check if current box (which has the largest W+D so far) is okay
        # All boxes below have W+D <= current W+D, so if current is satisfied, all are.
        # Condition: total_w <= w + d  (i.e., weight above current = total_w - w <= d)
        # But wait, current box is placed at bottom? No, sorted by W+D ascending means
        # the first processed box goes to bottom, last to top. So the current box is 
        # the topmost? No...
        # 
        # Actually when sorted by W+D ascending, the optimal arrangement places the 
        # box with smallest W+D at the top (it can bear the least total), and largest 
        # W+D at the bottom. Wait, let me reconsider.
        #
        # For the box with the largest W+D, it should be at the bottom because it can
        # handle the most weight above. So sort ascending = bottom to top means smallest
        # W+D at bottom, which seems wrong.
        #
        # The standard result: sort by W+D ascending, and the constraint for the i-th 
        # box in this sorted order (0-indexed) placed from bottom to top is that 
        # the sum of weights of boxes ABOVE it <= D_i. The critical constraint is 
        # actually on the last (topmost in terms of processing) = the box with largest W+D
        # being at the bottom. Hmm, I think the sort should give bottom = largest W+D.
        #
        # Let me just use the greedy: sort by W+D ascending, and for each box in order,
        # add it, and if total_w > (w+d) of current box, remove heaviest. This is a 
        # known correct greedy for this type of problem.
        
        if total_w > w + d:
            heaviest = -heapq.heappop(max_heap)
            total_w -= heaviest
    
    print(len(max_heap))

solve()

---

This editorial was generated by claude4.6opus-thinking.