Overview

Given \(N\) ingredients, the problem asks to replace exactly \(K\) of them with substitute ingredients to maximize the total deliciousness. By focusing on the “change in deliciousness” caused by each replacement, we can efficiently find the optimal combination.

Analysis

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

When ingredient \(i\) is replaced, its deliciousness changes from \(A_i\) to \(B_i\). The total deliciousness of the dish changes as follows: - Change amount: \(D_i = B_i - A_i\) - Total after replacement: (original total) \(+ D_i\)

For example, if \(A_i = 10, B_i = 15\), the change amount is \(+5\). Conversely, if \(A_i = 10, B_i = 7\), the change amount is \(-3\).

Since this problem requires replacing exactly \(K\) ingredients, to maximize the total deliciousness, the best strategy is to select and replace the \(K\) ingredients with the largest change amounts \(D_i\). Even if the change amount is negative (replacing would decrease deliciousness), if it falls within the top \(K\), it must be replaced due to the rule of selecting exactly \(K\) ingredients.

Algorithm

1. For all ingredients \(i = 1, \ldots, N\), compute the change amount from replacement: \(D_i = B_i - A_i\).
2. Sort the \(N\) computed change amounts in descending order (largest first).
3. Add the sum of the first \(K\) change amounts from the sorted list to the original total deliciousness \(\sum A_i\).
   • Expressed as a formula: Maximum value \(= \sum_{i=1}^{N} A_i + (\text{sum of the top } K \text{ values of } D_i)\)

Complexity

Let \(N\) be the number of ingredients. - Time complexity: \(O(N \log N)\) - Computing the change amounts takes \(O(N)\), sorting takes \(O(N \log N)\), and computing the total takes \(O(N)\), so the overall complexity is dominated by sorting. - For \(N = 3 \times 10^5\), this comfortably fits within the time limit. - Space complexity: \(O(N)\) - \(O(N)\) memory is used to store the input data (\(A_i, B_i\)) and the change amounts (\(D_i\)).

Implementation Notes

• Fast I/O: Since \(N\) can be as large as \(3 \times 10^5\), which is relatively large, in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar methods.

• Sort order: Since we want to select the largest change amounts first, either specify sort(reverse=True), or sort in ascending order and take the last \(K\) elements from the end.

• Exactly K items: If the condition were “at most \(K\)”, we would only select those with positive change amounts. However, since the condition is “exactly \(K\)”, we must always select exactly \(K\) items.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白文字で分割してリストにする
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 食材の数 N と入れ替える食材の数 K を取得
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 現在の食材のおいしさ A_i と入れ替え後の食材のおいしさ B_i を取得
    # input_data[2...n+1] が A_1...A_n
    # input_data[n+2...2n+1] が B_1...B_n
    a = list(map(int, input_data[2:n+2]))
    b = list(map(int, input_data[n+2:2*n+2]))
    
    # 各食材を入れ替えたときのおいしさの変化量 (B_i - A_i) を計算
    diffs = [b[i] - a[i] for i in range(n)]
    
    # 変化量を降順（大きい順）にソート
    # 料理全体のおいしさを最大化するためには、変化量が大きいものから K 個選んで入れ替える
    diffs.sort(reverse=True)
    
    # 元のおいしさの総和に、上位 K 個の変化量を加算することで最大のおいしさを求める
    # ちょうど K 個入れ替えるという条件があるため、上位 K 個をそのまま合計する
    ans = sum(a) + sum(diffs[:k])
    
    # 結果を出力
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.