Overview

This is a problem where you select up to \(K\) items from those stored in accessible areas, choosing the ones with the highest selling prices, and compute their total value.

Analysis

There are two key points for solving this problem:

1. Quickly determining which items are “selection candidates” We need to check whether the area \(C_i\) where each item is stored is included in the list of accessible areas \(\{S_1, S_2, \ldots, S_Q\}\). Since the number of items \(N\) and the number of accessible areas \(Q\) can be up to the order of \(10^5\), searching through the entire list \(S\) for each item would take \(O(N \times Q)\) time in the worst case, which would not meet the time limit. Therefore, by using a bucket (boolean array) or a set, we can determine whether a specific area is accessible in \(O(1)\).

2. Selecting items to maximize the total value (greedy method) There is a restriction of “at most \(K\) items” that can be selected. To maximize the total value, the optimal strategy is to select items in descending order of selling price from the available items. This is a fundamental approach known as the “greedy method.”

Algorithm

We compute the solution using the following steps:

1. Recording accessible areas: Prepare a boolean array is_accessible of length \(M+1\), and set the elements at positions \(S_1, \ldots, S_Q\) to True.
2. Filtering items: Check all items \((V_i, C_i)\), and add the price \(V_i\) to the list valid_prices only for items where is_accessible[C_i] is True.
3. Sorting: Sort the list valid_prices in descending order (largest first).
4. Computing the total: Take up to \(K\) items from the beginning of the sorted list and output their sum. If there are fewer than \(K\) candidate items, simply sum all available items.

Complexity

• Time complexity: \(O(N \log N + M)\)
  • Recording accessible areas takes \(O(Q + M)\)
  • Filtering items takes \(O(N)\)
  • Sorting items takes \(O(N \log N)\)
  • Overall, this is sufficiently fast for the constraints on \(N, M\) (approximately \(10^5\)).
• Space complexity: \(O(N + M)\)
  • Required for storing the list of item prices and the array of area information.

Implementation Notes

• Fast input/output: In Python, repeatedly calling input() can be slow, so we use sys.stdin.read().split() to read all input at once, speeding up the process.

• Using slicing: Python’s list slice valid_prices[:K] does not raise an error even when the list has fewer than \(K\) elements — it simply returns all available elements. This allows us to write the count-checking logic concisely.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割します。
    # 大量の入力を高速に処理するために sys.stdin.read().split() を使用します。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # 読み込んだ文字列のリストを整数のリストに変換します。
    nums = list(map(int, input_data))
    
    # 基本情報の取得
    # N: 商品の数, M: エリアの数, K: 最大選抜数, Q: 立ち入り可能エリア数
    N = nums[0]
    M = nums[1]
    K = nums[2]
    Q = nums[3]
    
    # 立ち入り可能なエリアを高速に判定するために、真偽値の配列を作成します。
    # エリア番号は1からMまでなので、サイズをM+1にします。
    is_accessible = [False] * (M + 1)
    
    # 立ち入り可能なエリア番号(S_j)は、N個の商品情報(V_i, C_i)の後に続いています。
    # 商品情報の開始インデックスは4、各商品は2つの数値(V, C)を持つため、
    # S_jの開始インデックスは 4 + 2 * N となります。
    s_start = 4 + 2 * N
    for i in range(s_start, s_start + Q):
        area_id = nums[i]
        is_accessible[area_id] = True
        
    # 立ち入り可能なエリアに保管されている商品の販売価格を抽出します。
    # 商品iの販売価格 V_i は nums[4 + 2*i]、エリア番号 C_i は nums[4 + 2*i + 1] です。
    valid_prices = []
    for i in range(N):
        v_idx = 4 + 2 * i
        c_idx = 4 + 2 * i + 1
        if is_accessible[nums[c_idx]]:
            valid_prices.append(nums[v_idx])
    
    # 販売価格の合計を最大化するため、抽出した価格を降順（大きい順）にソートします。
    valid_prices.sort(reverse=True)
    
    # 上位 K 個（商品が K 個未満の場合はすべて）の販売価格の合計を計算して出力します。
    # Pythonのスライス valid_prices[:K] はリストの要素数が K 未満でもエラーになりません。
    print(sum(valid_prices[:K]))

if __name__ == '__main__':
    solve()

---

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