Overview

This problem involves a factory that combines \(M\) types of parts to make products, processing \(N\) orders sequentially. Since each order consumes the same quantity of every part type, the problem can be solved efficiently by tracking only the transition of the part with the lowest stock.

Analysis

Naive Approach and Its Limitations

What happens if we naively process each order \(i\) by “checking whether all \(M\) types of parts have stock at least \(A_i\), and if so, reducing the stock of all \(M\) types”? In this case, each order requires up to \(M\) checks and updates, resulting in an overall time complexity of \(O(N \times M)\). The constraints state \(N, M \leq 5 \times 10^5\) with \(N+M \leq 5 \times 10^5\), but in the worst case (e.g., \(N=2.5 \times 10^5, M=2.5 \times 10^5\)), the number of operations exceeds \(6 \times 10^{10}\), which will not fit within the time limit.

Key Insight: Focus on the Minimum Stock

The crux of this problem is that “every part decreases at exactly the same time and by exactly the same amount.”

1. The condition to process an order is “all parts have stock \(B_j \geq A_i\)”, which can be rephrased as “the minimum stock \(\min(B_1, \dots, B_M) \geq A_i\)”.
2. When processing an order and reducing stock, we subtract the same value \(A_i\) from every \(B_j\). The relative ordering of stock quantities among parts does not change. In other words, the part that initially had the minimum stock will continue to have the minimum stock (including ties) throughout the entire process.

Therefore, there is no need to manage the stock of each individual part — it is sufficient to manage just a single variable: “the minimum stock among all parts”.

Algorithm

1. Compute the initial minimum stock: Find the minimum value among the given initial stocks \(B_1, B_2, \ldots, B_M\) and store it as min_stock.
2. Simulate the orders: For each order \(A_i\) (\(i = 1, \ldots, N\)), perform the following in sequence:
   • If min_stock >= A_i:
     • The order succeeds. Subtract \(A_i\) from min_stock and increment the success count by 1.
   • Otherwise:
     • The order is cancelled due to insufficient stock. Do nothing.
3. Output the result: Output the final success count.

Complexity

• Time complexity: \(O(N + M)\)
  • Finding the minimum value among all initial stocks takes \(O(M)\).
  • The loop checking each order once takes \(O(N)\).
  • Overall, the processing time is proportional to the input size.
• Space complexity: \(O(N + M)\)
  • This is the memory required to store the input values \(A_i\) and \(B_j\) in lists.

Implementation Notes

• Fast I/O: Since \(N + M\) can be as large as \(5 \times 10^5\), repeatedly calling Python’s standard input() may cause the input alone to take too much time. It is efficient to read all input at once using sys.stdin.read().split() or similar methods.

• Obtaining the minimum value: By applying Python’s min() function to a list or iterator, the minimum value can be obtained efficiently in \(O(M)\).

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # 大規模な入力（N, M <= 5 * 10^5）を効率的に処理するために sys.stdin.read().split() を使用
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 注文数 N と部品の種類数 M を取得
    n = int(input_data[0])
    m = int(input_data[1])
    
    # 全ての部品の在庫は、注文が成功するたびに同じ量（Ai）だけ減少する。
    # したがって、ある注文を処理できるかどうかは、その時点での「全部品の中の最小在庫数」に依存する。
    # 初めに最小在庫であった部品は、減少量がいずれの部品も等しいため、常に最小在庫（の一つ）であり続ける。
    # そのため、各部品の在庫を個別に管理する必要はなく、最小在庫の推移だけを追えばよい。
    
    # 部品の初期在庫 B_j は input_data のインデックス n+2 から n+m+1 に格納されている。
    # map関数とmin関数を用いて、初期在庫の最小値を効率的に求める。
    # スライス input_data[n+2 : n+m+2] は B_1 から B_M までの要素をカバーする。
    min_stock = min(map(int, input_data[n + 2 : n + m + 2]))
    
    # 実際に納品できた注文の件数をカウントする変数
    successful_orders = 0
    
    # 注文 A_i を順番に処理する。
    # 注文 A_i の必要数は input_data のインデックス 2 から n+1 に格納されている。
    for i in range(2, n + 2):
        required_amount = int(input_data[i])
        
        # 現在の最小在庫が必要数以上であれば、注文を処理できる
        if min_stock >= required_amount:
            # 注文を処理し、最小在庫を必要数分だけ減らす
            min_stock -= required_amount
            # 納品件数をインクリメント
            successful_orders += 1
        else:
            # 在庫が不足している場合、この注文はキャンセルされ、在庫は変化しない
            pass
            
    # 最終的に納品できた注文の件数を出力
    print(successful_orders)

if __name__ == '__main__':
    main()

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