Overview

A problem where you purchase each product at the cheapest store that handles the corresponding category, and find the minimum total cost to buy all products.

Analysis

In this problem, for each product category, you need to select the store that offers the lowest price.

A naive approach would be “for each product, look through all stores that handle the corresponding category and find the cheapest price,” but since the number of products \(N\) and the number of stores \(M\) can be up to \(2 \times 10^5\), the time complexity would be \(O(N \times M)\), which is too slow (TLE).

Instead, if we precompute “the minimum price for each category,” we can find the cheapest price for each product in constant time. This preprocessing can be achieved by recording the minimum price for each category while reading the store information.

Also, if there is a category in the product list that no store handles, we output -1 and terminate at that point.

Algorithm

1. For each category \(S_j\), record the minimum price \(C_j\) (using a dictionary or similar data structure).
2. Go through the product list \(T_i\) in order, adding the minimum price for each corresponding category to the total.
3. If there is no store handling a corresponding category, output -1 and terminate.
4. If all products can be purchased, output the total cost.

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(M)\) (proportional to the number of categories)

Implementation Notes

• To efficiently manage the minimum price for each category, it is useful to use dict or defaultdict.

• sys.stdin.read is used for fast input reading (important in Python).

• By immediately outputting -1 and terminating when a non-existent category is encountered, unnecessary computation is avoided.

  Source Code

import sys
from collections import defaultdict
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    idx = 2
    T = list(map(int, data[idx:idx+N]))
    idx += N
    
    # shops[S] = min cost for category S
    shops = {}
    for _ in range(M):
        s = int(data[idx])
        c = int(data[idx+1])
        idx += 2
        if s not in shops:
            shops[s] = c
        else:
            if c < shops[s]:
                shops[s] = c
    
    total_cost = 0
    for t in T:
        if t not in shops:
            print(-1)
            return
        total_cost += shops[t]
    
    print(total_cost)

if __name__ == "__main__":
    main()

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