Overview

Whether to swap each ingredient can be considered independently. By selecting exactly \(K\) ingredients with the largest “change in value” \(B_i - A_i\), we can maximize the overall deliciousness.

Analysis

The final total deliciousness can be decomposed as follows:

• First, the total when no ingredients are swapped: \(\sum A_i\)
• The change when ingredient \(i\) is swapped: \(B_i - A_i\)

Therefore, if we let \(S\) (\(|S|=K\)) be the set of swapped ingredients,

[ \text{Total deliciousness} = \sum Ai + \sum{i \in S}(B_i - A_i) ]

Since \(\sum A_i\) is constant regardless of the choice, what we need to maximize is
[ \sum_{i \in S}(B_i - A_i) ] In other words, the problem reduces to “selecting \(K\) items with the largest differences \(d_i = B_i - A_i\).”

Why a naive approach doesn’t work

If we enumerate all combinations of choosing \(K\) items from \(N\), the number of cases is \(\binom{N}{K}\), which is extremely large. For \(N \le 3 \times 10^5\), this is far too slow.

How to solve it

Create the difference array \(d_i\), sort it in descending order, and sum the top \(K\) elements.
Even if all differences are negative, we must select exactly \(K\) items, so in that case, choosing the top \(K\) (even at a loss) is the best strategy.

For example,
when \(A=[5,1,4],\ B=[6,-2,10],\ K=2\),
the differences are \([1,-3,6]\). In descending order: \([6,1,-3]\), so the top 2 are \(6,1\).
The base total is \(\sum A_i=10\), so the answer is \(10+6+1=17\).

Algorithm

1. Compute the total of \(A\): base = sum(A).
2. For each \(i\), compute the difference diffs[i] = B_i - A_i.
3. Sort diffs in descending order.
4. Output base + sum(diffs[:K]).

Complexity

• Time complexity: \(O(N \log N)\) (sorting the differences)
• Space complexity: \(O(N)\) (difference array)

Implementation Notes

• Due to the constraints, the total value can become very large, but Python’s int handles arbitrary precision without overflow concerns.

• Since the input can be large, using sys.stdin.readline speeds up reading.

• Using zip(A, B) allows writing \(B_i - A_i\) concisely.

  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)
    diffs = [b - a for a, b in zip(A, B)]
    diffs.sort(reverse=True)

    ans = base + sum(diffs[:K])
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.