Overview

When discarding exactly \(K\) out of \(N\) souvenirs, the optimal strategy to maximize the total satisfaction of the remaining souvenirs is to “discard the \(K\) souvenirs with the lowest satisfaction.”

Analysis

Since the number of souvenirs to bring back is fixed at \(N-K\), maximizing the total satisfaction is equivalent to minimizing the “total satisfaction of discarded souvenirs.”

• If you discard souvenirs with high satisfaction, the total decreases by a large amount.
• Conversely, if you discard souvenirs with low satisfaction, the decrease in the total is minimized.

More formally, if the set of discarded souvenirs contains a mix of “large values” and “small values,” swapping so that large values are kept and small values are discarded will increase (or not change) the total of what you bring back. Therefore, the optimal strategy is ultimately to “discard the \(K\) smallest items.”

Why a Naive Approach Doesn’t Work

If we try all possible combinations of which \(K\) items to discard, there are \(\binom{N}{K}\) combinations, which is far too many to compute when \(N \le 2 \times 10^5\) (TLE).

Concrete Example

For example, when \(D = [6, 2, 9, 4]\) and \(K=2\): - Discard the \(2\) smallest (\(2, 4\)) → Remaining total is \(6+9=15\) - If we discard \(6, 2\) → Remaining total is \(4+9=13\) (smaller)

Therefore, “discarding the smallest items” is the correct approach.

Algorithm

1. Sort the satisfaction array \(D\) in ascending order.
2. The first \(K\) items become the “discarded souvenirs” (the \(K\) smallest).
3. Output the sum of the remaining items (indices \(K\) onward): \(\sum_{i=K}^{N-1} D_i\).

This minimizes the “total satisfaction of discarded souvenirs,” and consequently maximizes the “total satisfaction of souvenirs brought back.”

Complexity

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

Implementation Notes

• Since \(N\) can be large, reading input all at once with sys.stdin.buffer.read() is faster.

• The total satisfaction can be as large as \(10^9 \times 2\times 10^5 = 2\times 10^{14}\), but since Python’s int supports arbitrary precision, using sum directly is fine.

• After sorting, computing sum(D[K:]) concisely calculates the total excluding the \(K\) discarded items.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    D = data[2:2+N]
    D.sort()
    print(sum(D[K:]))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.