Overview

Given \(N\) cardboard boxes, the problem asks to stack as many boxes as possible while respecting the load capacity constraint (the total weight of all boxes above a given box \(\leq\) its load capacity). This can be solved using a greedy approach with a priority queue (heap), after determining the optimal order in which to stack the boxes.

Analysis

1. Optimizing the Stacking Order

First, consider the most advantageous order to stack a chosen set of boxes \(S\). Suppose two boxes \(i\) and \(j\) are stacked adjacent to each other (\(i\) on top, \(j\) on the bottom). The conditions that must hold are: - For box \(i\): (total weight above box \(i\)) \(\leq D_i\) - For box \(j\): (total weight above box \(i\)) \(+ W_i \leq D_j\)

When we determine the condition under which swapping \(i\) and \(j\) does not make things less restrictive (i.e., there is no benefit to swapping), we derive the relation \(W_i + D_i \leq W_j + D_j\). In other words, placing boxes with a smaller sum of weight \(W\) and load capacity \(D\) higher, and those with a larger sum lower, yields the most stable stacking arrangement.

2. Choosing Which Boxes to Select (Greedy)

Sort the boxes in ascending order of \(W_i + D_i\) and consider stacking them from the top down. However, simply using a “stack it if you can” approach may cause issues where a heavy box prevents future boxes from being stacked.

Therefore, we use the following strategy: - Let current_total_weight be the current total weight of stacked boxes. - Check whether box \(i\) can be placed at the bottom (current_total_weight <= D_i). - If it can be placed: Stack it as is. - If it cannot be placed: Compare the heaviest box among the currently stacked boxes with the current box \(i\). If the current box is lighter, discard the heaviest box and replace it with the current box.

Even though this replacement does not change the total number of boxes, it reduces the total weight, increasing the possibility of stacking additional boxes in the future. Moreover, due to the sorting order, this replacement is always safe to perform.

Algorithm

1. Sort each cardboard box in ascending order of \(W_i + D_i\).
2. Prepare a max-heap (in Python, use heapq with negated values) to manage the weights of the currently stacked boxes.
3. Examine each sorted box one by one:
   • If current total weight <= D_i:
     • Add box \(i\) to the heap and add \(W_i\) to the total weight.
   • Otherwise (cannot stack), if maximum weight in the heap > W_i:
     • Remove the box with the maximum weight and add \(W_i\) to the heap instead.
     • Update the total weight (-maximum weight + W_i).
4. The final size of the heap is the maximum number of boxes that can be stacked.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the boxes takes \(O(N \log N)\).
  • Each box undergoes at most one heap operation (insertion or deletion), so the overall cost is \(O(N \log N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the input data and the heap.

Implementation Notes

• Python’s heapq is a min-heap (extracts the smallest value), so to use it as a max-heap, weights must be stored as negative values.

• Since \(N\) can be as large as \(2 \times 10^5\), it is efficient to read input quickly using sys.stdin.read().split().

  Source Code

import sys
import heapq

def solve():
    # 高速な入出力のために、すべての入力を一度に読み込みます。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 段ボール箱の個数 N
    N = int(input_data[0])
    
    # 各段ボール箱の重さ W と耐荷重 D を取得します。
    # 重さ W と耐荷重 D の和 (W + D) を「期限」と見なすことができます。
    boxes = []
    for i in range(N):
        w = int(input_data[2*i + 1])
        d = int(input_data[2*i + 2])
        boxes.append((w, d))
    
    # 段ボール箱を (W + D) の昇順でソートします。
    # これは、ある集合の箱を積むとき、(W + D) が小さい箱ほど上に、
    # 大きい箱ほど下に配置するのが最適（条件を満たしやすい）だからです。
    boxes.sort(key=lambda x: x[0] + x[1])
    
    # 現在選んでいる段ボール箱の重さのリストを保持するための最大ヒープ。
    # Pythonのheapqは最小ヒープなので、重さを負の値にして格納します。
    pq = []
    # 現在積み上げている段ボール箱の重さの合計。
    current_total_weight = 0
    
    for w, d in boxes:
        # 現在の合計重さが、新しく追加しようとしている段ボール箱の耐荷重以下であれば、
        # その箱を一番下に置くことができます。
        if current_total_weight <= d:
            heapq.heappush(pq, -w)
            current_total_weight += w
        # もし追加できない場合でも、現在選んでいる箱の中に、
        # 今見ている箱よりも重いものがあれば、それを差し替えることで
        # 合計重さを減らすことができます（箱の数は変わりません）。
        # (W + D) の昇順で処理しているため、差し替えても条件は維持されます。
        elif pq and -pq[0] > w:
            # ヒープの最小値（負の重さの最小値 ＝ 実際の最大重さ）を取り出し、
            # 新しい箱の重さと入れ替えます。
            heaviest_w_neg = heapq.heapreplace(pq, -w)
            current_total_weight += heaviest_w_neg + w
            
    # 選ばれた段ボール箱の個数（ヒープのサイズ）を出力します。
    print(len(pq))

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.