Overview

This problem asks you to minimize the total amount paid when purchasing all \(N\) items, using a coupon that can make up to \(K\) items free.

Analysis

Key Insight

Since coupons can make items cost \(0\) yen, using coupons on more expensive items is more beneficial.

For example, consider the case where item prices are \([100, 300, 200, 500]\) and \(K = 2\): - Sorted in descending order: \(500, 300, 200, 100\) - Items to use coupons on: the \(500\) yen and \(300\) yen items (top 2) - Amount to pay: \(200 + 100 = 300\) yen

If you used coupons on cheaper items (\(100\) yen and \(200\) yen), you would pay \(500 + 300 = 800\) yen, resulting in a loss.

Why Greedy Works

In this problem, there is only a simple constraint: “up to \(K\) items can be made free.” Since there are no dependencies between items, the greedy approach of selecting the \(K\) most expensive items and applying coupons to them gives the optimal solution.

Comparison with Naive Approach

If you tried all combinations of items, you would need to examine \(\binom{N}{K}\) ways to choose \(K\) items from \(N\). When \(N\) or \(K\) is large, the computational complexity explodes and results in TLE (Time Limit Exceeded).

Using the greedy approach, the optimal solution can be found just by sorting.

Algorithm

1. Sort the price list \(D\) in descending order (highest first)
2. After sorting, apply coupons to the first \(K\) items (these become \(0\) yen)
3. Calculate and output the sum of prices for the remaining items (from index \(K\) onwards)

After sorting: D[0], D[1], ..., D[K-1], D[K], D[K+1], ..., D[N-1]
               ~~~~~~~~~~~~~~~~~~~~    ~~~~~~~~~~~~~~~~~~~~~~~~~~~
               Coupon applied (0 yen)   Items to pay for (calculate sum)

Complexity

• Time complexity: \(O(N \log N)\)
  • \(O(N \log N)\) for sorting
  • \(O(N)\) for calculating the sum
• Space complexity: \(O(N)\)
  • \(O(N)\) for storing the price list

Implementation Notes

1. Descending sort: Use D.sort(reverse=True) to arrange prices from highest to lowest

2. Sum calculation with slicing: D[K:] represents “all elements from index \(K\) onwards” in Python slice notation. This concisely retrieves “items without coupon application”

3. When \(K = N\): Coupons can be applied to all items, so D[N:] becomes an empty list, and sum([]) returns \(0\). No special case handling is needed

4. Beware of overflow: \(D_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), so the sum can be around \(2 \times 10^{14}\) at maximum. Python has no integer overflow issues, but in other languages, you need to use 64-bit integer types

   Source Code

N, K = map(int, input().split())
D = list(map(int, input().split()))

D.sort(reverse=True)
print(sum(D[K:]))

---

This editorial was generated by claude4.5opus.