Overview

Given \(N\) types of seating areas (price \(C_i\), capacity \(K_i\)), \(M\) fans sequentially attempt to reserve their desired area \(P_j\). This is a simulation problem where we manage the capacity of each area and calculate the total price of successfully reserved tickets.

Analysis

The key point of this problem is managing in real-time how many seats remain in each area.

Since fans make reservations one at a time in order, the result of a previous person’s reservation affects whether later people can reserve. Therefore, we need to process the following operations in the exact order fans are given in the input:

1. Check the remaining number of seats (capacity) for the fan’s desired area \(P_j\).
2. If at least \(1\) seat remains:
   • The reservation succeeds: add the price \(C_{P_j}\) of that area to the total amount.
   • Decrease the remaining seat count for that area by \(1\).
3. If no seats remain:
   • The reservation fails: do nothing.

Checking the constraints, both the number of areas \(N\) and the number of fans \(M\) are at most \(10^5\). If we can process each fan in constant time \(O(1)\), the overall complexity is \(O(N + M)\), which is well within the time limit.

Algorithm

1. Data storage: Store the price \(C\) and capacity \(K\) for each area in arrays (lists).
   • Since area numbers are given from \(1\) to \(N\), be careful to handle the offset with program indices (\(0\) to \(N-1\)).
2. Simulation: Loop over the \(M\) fans.
   • Get the current fan’s desired area \(P_j\).
   • Check whether K[P_j] is greater than \(0\).
   • If the condition is met, add C[P_j] to the total price variable total_price and decrease K[P_j] by \(1\).
3. Output: Print the final total_price.

Complexity

• Time complexity: \(O(N + M)\)
  • Reading area information takes \(O(N)\), and processing fan reservations (loop) takes \(O(M)\). Since each reservation is processed in constant time, the overall time is linear.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for arrays storing each area’s price and capacity.

Implementation Notes

• Fast I/O: In Python, when the amount of data is large (around \(10^5\) lines), the input() function can be slow. By reading all input at once using sys.stdin.read().split(), execution time can be reduced.

• Index adjustment: The area numbers \(1 \dots N\) from the problem statement need to be converted to array indices \(0 \dots N-1\) (e.g., subtracting \(1\) from the input \(P_j\)).

  Source Code

import sys

def solve():
    # 入力データをすべて読み込み、スペースや改行で分割してリストに格納します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 座席エリアの数, M: ファンの数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各エリアの価格 C と定員 K を格納するリスト
    # 0インデックスで管理するため、エリア i はインデックス i-1 に対応させます
    C = [0] * N
    K = [0] * N
    
    # エリア情報の読み込み
    idx = 2
    for i in range(N):
        C[i] = int(input_data[idx])
        K[i] = int(input_data[idx + 1])
        idx += 2
        
    total_price = 0
    # 各ファンの予約処理を順番に行います
    for _ in range(M):
        # 予約しようとするエリア番号 P (1-indexed)
        p = int(input_data[idx])
        idx += 1
        
        # 0-indexed に変換
        area_idx = p - 1
        
        # 定員に達していなければ予約可能
        if K[area_idx] > 0:
            total_price += C[area_idx]
            K[area_idx] -= 1
            
    # 合計金額を出力
    print(total_price)

if __name__ == '__main__':
    solve()

---

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