Overview

This is a problem where you combine all \(N + M\) fruits together, select the top \(K\) fruits in descending order of sweetness, and find the total of their sweetness values.

Analysis

• Although the fruits already in the store (\(N\) fruits) and the newly arrived fruits (\(M\) fruits) come from different sources, there are no restrictions on how to choose. In other words, the key insight is that all fruits can be treated as a single set without distinction.
• “Selecting \(K\) fruits in descending order of sweetness” simply means sorting all fruits by sweetness in descending order and taking the first \(K\) from the top.
• A straightforward approach of sorting all fruits is sufficiently fast. Since \(N + M \leq 150000\), the sorting complexity of \(O((N+M) \log(N+M))\) is well within the time limit.

Let’s verify with a concrete example.

For instance, with \(N = 3, M = 2, K = 3\), where the sweetness of the store’s fruits is \([5, 1, 3]\) and the sweetness of the new fruits is \([4, 2]\):

1. Combining all together: \([5, 1, 3, 4, 2]\)
2. Sorting in descending order: \([5, 4, 3, 2, 1]\)
3. The top \(K = 3\) fruits are \([5, 4, 3]\)
4. The total is \(5 + 4 + 3 = 12\)

Algorithm

1. Combine the sweetness values of the \(N\) fruits and the \(M\) fruits into a single list.
2. Sort that list in descending order of sweetness (from largest to smallest).
3. Take the first \(K\) elements and output their sum.

all_fruits = elements of A + elements of B
Sort all_fruits in descending order
answer = sum of the first K elements of all_fruits

Complexity

• Time complexity: \(O((N+M) \log(N+M))\)
  • Sorting is the dominant operation. Since \(N + M \leq 150000\), this is sufficiently fast.
• Space complexity: \(O(N+M)\)
  • For the list storing all fruits.

Implementation Notes

• Fast input: Using sys.stdin.read() to read all input at once and splitting with split(). When \(N + M\) is large, this is faster than reading line by line with input().

• Descending sort: By sorting with fruits.sort(reverse=True) and slicing with fruits[:K], the top \(K\) elements can be extracted concisely.

• Overflow of sweetness sum: Each fruit’s sweetness can be up to \(10^9\), and \(K\) can be up to \(150000\), so the total can reach approximately \(1.5 \times 10^{14}\). Python has no integer overflow issues, so there’s nothing to worry about, but if solving in C++ or similar languages, you need to use long long.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    fruits = []
    for i in range(N + M):
        fruits.append(int(input_data[idx])); idx += 1
    
    fruits.sort(reverse=True)
    print(sum(fruits[:K]))

main()

This editorial was generated by claude4.6opus-thinking.