Overview

In a concert where each seating area has a capacity limit, fans attempt to make reservations in order. A reservation succeeds if the area hasn’t reached capacity. The problem asks for the total ticket price of all fans who successfully reserved.

Analysis

The key points of this problem are as follows:

• Fans attempt reservations in order. It’s first-come-first-served: if the capacity hasn’t been reached, the reservation succeeds; otherwise, it fails.
• By tracking “how many more people can reserve (remaining seats)” for each area, we can determine whether each fan’s reservation succeeds or fails.

Let’s think through a concrete example.

For instance, if Area 1 has price \(C_1 = 5000\) and capacity \(K_1 = 2\): - 1st person reserves Area 1 → 1 seat remaining → Success (+5000) - 2nd person reserves Area 1 → 0 seats remaining → Success (+5000) - 3rd person reserves Area 1 → 0 seats remaining, capacity already reached → Failure

Like this, we can determine the outcome simply by counting down the remaining seats.

Comparison with a naive approach:

Since this problem can be solved with a straightforward simulation, no special techniques are needed. However, in Python, when the input is large (potentially over \(10^5\) lines), calling input() line by line can be slow, so it’s important to read all input at once using sys.stdin.read().

Algorithm

1. For \(N\) areas, store the price \(C_i\) and capacity (remaining seats) \(K_i\) in arrays.
2. Process \(M\) fans in order:
   • For the area \(P_j\) that fan \(j\) wants to reserve, if \(K[P_j] > 0\) (seats available):
     • Decrease \(K[P_j]\) by 1 (consume one seat)
     • Add \(C[P_j]\) to the total amount
   • Otherwise, do nothing (reservation failed)
3. Output the final total amount.

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(N)\) for reading area information, \(O(M)\) for processing fan reservations (each fan’s processing is \(O(1)\))
• Space complexity: \(O(N)\)
  • Arrays to store the price and remaining seats for each area

Implementation Tips

• Fast input processing: In Python, reading all input at once with sys.stdin.read(), splitting with split(), and accessing sequentially by index is fast. This is significantly faster than calling input() \(M\) times.

• 1-indexed arrays: Since area numbers range from \(1\) to \(N\), allocating arrays of size \(N+1\) and using indices \(1\) through \(N\) eliminates the need for index conversion.

• Direct management of remaining seats: While counting the number of reservations and comparing with the capacity is also correct, decrementing the remaining seats is simpler and more efficient.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    C = [0] * (N + 1)
    K = [0] * (N + 1)
    for i in range(1, N + 1):
        C[i] = int(input_data[idx]); idx += 1
        K[i] = int(input_data[idx]); idx += 1
    
    total = 0
    for j in range(M):
        p = int(input_data[idx]); idx += 1
        if K[p] > 0:
            K[p] -= 1
            total += C[p]
    
    print(total)

main()

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