Overview

For each day, count the “number of applicants per classroom,” and accumulate the number of people who could participate for classrooms that are within capacity.

Analysis

The key observation is that whether a lecture is canceled depends solely on “the number of applicants for that classroom on that day.” Specifically, if the number of applicants for classroom \(j\) on a given day is \(x\), then:

• If \(x \le C_j\), all \(x\) applicants for that classroom can participate
• If \(x > C_j\), 0 people from that classroom can participate (all are denied)

Therefore, if we can tally “classroom number \(\rightarrow\) number of applicants” for each day, we can compute the answer.

Naively counting the number of applicants for every classroom each day would require iterating over all \(M\) classrooms daily, resulting in worst-case \(O(NM)\) (\(10^5 \times 10^5\)), which is far too slow. However, in this problem \(\sum K_i \le 2 \times 10^5\), so by only counting classrooms that actually have applicants, we can process everything efficiently.

Example: If the requests on a given day are [1,1,3,3,3,5], it suffices to build {1:2, 3:3, 5:1}, and all other classrooms have “0 applicants” and don’t affect the result.

Algorithm

1. Store the classroom capacities \(C_1,\dots,C_M\) in an array (using 1-indexed makes it easy to correspond with classroom numbers).
2. For each day, do the following:
   1. Read the list of requested classrooms for that day, and count cnt[classroom] = number of applicants using a dictionary (associative array) cnt.
   2. For each classroom (room, v) in cnt:
      • If \(v \le C_{room}\), add ans += v
      • Otherwise, add nothing (the lecture is canceled, so 0 people)
3. Output the final ans.

With this approach, the counting of applicants only requires work proportional to the number of applicants.

Complexity

• Time complexity: \(O\!\left(\sum_{i=1}^{N} K_i\right)\) (Each request is counted once in the dictionary, and the number of classrooms checked is also bounded by \(\sum K_i\) in total)
• Space complexity: \(O(M + U)\) where \(U\) is “the number of distinct classrooms on that day,” which is at most \(K_i\). The capacity array uses \(O(M)\), and the per-day dictionary uses \(O(U)\).

Implementation Notes

• Since the input is large, reading all at once with something like sys.stdin.buffer.read().split() and converting to integers improves performance.

• The per-day tallying can be done concisely with dict (cnt[p] = cnt.get(p, 0) + 1).

• Using a 1-indexed capacity array C[1..M] allows direct use of classroom numbers from the input, reducing the chance of errors.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = map(int, data)
    it = iter(it)

    N = next(it)
    M = next(it)

    C = [0] * (M + 1)
    for j in range(1, M + 1):
        C[j] = next(it)

    ans = 0
    for _ in range(N):
        K = next(it)
        cnt = {}
        for _ in range(K):
            p = next(it)
            cnt[p] = cnt.get(p, 0) + 1
        for room, v in cnt.items():
            if v <= C[room]:
                ans += v

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.