Overview

When you can make the prices of up to \(K\) selected products \(0\) yen, the optimal strategy to minimize the total payment is to “use coupons on the most expensive products first.”

Analysis

Using a coupon directly reduces the payment for that product. In other words, the “discount” obtained by using a coupon on product \(i\) is exactly \(D_i\) yen. Therefore, minimizing the total payment is equivalent to “maximizing the total discount.”

The key insight is as follows:

• When selecting \(K\) products to use coupons on, the total discount equals the sum of the prices of the selected products
• To maximize the total discount, we should prioritize selecting products with higher prices (greedily pick from the largest)

For example, if \(D=[5, 2, 9, 4]\) and \(K=2\): - Using coupons on the two most expensive items \(9\) and \(5\) gives a discount of \(14\), and the payment is \((5+2+9+4)-14=6\) - If we use coupons on \(5\) and \(4\), the discount is \(9\), and the payment is \(20-9=11\)

So using coupons on more expensive products is always better.

Naively exploring all possible choices of which products to use coupons on would require \({N \choose K}\) combinations, which is far too slow for \(N \le 2\times 10^5\). Instead, we reduce the problem to the greedy approach of “selecting the \(K\) largest prices” and solve it with sorting.

Algorithm

1. Compute the total sum \(S=\sum D_i\) of the price array \(D\).
2. Sort \(D\) in descending order.
3. Compute the sum \(T\) of the first \(K\) elements (the \(K\) most expensive items).
4. The answer is \(S-T\).

※ When \(K=0\), no discount can be applied, so simply output \(S\).

Complexity

• Time complexity: Dominated by sorting, so \(O(N \log N)\)
• Space complexity: \(O(N)\) to store the array

Implementation Notes

• Since \(D_i\) can be up to \(10^9\) and \(N\) can be up to \(2\times 10^5\), the total can be as large as approximately \(2\times 10^{14}\). Python’s int can handle this safely.

• Using D.sort(reverse=True) for descending sort and sum(D[:K]) to get the sum of the top \(K\) elements makes the code concise.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    D = list(map(int, input().split()))
    total = sum(D)
    if K == 0:
        print(total)
        return
    D.sort(reverse=True)
    print(total - sum(D[:K]))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.