Overview

This problem asks you to process \(N\) orders sequentially and produce/deliver products only when the inventory of all \(M\) types of parts is sufficient, then determine the number of orders that were actually delivered.

Analysis

Key Insight: The Bottleneck is the “Part with the Least Inventory”

To produce \(A_i\) products, every type of part must have at least \(A_i\) units available. When an order is processed, all parts decrease by the same amount (\(A_i\) units). In other words, each part’s inventory decreases uniformly while maintaining the “difference from the initial inventory.”

Let’s consider a concrete example. When \(M = 3\) and the initial inventory is \(B = [10, 7, 15]\):

• Whether to accept an order is determined by whether all parts have at least \(A_i\) units.
• Since all parts decrease by the same amount, the part with the smallest inventory is always the constraint.
• The minimum initial inventory is \(\min(B) = 7\).

After processing some orders, the inventory of each part becomes \([10 - S, 7 - S, 15 - S]\) (where \(S\) is the cumulative production count). Whether the next order of \(A_i\) products can be fulfilled is determined by whether the minimum value satisfies \(7 - S \geq A_i\).

Problem with the Naive Approach

Checking all \(M\) types of parts for each order results in \(O(N \times M)\), which may TLE when \(N, M\) are up to \(5 \times 10^5\).

Solution

From the above analysis, there is no need to manage \(M\) types of parts individually — it suffices to keep track of only \(\min(B)\). We can manage the remaining inventory (the bottleneck part’s inventory) with a single variable and process each order in \(O(1)\).

Algorithm

1. Compute the minimum initial inventory \(\text{remaining} = \min(B_1, B_2, \ldots, B_M)\).
2. Process orders in order \(i = 1, 2, \ldots, N\):
   • If \(\text{remaining} \geq A_i\), the order can be delivered. Subtract \(A_i\) from \(\text{remaining}\) and increment the count by \(1\).
   • If \(\text{remaining} < A_i\), the order is cancelled. Do nothing.
3. Output the final count.

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(M)\) for computing \(\min(B)\), \(O(N)\) for processing orders
• Space complexity: \(O(N + M)\)
  • Required for reading input (if only the minimum inventory value is stored, \(O(1)\) suffices)

Implementation Notes

• Fast input: Since \(N + M\) can be as large as \(5 \times 10^5\), we use sys.stdin.buffer.read() to read all input at once, reducing input overhead.

• Integer overflow: Although \(A_i, B_j\) can be up to \(10^9\), Python uses arbitrary-precision integers, so there is no concern about overflow.

• The core idea is simple: Once you notice the structure that all parts decrease by the same amount, the problem reduces to a simple one: “Treat the minimum initial inventory as a budget and greedily process orders from the beginning.”

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    A = [int(input_data[idx + i]) for i in range(N)]; idx += N
    B = [int(input_data[idx + i]) for i in range(M)]; idx += M
    
    min_B = min(B)
    count = 0
    remaining = min_B
    
    for i in range(N):
        if remaining >= A[i]:
            remaining -= A[i]
            count += 1
    
    print(count)

if __name__ == '__main__':
    main()

---

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