Overview

Among the products in accessible areas, we find the maximum total price when selecting up to \(K\) items with the highest selling prices.

Analysis

First, since the condition states “only products in accessible areas are candidates,” we can filter candidates by checking whether each product’s area is permitted. The problem then is how to select “up to \(K\) items” from the candidate products to maximize the total.

Intuitively, “collect all candidates, sort in descending order, and sum the top \(K\)” works, but since there can be up to \(N=2\times 10^5\) candidates, sorting at \(O(N\log N)\) is often fast enough. However, more generally, “it suffices to maintain only the top \(K\),” and there is no need to sort the entire collection each time.

The key insight is: - To maximize the total, it is optimal to select the \(K\) items with the highest values from the candidates. - In other words, we just need to efficiently manage the “top \(K\) items.”

For this purpose, we use a data structure (min-heap) that maintains a set of size \(K\) while allowing us to immediately retrieve “the minimum value among the currently selected items.”

Example: When \(K=3\) and the candidate values arrive in order \([5,1,4,10,3]\): - First 3 items give \(\{5,1,4\}\) (minimum is 1) - Next, 10 is greater than the minimum 1, so we swap → \(\{5,4,10\}\) - Next, 3 is not greater than the minimum 4, so we ignore it In the end, we obtain the sum of the top 3 items.

Algorithm

1. Create the accessible area set \(S\) as an array accessible[area] (boolean), setting True for each \(S_j\).
2. Prepare a min-heap heap and a variable total representing the sum of values currently in the heap.
3. For each product \((V_i, C_i)\), do the following:
   • If accessible[C_i] is False, skip (not a candidate).
   • If the number of selected items is still less than \(K\), add \(V_i\) to the heap and add it to total.
   • If \(K\) items are already selected, compare with the heap’s minimum value heap[0]:
     • If \(V_i > heap[0]\), swap with the minimum value (heapreplace). Update total by the difference.
     • Otherwise, adding it would not make the top \(K\), so ignore it.
4. Output total at the end.

With this method, only the “top \(K\) among all candidates seen so far” remain in the heap at all times, and the total is maintained simultaneously.

Complexity

• Time complexity: \(O(N \log K + M + Q)\) (essentially, each candidate product requires at most one heap operation at \(O(\log K)\))
• Space complexity: \(O(M + K)\) (the accessibility array and the heap)

Implementation Notes

• Accessibility checking can be done with a set (set), but since \(M\le 10^5\), using a boolean array accessible is faster.

• Updating total incrementally each time eliminates the need to re-sum the heap contents at the end.

• heapq.heapreplace(heap, v) has a smaller constant factor than “pop the minimum then push,” and makes difference-based updates easier.

• Since the input is large, reading all at once with sys.stdin.buffer.read() is faster.

  Source Code

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    idx = 0

    N = data[idx]; M = data[idx + 1]; K = data[idx + 2]; Q = data[idx + 3]
    idx += 4

    items_v = [0] * N
    items_c = [0] * N
    for i in range(N):
        items_v[i] = data[idx]
        items_c[i] = data[idx + 1]
        idx += 2

    accessible = [False] * (M + 1)
    for _ in range(Q):
        s = data[idx]
        idx += 1
        accessible[s] = True

    heap = []
    total = 0

    for v, c in zip(items_v, items_c):
        if not accessible[c]:
            continue
        if len(heap) < K:
            heapq.heappush(heap, v)
            total += v
        else:
            if v > heap[0]:
                smallest = heapq.heapreplace(heap, v)
                total += v - smallest

    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.