Overview

By selecting the \(K\) items with the highest points and summing them, we can find the maximum number of points that can be earned.

Analysis

In this problem, Takahashi wants to maximize his total points using \(K\) purchase opportunities. However, there is a constraint that each item can only be purchased once.

Naive Approach and Its Issues

For example, one could consider exhaustively searching through all combinations of choosing \(K\) items from all products. However, this would require \(_N C_K\) combinations, and since \(N\) can be up to \(2 \times 10^5\), this is not practical (it would take far too much time).

Key to the Solution: Greedy Algorithm

In fact, this problem can be solved efficiently using a “greedy algorithm.” Specifically, the strategy of “always choosing the item with the highest points” is optimal. This is because, to maximize the total points earned, we want to select as many high-scoring items as possible. Also, since the same item cannot be purchased twice, it is optimal to select the top \(K\) items one by one.

Concrete Example

For example, suppose we have the following input:

N = 5, K = 3
P = [10, 20, 5, 15, 25]

Sorting the points in descending order:

[25, 20, 15, 10, 5]

The sum of the top 3 is \(25 + 20 + 15 = 60\), which is the maximum value.

Algorithm

1. Read the list of item points \(P\).
2. Sort the points in descending order.
3. Take the first \(K\) elements from the sorted list and compute their sum.
4. Output the sum.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (for storing the input list)

Implementation Notes

• Using sort(reverse=True) makes it easy to sort in descending order.

• sum(P[:K]) quickly computes the sum of the first \(K\) elements.

• Don’t forget to use map(int, ...) when reading the input.

  Source Code

# 入力受け取り
N, K = map(int, input().split())
P = list(map(int, input().split()))

# ポイントが高い順にソート
P.sort(reverse=True)

# 上位K個のポイントを合計
answer = sum(P[:K])

# 出力
print(answer)

---

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