Overview

Given \(N\) products, you can select up to \(K\) of them and make their prices \(0\) yen. The problem asks you to minimize the total amount paid.

Approach

To minimize the total amount paid, we should think about “maximizing the amount saved by using coupons (the discount amount).”

Each coupon makes the price of one product \(0\) yen. Therefore, using a coupon on a product priced at \(1000\) yen saves \(1000\) yen, but using it on a \(100\) yen product only saves \(100\) yen.

From this observation, the following strategy is optimal: - Select the \(K\) most expensive products and apply coupons to them.

If the number of coupons \(K\) is greater than the number of products \(N\), all products can be made \(0\) yen, so the total amount is \(0\) yen.

Algorithm

1. Receive the list of product prices \(D\).
2. Sort the list \(D\) in descending order (from largest to smallest).
3. Exclude the first \(K\) products (or treat them as \(0\) yen).
4. Sum up the prices of the remaining products.

As a concrete example, consider the case where \(N=5, K=2\) and the prices are \([100, 500, 200, 800, 300]\). - Sorting in descending order gives \([800, 500, 300, 200, 100]\). - Apply coupons to the \(2\) most expensive items (\(800\) yen and \(500\) yen). - The answer is \(600\) yen, which is the sum of the remaining \([300, 200, 100]\).

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the product prices takes \(O(N \log N)\). The subsequent summation is \(O(N)\), so the sorting complexity dominates.
• Space complexity: \(O(N)\)
  • A list of length \(N\) is used to store the product prices.

Implementation Notes

• In Python, you can easily sort in descending order using list.sort(reverse=True).

• By using slicing such as sum(d[k:]), you can concisely express the operation of “summing only the elements from the \(K\)-th onward.” When \(K \geq N\), the slice d[k:] returns an empty list, so the result correctly becomes \(0\).

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを取得し、スペース区切りで分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 商品の数, K: クーポンの最大使用回数
    n = int(input_data[0])
    k = int(input_data[1])
    
    # D: 各商品の価格リスト
    d = list(map(int, input_data[2:]))
    
    # 支払う合計金額を最小化するためには、価格が高い商品から順にクーポンを適用するのが最適です。
    # 商品の価格を降順（大きい順）にソートします。
    d.sort(reverse=True)
    
    # クーポンは最大 K 個の商品を 0 円にできるため、
    # 価格が高い方から K 個を除いた残りの商品の合計金額が、支払う最小金額となります。
    # スライス d[k:] を使うことで、インデックス K 以降（K+1番目以降の商品）を取得できます。
    # もし K >= N の場合、d[k:] は空リストになり、sum は 0 を返します。
    ans = sum(d[k:])
    
    # 結果を出力します
    print(ans)

if __name__ == '__main__':
    solve()

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