Overview

Over \(N\) days, lectures are held in \(M\) classrooms. Each classroom has a capacity limit, and if the number of applicants on a given day exceeds the capacity, the lecture in that classroom is canceled for that day. The problem asks for the total number of people who actually attended lectures across all days.

Analysis

The key point in solving this problem is efficiently aggregating “how many people gathered in each classroom on each day.”

1. Naive Approach

If we check “how many people requested this classroom?” for all \(M\) classrooms every day, the computational complexity becomes \(O(N \times M)\). In this problem, \(N, M \le 10^5\), so in the worst case, approximately \(10^{10}\) operations would be needed, which exceeds the time limit.

2. Efficient Solution

In practice, not all classrooms have attendees every day. If we let \(K_i\) be the number of visitors on day \(i\), then the number of classrooms with applicants on that day is at most \(K_i\). Looking at the constraints, \(\sum K_i \le 2 \times 10^5\), meaning the total number of visitors across all days is sufficiently small.

Therefore, by only aggregating and checking classrooms that actually have applicants on each day, we can significantly reduce the computational complexity.

Algorithm

We proceed with the following steps:

1. Preparation: Store the capacity \(C_j\) of each classroom in an array (since classroom numbers start from \(1\), using 1-indexed management makes implementation smoother).
2. Processing each day:
   • Receive the list of classrooms requested by that day’s visitors.
   • Use a hash map (e.g., collections.Counter in Python) to count the number of applicants per classroom.
   • For each counted classroom (room_id), perform the following check:
     • If number of applicants <= C[room_id], add that number to the total.
     • Otherwise (capacity exceeded), do not add.
3. Output: Output the cumulative result across all days.

Complexity

Let the total input size be \(S = \sum K_i\).

• Time complexity: \(O(M + S)\)
  • Reading the classroom capacities takes \(O(M)\).
  • The aggregation and checking for each day takes time proportional to that day’s visitor count \(K_i\), so the total is \(O(S)\).
• Space complexity: \(O(M + \max K_i)\)
  • \(O(M)\) is needed for the array storing capacities.
  • The hash map for each day’s aggregation uses at most \(O(K_i)\) space.

Implementation Tips

• Fast I/O: Since the total number of input values is large, in Python it is effective to read all input at once using techniques like sys.stdin.read().split().

• Efficient aggregation: By using collections.Counter, you can easily aggregate “how many of each element exist” from a list in \(O(K_i)\).

• Handling 1-indexed: Since classroom numbers \(1 \sim M\) are used directly as array indices, preparing an array of size \(M+1\) helps prevent off-by-one errors.

  Source Code

import sys
from collections import Counter

def solve():
    # 全ての入力を一度に読み込み、空白文字で分割してトークン化します。
    # これにより、行の区切りを気にせずにデータを取得できます。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # 全てのトークンを整数に変換します。
    data = list(map(int, input_data))
    
    # 読み込み位置を管理するポインタ
    ptr = 0
    
    # N: イベントの日数, M: 教室の個数
    if ptr + 1 >= len(data):
        return
    N = data[ptr]
    M = data[ptr+1]
    ptr += 2
    
    # 各教室の定員情報を取得（1-indexedにするためサイズ M+1 のリストを作成）
    # C[j] に教室 j の定員が入るようにします。
    C = [0] * (M + 1)
    for i in range(1, M + 1):
        if ptr < len(data):
            C[i] = data[ptr]
            ptr += 1
            
    total_participants = 0
    
    # N日間、各日の情報を処理します。
    for _ in range(N):
        if ptr >= len(data):
            break
        
        # その日の来場者数 K
        K = data[ptr]
        ptr += 1
        
        # その日の来場者が希望する教室のリストを取得
        # 連続した K 個の要素をスライスで取得します。
        day_rooms = data[ptr : ptr + K]
        ptr += K
        
        # 各教室を希望した人数をカウントします。
        # collections.Counter を使用することで、効率的に集計できます。
        day_counts = Counter(day_rooms)
        
        # 各教室ごとに、希望者数が定員以下かどうかを判定します。
        for room_id, count in day_counts.items():
            # room_id が有効な範囲内であり、かつ定員以下の場合のみ加算
            if room_id <= M and count <= C[room_id]:
                total_participants += count
            # 定員を超えた場合は、その教室の講演は中止（0人が参加）となります。
            
    # 全日程の合計人数を出力します。
    sys.stdout.write(str(total_participants) + '\n')

if __name__ == '__main__':
    solve()

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