Overview

This is a problem of maximizing the total points that can be earned from \(N\) types of products using at most \(K\) purchase opportunities. Under the constraint that each product can only be purchased once, we need to collect points efficiently.

Analysis

The key to solving this problem is to think about “which products should be purchased with priority.”

To maximize the total points, the best strategy is simply to select products in order from the highest point value. This approach of repeatedly making the most profitable choice at each step is called a “greedy algorithm.”

However, we need to pay attention to the following two constraints: 1. Purchase limit: We can make at most \(K\) purchases. 2. Product variety limit: There are only \(N\) types of products. Since each product can only be bought once, even if \(K\) is greater than \(N\), we can purchase at most \(N\) items.

Therefore, the actual number of items to purchase is “the smaller value of \(N\) and \(K\).”

Algorithm

We find the solution using the following steps:

1. Read input: Obtain the number of products \(N\), purchase opportunities \(K\), and the points \(P_i\) for each product.
2. Sort: Sort the points \(P_i\) of each product in descending order (from largest to smallest).
3. Determine quantity: Calculate the number of products to buy, num_to_buy, as \(\min(N, K)\).
4. Calculate total: Sum up the first num_to_buy elements from the sorted list.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the list of points is the bottleneck. For \(N=2 \times 10^5\), \(O(N \log N)\) comfortably fits within the time limit.
• Space complexity: \(O(N)\)
  • This is the memory required to store the points of \(N\) products in a list.

Implementation Notes

• Sort order: Python’s sort() method and sorted() function default to ascending order (smallest first), so you need to either specify reverse=True for descending order, or use slicing after sorting to retrieve elements from the end.

• Case where \(K > N\): Since the problem constraints allow \(K\) to exceed \(N\), simply trying to select \(K\) items could result in an out-of-bounds access on the list. This can be handled safely by using min(n, k), or by leveraging the property of slicing (p[:k] does not raise an error even if \(k\) exceeds the number of elements).

  Source Code

import sys

def solve():
    # 標準入力からNとKを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    
    # ポイントのリストを読み込む
    p = list(map(int, input_data[2:]))
    
    # ポイントを降順（大きい順）にソートする
    p.sort(reverse=True)
    
    # 購入できる最大数は商品の種類数Nと購入機会Kの小さい方
    num_to_buy = min(n, k)
    
    # 上位 num_to_buy 個の合計を計算して出力する
    print(sum(p[:num_to_buy]))

if __name__ == '__main__':
    solve()

---

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