Overview

Given each box’s “weight \(W_i\)” and “load capacity \(D_i\)”, we want to find the maximum number of boxes that can be stacked vertically without any box being crushed. The conclusion is that we can find the maximum count using a greedy algorithm that processes boxes in a specific order, either “adding a box / or discarding the heaviest box if it doesn’t fit.”

Analysis

Key Observation: The condition depends on the “total weight above”

When boxes are arranged from bottom to top, the condition for box \(i\) not being crushed is:

• “Total weight of all boxes above it” \(\le D_i\)

Changing the perspective slightly, if we let \(T\) denote the total weight from “all boxes above + the box itself”, then:

• \(T \le W_i + D_i\)

Here, \(W_i + D_i\) represents “the maximum total weight (including itself) that the box can support,” so we call this the strength.

In other words, when looking from bottom to top, it’s OK as long as “the accumulated total weight \(T\) does not exceed each box’s strength \(S_i = W_i + D_i\).”

Why naive approaches are difficult

• We need to optimize both which boxes to select (subset) and in what order to stack them (permutation).
• Exhaustive search is obviously infeasible, and DP won’t work either since the “total weight” can be up to \(10^9\), making weight-based DP impractical.
• Since \(N \le 2 \times 10^5\), methods like \(O(N^2)\) are also too slow.

Solution Strategy: Fix the ordering and greedily maximize the count

Consider the boxes sorted in ascending order of strength \(S_i = W_i + D_i\). Processing them in this order:

• Let \(T\) be the total weight of currently selected boxes
• If adding a new box (with strength \(S\), weight \(W\)) satisfies \(T + W \le S\), then it can safely be stacked “somewhere” in the pile

If \(T + W > S\), then “without discarding something from the current set, it’s impossible to have a valid stacking that includes a box with this strength \(S\) near the bottom.” Since we want to maximize the count, discarding the heaviest box — which reduces the total weight the most — is optimal.

By repeating this “add, and if it fails, discard the heaviest box” process, at each step we maintain: - The “maximum-count set” achievable using only the boxes seen so far.

Algorithm

1. For each box, compute the strength \(S_i = W_i + D_i\) and create pairs \((S_i, W_i)\).
2. Sort by \((S_i)\) in ascending order.
3. Prepare total (the total weight of currently selected boxes) and a heap to manage the weights of selected boxes.
   • Since we want to quickly extract the “heaviest box,” we need a max-heap (in Python, we use negative values to simulate this with the min-heap from heapq).
4. Process each box in sorted order:
   • Tentatively add the box: total += w, push -w onto the heap
   • If total > S, the condition is violated, so discard the “heaviest box” from the heap (subtract its weight from total)
5. The number of elements remaining in the heap at the end is the answer.

Intuitive Example

Boxes with small strength (\(W + D\) is small) “can’t support much on top,” making them hard to place at the bottom, so they need to be processed first to satisfy the conditions. When the total weight exceeds the limit midway, discarding the heaviest box reduces the total weight the most, making it easier to keep more boxes — that’s the key insight.

Complexity

• Time complexity: \(O(N \log N)\) (sorting \(O(N \log N)\) + heap operations \(O(\log N)\) per box)
• Space complexity: \(O(N)\) (box array and heap)

Implementation Notes

• The strength is \(S_i = W_i + D_i\). Sorting in ascending order by this value is the core idea.

• Python’s heapq is a min-heap, so to extract the maximum value (heaviest box), we insert -w.

• Note that when total > S, we only need to discard exactly one box: Since we just added one box that caused the violation, discarding the single heaviest box reduces total by the largest possible amount, which is optimal for subsequent processing.

  Source Code

import sys
import heapq

def main():
    input = sys.stdin.readline
    N = int(input())
    boxes = []
    for _ in range(N):
        w, d = map(int, input().split())
        boxes.append((w + d, w))  # (strength, weight)

    boxes.sort()  # by strength ascending

    total = 0
    heap = []  # max-heap by weight via negative
    for s, w in boxes:
        total += w
        heapq.heappush(heap, -w)
        if total > s:
            total += heapq.heappop(heap)  # subtract largest weight

    print(len(heap))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.