Overview

Each seating area of a concert has a fixed capacity and ticket price, and fans attempt to reserve tickets for their specified area in order. When an area exceeds its capacity, no more reservations can be made. Find the total ticket cost after all fans have made their reservation attempts.

Analysis

In this problem, we need to manage “how many seats remain” for each seating area while processing each fan’s reservation request sequentially.

The key observations are as follows:

• Tickets cannot be sold beyond the capacity \(K_i\) of each area.
• Whether a reservation is possible can be determined by checking the “remaining seats” at that point.
• Fan reservation requests are processed in order, so the result of a previous fan affects the next fan.

A naive approach, such as “checking the entire reservation status every time,” would be extremely inefficient (e.g., managing with a 2D list). However, if we only manage the remaining seat count for each area, each reservation request can be processed in constant time.

Therefore, we can efficiently handle this by maintaining an array of remaining seats for each area and decrementing the value for each fan’s request.

Algorithm

1. Read the number of seating areas \(N\) and the number of fans \(M\).
2. Read the ticket price \(C_i\) and capacity \(K_i\) for each area \(i\), and create a “remaining seats management array remaining” by copying the capacity information.
3. Read each fan’s reservation request in order and do the following:
   • If remaining[P_j] for the specified area \(P_j\) is greater than 0,
     • Decrement remaining[P_j] by 1.
     • Add the ticket price \(C_{P_j}\) of that area to the total.
4. Output the final total ticket cost.

With this method, each fan’s reservation is processed in constant time, so the overall processing runs in \(O(M)\).

Concrete Example

For example, given the following input:

2 4
100 2
200 1
1
2
1
1

• Area 1: Price 100 yen, Capacity 2
• Area 2: Price 200 yen, Capacity 1

Fan reservation order: 1. Area 1 → OK (1 remaining), total += 100 → 100 2. Area 2 → OK (0 remaining), total += 200 → 300 3. Area 1 → OK (0 remaining), total += 100 → 400 4. Area 1 → NG (0 remaining), ignored

The final total is 400.

Complexity

• Time complexity: \(O(N + M)\)
  (\(O(N)\) for initial data reading, \(O(M)\) for processing each fan)
• Space complexity: \(O(N)\)
  (\(O(N)\) used for the C, K, and remaining arrays)

Implementation Notes

• By managing remaining seats in a separate array, we can perform checks and updates quickly.

• To handle 1-indexed access, setting the array size to \(N+1\) makes implementation easier.

• To speed up input, sys.stdin.read() is used.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    C = [0] * (N+1)
    K = [0] * (N+1)
    for i in range(1, N+1):
        C[i] = int(data[idx])
        idx += 1
        K[i] = int(data[idx])
        idx += 1
    
    # 各エリアの残り座席数を管理
    remaining = K[:]
    
    total_cost = 0
    for _ in range(M):
        P = int(data[idx])
        idx += 1
        if remaining[P] > 0:
            remaining[P] -= 1
            total_cost += C[P]
    
    print(total_cost)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.