Overview

For each day, count the number of applicants for each classroom. If the number is within capacity, all participate; if it exceeds capacity, no one participates. The problem asks for the total number of participants over all \(N\) days.

Analysis

Key Observation

The critical point of this problem is how overcapacity is handled. When capacity is exceeded, it’s not that “some people can’t get in” — rather, the lecture itself is canceled and no one can participate. Pay careful attention to this distinction.

For example, when a classroom’s capacity is 3: - 3 applicants → all 3 can participate (✅ within capacity) - 5 applicants → 0 can participate (❌ canceled due to overcapacity)

Each Day is Independent

There is no need to consider cumulative effects across days. Everything resets daily, and the decision is based solely on that day’s number of applicants.

Is a Naive Approach Sufficient?

For each day, we simply tally the preferred classrooms of visitors and compare each classroom’s count against its capacity. Since the constraint guarantees \(\sum K_i \leq 2 \times 10^5\), processing each visitor one by one is fast enough. No special algorithm is needed — the essence of this problem is correctly performing the counting (tallying).

Algorithm

1. Read the classroom capacities \(C_1, C_2, \ldots, C_M\).
2. For each day \(i = 1, 2, \ldots, N\):
   • Read the preferred classrooms of the \(K_i\) visitors for that day.
   • Count the number of applicants per classroom (using Counter or a hash map).
   • For each classroom, if the number of applicants \(\leq\) capacity, add that count to the answer.
3. Output the total over all \(N\) days.

Concrete Example

With 2 classrooms having capacities \(C_1 = 3, C_2 = 2\):

• Day 1: Preferences are [1, 1, 2, 1] → Classroom 1 has 3 people (\(3 \leq 3\) ✅), Classroom 2 has 1 person (\(1 \leq 2\) ✅) → +4 people
• Day 2: Preferences are [2, 2, 2] → Classroom 2 has 3 people (\(3 > 2\) ❌, canceled) → +0 people

Total: 4 people

Complexity

• Time complexity: \(O(N + \sum_{i=1}^{N} K_i + M)\)
  • Each visitor is processed once, and tallying is done per classroom per day, so the cost is proportional to the total number of visitors. \(M\) accounts for reading the capacities.
• Space complexity: \(O(M + \max_i K_i)\)
  • For the capacity array of size \(M\) and the per-day counter (at most \(K_i\) distinct entries).

Implementation Tips

• Fast input: By reading all input at once with sys.stdin.buffer.read() and splitting with split(), Python can process the data quickly. Calling input() line by line can be slow.

• Using Counter: Python’s collections.Counter allows concise counting of applicants per classroom.

• Classroom index: Since classroom numbers are 1-indexed, the capacity array C is allocated with size \(M+1\) so that C[j] (\(j = 1, \ldots, M\)) can be accessed directly.

  Source Code

import sys
from collections import Counter

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
    C = [0] * (M + 1)
    for j in range(1, M + 1):
        C[j] = int(input_data[idx]); idx += 1
    
    total = 0
    for i in range(N):
        K = int(input_data[idx]); idx += 1
        cnt = Counter()
        for k in range(K):
            p = int(input_data[idx]); idx += 1
            cnt[p] += 1
        for room, count in cnt.items():
            if count <= C[room]:
                total += count
    
    print(total)

main()

---

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