Overview

Given \(N\) souvenirs, give up \(K\) of them and bring back the rest. The problem is to maximize the total satisfaction of the souvenirs you bring back.

Analysis

The goal of this problem is to maximize the total satisfaction of the souvenirs you bring back. In other words, we need to minimize the total satisfaction of the souvenirs we give up.

Naive Approach and Its Issues

For example, if we exhaustively search all ways to choose \(K\) items from all combinations, the number of combinations would be \({}_N C_K\), resulting in an extremely large computational cost. This is impractical, especially since \(N\) can be as large as \(2 \times 10^5\).

Solution

In fact, since we want to bring back souvenirs with high satisfaction, it is optimal to give up the \(K\) souvenirs with the lowest satisfaction.

Therefore, we can solve the problem with the following steps: 1. Sort all souvenirs in descending order of satisfaction. 2. Take the sum of the top \((N - K)\) satisfaction values — this gives the maximum total satisfaction of the souvenirs we bring back.

Example

For instance, consider the following input:

N = 5, K = 2
D = [3, 1, 4, 1, 5]

Sorting in descending order gives:

[5, 4, 3, 1, 1]

The sum of the top \(N - K = 3\) items is \(5 + 4 + 3 = 12\), which is the answer.

Algorithm

1. Sort the satisfaction list \(D\) in descending order.
2. Compute the sum of the first \((N - K)\) elements.
3. Output that sum.

Complexity

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

Implementation Notes

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

• You can extract the top \((N - K)\) items using the slice D[:N - K].

• The total can be computed using the sum() function.

  Source Code

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

# 満足度を降順にソート
D.sort(reverse=True)

# 上位(N - K)個の合計が答え
answer = sum(D[:N - K])

# 出力
print(answer)

---

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