Overview

Given the earned points \(P_i\) for each product, maximize the total points under the conditions that each product can be purchased at most once and the maximum number of purchases is \(K\).

Analysis

• The points earned per purchase are fixed for each product, and there are no interactions between purchases (such as discounts or multipliers).
• Furthermore, since there is a constraint that “each product can be purchased at most once,” the optimal strategy is simply to select up to \(K\) products in descending order of points.

Concrete example: - When \(P = [10, 3, 8, 5]\), \(K = 2\):
Sorting in descending order gives \([10, 8, 5, 3]\), so the top 2 give \(10 + 8 = 18\), which is the maximum.
Any other combination (e.g., \(10 + 5 = 15\)) is always smaller.

A brute-force approach of trying all possible subsets of products to buy would result in \(\binom{N}{K}\) combinations, which is impractical for \(N \le 2 \times 10^5\) (TLE).
The key observation in this problem is that there is no need to deliberate over the selection — it is entirely determined by “taking the top items.”

Also, even if \(K\) is larger than \(N\), the maximum number of products that can be bought is \(N\), so the actual number of items we can select is \(k = \min(N, K)\).

Algorithm

1. Sort the array \(P\) in descending order.
2. Set \(k = \min(N, K)\).
3. Output the sum of the first \(k\) elements after sorting: \(\sum_{i=1}^{k} P_i\).

When sorted in descending order, the first \(k\) elements form the subset of \(k\) items with the maximum total, so this is the optimal solution.

Complexity

• Time complexity: \(O(N \log N)\) (sorting)
• Space complexity: \(O(N)\) (storing the array)

Implementation Notes

• Be careful about the case where \(K > N\); set \(k = \min(N, K)\) and sum the first \(k\) elements.

• Since \(P_i\) can be up to \(10^9\) and \(N\) can be large, the total can become very large. However, Python’s int has arbitrary precision, so there is no concern about overflow.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    P.sort(reverse=True)
    k = min(N, K)
    print(sum(P[:k]))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.