Overview

Given \(N\) ingredients, you must choose exactly \(K\) of them to replace with substitute ingredients, maximizing the total deliciousness. For each ingredient, compute the “gain from replacement,” then greedily select the \(K\) ingredients with the largest gains.

Analysis

Rephrasing the Problem

First, the total deliciousness of the dish without any replacements is \(\sum_{i=1}^{N} A_i\).

If you replace the \(i\)-th ingredient, the change in deliciousness (gain) is:

\[d_i = B_i - A_i\]

• If \(d_i > 0\), replacing increases the deliciousness
• If \(d_i < 0\), replacing decreases the deliciousness
• If \(d_i = 0\), there is no change

Since exactly \(K\) ingredients must be replaced, the final deliciousness can be expressed as:

\[\sum_{i=1}^{N} A_i + \sum_{i \in S} d_i\]

where \(S\) is the set of \(K\) ingredients chosen for replacement.

Strategy for Maximization

Since \(\sum A_i\) is fixed, we only need to maximize \(\sum_{i \in S} d_i\) (the total gain of the chosen \(K\) ingredients).

This is simply achieved by sorting \(d_i\) in descending order and selecting the top \(K\) values.

Important Note

Since exactly \(K\) ingredients must be replaced, you need to select \(K\) ingredients even if some gains are negative. For example, if \(N=3, K=2\) and \(d = [5, -1, -3]\), you must choose \(d_1 = 5\) and \(d_2 = -1\), giving a total gain of \(5 + (-1) = 4\).

Concrete Example

For \(N=3, K=2, A=[10, 20, 30], B=[15, 5, 35]\):

• \(d = [15-10, \ 5-20, \ 35-30] = [5, -15, 5]\)
• Sorted in descending order: \([5, 5, -15]\)
• Sum of top \(K=2\) values: \(5 + 5 = 10\)
• Answer: \((10+20+30) + 10 = 70\)

Algorithm

1. Compute the total sum \(\text{total} = \sum_{i=1}^{N} A_i\).
2. For each \(i\), compute the gain \(d_i = B_i - A_i\).
3. Sort \(d_i\) in descending order.
4. Add the top \(K\) values of \(d_i\) to \(\text{total}\).
5. Output the result.

Complexity

• Time complexity: \(O(N \log N)\) (sorting is the bottleneck)
• Space complexity: \(O(N)\) (to store the gain array)

Implementation Notes

• The deliciousness values \(A_i, B_i\) range from \(-10^9\) to \(10^9\), and \(N\) can be up to \(3 \times 10^5\), so the total sum can reach approximately \(3 \times 10^{14}\). Python handles arbitrary-precision integers so there is no overflow concern, but in C++ and similar languages, you need to use long long.

• Be careful not to overlook the constraint that “exactly \(K\) ingredients must be replaced.” There may be cases where you must select ingredients even with negative gains.

• By reading all input at once with sys.stdin.read(), you can process input efficiently even in Python.

  Source Code

def main():
    import sys
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    A = [int(input_data[idx + i]) for i in range(N)]; idx += N
    B = [int(input_data[idx + i]) for i in range(N)]; idx += N
    
    # diff[i] = B[i] - A[i], the gain from swapping ingredient i
    # We want to choose exactly K ingredients to swap to maximize sum(A) + sum of K chosen diffs
    # To maximize, we sort diffs in descending order and pick the top K
    # But we MUST pick exactly K, so even if some diffs are negative, we must pick them
    
    total = sum(A)
    diffs = [B[i] - A[i] for i in range(N)]
    diffs.sort(reverse=True)
    total += sum(diffs[:K])
    print(total)

main()

---

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