Overview

There are multiple counters, each with a maximum number of applications it can process. Applications arrive in order, and if there is availability at the requested counter, the application is accepted. Determine how many applications are ultimately accepted.

Analysis

In this problem, applications are processed in the order they arrive, so we can think of it as the counter slots being filled on a first-come, first-served basis. When an application arrives, if the requested counter still has remaining processing capacity, the application is accepted; otherwise, it is rejected.

A straightforward approach is to check the remaining processing capacity of the requested counter each time and decrement it by one. This can be processed in \(O(1)\) per application, so it is sufficiently fast overall.

However, care must be taken with input/output handling. Calling Python’s input() line by line is slow, so it is necessary to read all input at once for speedup. Also, note that counter numbers are 1-indexed, so you need to convert to 0-indexed when accessing the array.

Algorithm

1. Read all input efficiently (using sys.stdin.read).
2. Maintain the remaining processing capacity of each counter as a list counters (initialized with \(C_i\)).
3. Process applications in order:
   • Get the requested counter number \(T_j\).
   • If counters[T_j - 1] is greater than 0, the application can be accepted:
     • Decrement counters[T_j - 1] by 1.
     • Increment the accepted count by 1.
4. Output the final accepted count.

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(N + M)\)

Implementation Notes

• Use sys.stdin.read for fast input reading.

• Since counter numbers are 1-indexed, use T - 1 when accessing the list.

• counters is a list that manages the remaining processing capacity of each counter.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    C = list(map(int, data[2:2+N]))
    
    # 各窓口の残り処理可能件数を管理
    counters = C[:]
    
    accepted = 0
    idx = 2 + N
    for _ in range(M):
        T = int(data[idx])
        idx += 1
        if counters[T - 1] > 0:
            counters[T - 1] -= 1
            accepted += 1
    print(accepted)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.