Overview

Rather than directly considering “which ingredients to swap,” this problem focuses on how much the overall deliciousness of the dish increases or decreases due to swapping.
For each ingredient, compute the change \(B_i - A_i\), and select exactly \(K\) ingredients with the largest values.

Analysis

First, if we don’t swap any ingredients, the overall deliciousness of the dish is

\[ A_1 + A_2 + \cdots + A_N \]

Now, if we swap the \(i\)-th ingredient, its deliciousness changes from \(A_i\) to \(B_i\).
In other words, the overall deliciousness changes by

\[ B_i - A_i \]

If we think of this value as the “change due to swapping,” the problem can be rephrased as follows:

• The initial total is \(\sum A_i\)
• Add the change \(B_i - A_i\) for each of the \(K\) selected ingredients
• Choose the selection that maximizes the total

Therefore, it is optimal to select the \(K\) ingredients with the largest change values.

Concrete Example

For example, given

• \(A = [5, 3, 8, 4]\)
• \(B = [6, 10, 2, 7]\)
• \(K = 2\)

The initial total is

\[ 5 + 3 + 8 + 4 = 20 \]

The change for each ingredient is

• \(6 - 5 = 1\)
• \(10 - 3 = 7\)
• \(2 - 8 = -6\)
• \(7 - 4 = 3\)

So we have

\[ [1, 7, -6, 3] \]

Selecting the \(2\) largest values gives \(7, 3\), so the maximum value is

\[ 20 + 7 + 3 = 30 \]

Why the Naive Approach Fails

If we try all ways to choose \(K\) items from \(N\), the number of combinations is

\[ \binom{N}{K} \]

which is far too large to handle when \(N \leq 3 \times 10^5\).

Instead, by viewing each ingredient independently and expressing its “swapping value” as \(B_i - A_i\), we can reformulate the problem as taking the top \(K\) items by value, which can be solved efficiently.

Also, it is not a problem if some change values are negative.
This is because the problem requires swapping exactly \(K\) ingredients, so even if some swaps result in a loss, we must choose the ones that minimize that loss.
“Selecting the top \(K\) in descending order” naturally handles this condition as well.

Algorithm

1. Compute the original overall deliciousness \(base = \sum A_i\)
2. Compute the change for each ingredient \(diff_i = B_i - A_i\)
3. Sort \(diff\) in descending order
4. Add the sum of the top \(K\) values to \(base\)
5. Output that value

The corresponding parts in the code are:

• base = sum(A)
  The original total
• diff = [b - a for a, b in zip(A, B)]
  The change for each ingredient
• diff.sort(reverse=True)
  Sort in descending order
• base + sum(diff[:K])
  Add the top \(K\) values to get the answer

Complexity

• Time complexity: \(O(N \log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Organizing the solution as “initial total + top \(K\) change values” makes it easy to implement.

• The change values can be negative, but since we must select exactly \(K\) items, we can simply use the top \(K\) values as-is.

• \(A_i\) and \(B_i\) can include negative values, and the total can become large, but Python’s integers handle this safely.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    base = sum(A)
    diff = [b - a for a, b in zip(A, B)]
    diff.sort(reverse=True)
    
    print(base + sum(diff[:K]))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.