Overview

This problem asks us to maximize the total satisfaction of souvenirs we bring home when giving up \(K\) out of \(N\) souvenirs. This can be solved with a greedy approach: “select the \(N-K\) souvenirs with the highest satisfaction.”

Analysis

Rephrasing the Problem

“Giving up \(K\) items” means “bringing home \(N-K\) items.”

Since we want to maximize the total satisfaction of souvenirs we bring home, the problem can be rephrased as follows:

Select \(N-K\) items from \(N\) souvenirs to maximize the total satisfaction

Key Insight

To maximize the total, selecting items in order of decreasing satisfaction is optimal.

For example, consider the case where \(N = 5\), \(K = 2\), and satisfactions are \([3, 1, 4, 1, 5]\). - We can bring home \(N - K = 3\) items - Sorting satisfactions in descending order gives \([5, 4, 3, 1, 1]\) - Selecting the top \(3\) items gives \(5 + 4 + 3 = 12\)

This is the maximum value. Conversely, the optimal strategy is to give up the \(K\) items with the lowest satisfaction (in this example, \(1, 1\)).

Why the Greedy Approach Works

Since all satisfactions are positive values (\(D_i \geq 1\)), it’s always better to select items with higher satisfaction if we can. Since the number of items to select is fixed (\(N-K\)), we can obtain the optimal solution by simply selecting the top items.

Algorithm

1. Read input (\(N\), \(K\), satisfaction array \(D\))
2. Sort array \(D\) in descending order (largest first)
3. Calculate the sum of the first \(N-K\) elements of the sorted array
4. Output that sum

Execution with a Concrete Example

Input: \(N = 4\), \(K = 1\), \(D = [10, 30, 20, 40]\)

1. Sort in descending order: \(D = [40, 30, 20, 10]\)
2. Select top \(N-K = 3\) items: \(40, 30, 20\)
3. Sum: \(40 + 30 + 20 = 90\)

Output: 90

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting takes \(O(N \log N)\)
  • Computing the sum takes \(O(N-K) \subseteq O(N)\)
• Space complexity: \(O(N)\)
  • Size of the array storing satisfactions

Implementation Notes

• In Python, sort(reverse=True) sorts in descending order
• Slice D[:N-K] retrieves the first \(N-K\) elements
• The sum() function easily computes the sum of a list
• It’s important not to be confused by the problem statement saying “give up \(K\) items,” and instead interpret it as “select \(N-K\) items”

Source Code

def solve():
    N, K = map(int, input().split())
    D = list(map(int, input().split()))
    
    # Since we give up K items, we bring home N-K items
    # To maximize total satisfaction, select the N-K items with highest satisfaction
    
    D.sort(reverse=True)
    
    # Calculate the sum of top N-K items
    result = sum(D[:N-K])
    
    print(result)

solve()

---

This editorial was generated by claude4.5opus.