Overview

This problem asks you to calculate the satisfaction level of each snack (base tastiness + preference adjustment) and find the sum of the top \(K\) satisfaction levels.

Analysis

Key Insight

The key points of this problem are very simple:

1. Each snack’s satisfaction can be calculated independently: The satisfaction of snack \(i\) is \(T_i + C_i\), which is not affected by the choice of other snacks
2. Greedy approach is optimal: To maximize the total satisfaction, simply select the \(K\) snacks with the highest satisfaction levels in order

Concrete Example

For example, suppose \(N = 4\), \(K = 2\) with the following snacks:

Snack	\(T_i\)	\(C_i\)	Satisfaction \(T_i + C_i\)
1	10	5	15
2	8	-3	5
3	20	-5	15
4	3	10	13

Sorting satisfaction levels in descending order: 15, 15, 13, 5

Selecting the top \(K = 2\), we choose the snacks with satisfaction 15 and 15, giving a total of \(15 + 15 = 30\).

About the Naive Approach

For this problem, the naive approach of “trying all combinations of \(K\) items” is unnecessary. - Enumerating all combinations takes \(O(\binom{N}{K})\), which results in TLE for large \(N\) - However, since we can obtain the optimal solution by simply sorting and selecting the top \(K\) items, this is not needed

Algorithm

1. Calculate satisfaction levels: For each snack \(i\), calculate the satisfaction \(T_i + C_i\) and store it in a list
2. Sort: Sort the satisfaction list in descending order (largest first)
3. Sum of top K: Take the first \(K\) elements from the sorted list and calculate their sum

Input: N=4, K=2, snack information
↓
Satisfaction list: [15, 5, 15, 13]
↓ Sort (descending)
[15, 15, 13, 5]
↓ Select top K
[15, 15]
↓ Sum
Output: 30

Complexity

• Time Complexity: \(O(N \log N)\)

  • Calculating satisfaction levels: \(O(N)\)
  • Sorting: \(O(N \log N)\)
  • Sum of top \(K\): \(O(K)\) (which is \(O(N)\) since \(K \leq N\))
  • Overall, \(O(N \log N)\) dominates

• Space Complexity: \(O(N)\)

  • The list storing satisfaction levels holds \(N\) elements

Implementation Notes

1. Be careful of overflow: Based on the ranges of \(T_i\) and \(C_i\), the maximum satisfaction is approximately \(2 \times 10^9\). The sum of \(K\) items can be at most approximately \(4 \times 10^{14}\), but in Python there’s no need to worry about integer overflow (in C++ and similar languages, you need to use long long)

2. Descending sort: Using sort(reverse=True) sorts in descending order

3. Using slicing: In Python, satisfactions[:K] easily extracts the first \(K\) elements

Source Code

def main():
    N, K = map(int, input().split())
    satisfactions = []
    for _ in range(N):
        T, C = map(int, input().split())
        satisfactions.append(T + C)
    
    # Sort satisfaction levels in descending order and find the sum of top K
    satisfactions.sort(reverse=True)
    print(sum(satisfactions[:K]))

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.