Overview

This problem asks us to find the total number of participants over \(N\) days, under the condition that for each day, if the number of applicants for a classroom is within its capacity, all of them can participate, but if it exceeds the capacity, none of them can participate in that classroom.

Analysis

Based on the problem’s conditions, we need to tally the number of applicants for each classroom on each day and determine whether that number is within the classroom’s capacity. A straightforward approach would be to process all visitor information for each day, count the number of applicants for each classroom, and compare with the capacity.

The key observation is that the total sum of daily visitors \(K_i\) is at most around 200,000. Therefore, counting the occurrences of requested classrooms for each day is sufficiently efficient. However, since the number of classrooms \(M\) can be up to 100,000, checking all classrooms every day would be inefficient. We realize that we only need to process the classrooms that actually have applicants on that day.

Algorithm

1. Read the capacity \(C_j\) for each classroom
2. For each day, perform the following:
   • Read the number of visitors \(K_i\) and the list of requested classrooms
   • Use a dictionary (or hash map) to count the number of applicants for each requested classroom
   • For each requested classroom, if the number of applicants is at most the capacity \(C_j\), add that number to the participant count
3. Sum up the participant counts across all days and output the result

Since we only process classrooms that actually have applicants on each day, the computation is efficient.

Complexity

• Time complexity: \(O(\sum_{i=1}^{N} K_i)\)
• Space complexity: \(O(M + \max(K_i))\)

Implementation Notes

• Efficiency can be improved by reading all input data at once

• Use a dictionary for each day to count occurrences of requested classrooms

• Classroom numbers are 1-indexed, so be careful with array indexing

• Since we only process classrooms that actually have applicants on that day, no unnecessary loops occur

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
    
    it = iter(data)
    N = int(next(it)); M = int(next(it))
    C = [0] * (M + 1)
    for j in range(1, M + 1):
        C[j] = int(next(it))
    
    total_attended = 0
    for i in range(N):
        K_i = int(next(it))
        day_requests = []
        for k in range(K_i):
            p = int(next(it))
            day_requests.append(p)
        
        count_per_room = {}
        for room in day_requests:
            count_per_room[room] = count_per_room.get(room, 0) + 1
        
        day_attended = 0
        for room, count in count_per_room.items():
            if count <= C[room]:
                day_attended += count
        
        total_attended += day_attended
    
    print(total_attended)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.