概要

\(N\) 個の既存のフルーツと \(M\) 個の新しいフルーツ、合わせて \(N+M\) 個の中から、甘さが大きい順に \(K\) 個選んだときの合計値を求める問題です。

考察

この問題のポイントは、「どのフルーツが元からあったか、新しく届いたか」を区別する必要がないという点です。

すべてのフルーツを一つのグループとして扱い、その中から単純に甘いもの（値が大きいもの）を \(K\) 個選べば、目的の合計値を得ることができます。

効率的な選び方

「大きい順に \(K\) 個選ぶ」ための最も愚直で確実な方法は、すべてのフルーツを降順（大きい順）に並べ替える（ソートする）ことです。

制約を確認すると、フルーツの総数 \(N+M\) は最大で \(150,000\) 個です。一般的なプログラミング言語のソートアルゴリズムの計算量は \(O(L \log L)\) （\(L\) は要素数）であり、今回のケースでは約 \(1.5 \times 10^5 \times \log(1.5 \times 10^5) \approx 2.5 \times 10^6\) 回程度の計算量となります。これは、一般的な競技プログラミングの制限時間（2秒）内に十分間に合う計算量です。

アルゴリズム

以下の手順で解くことができます。

1. 全てのフルーツの甘さ \(A_1, \dots, A_N\) および \(B_1, \dots, B_M\) を一つのリスト（配列）に格納する。
2. リストを降順（大きい順）にソートする。
3. ソートされたリストの先頭から \(K\) 個の要素を取り出し、その合計を計算する。
4. 計算した合計値を出力する。

計算量

\(L = N + M\) とします。

• 時間計算量: \(O(L \log L)\)
  • 全ての要素の読み込みに \(O(L)\)、ソートに \(O(L \log L)\)、先頭 \(K\) 個の合計計算に \(O(K)\) かかります。全体としてソートの計算量が支配的になります。
• 空間計算量: \(O(L)\)
  • \(N+M\) 個の要素を保持するためのリストが必要です。

実装のポイント

• 高速な入出力: Pythonにおいて、データ件数が \(10^5\) を超えるような場合は、input() を繰り返すよりも sys.stdin.read().split() を使って一括で入力を取得し、数値に変換する方が実行時間を大幅に短縮できます。

• スライスと合計: ソートした後のリストから \(K\) 個選ぶ際は、Pythonのリストのスライス機能 fruits[:k] と sum() 関数を組み合わせることで、簡潔かつ高速に合計を求めることができます。

  ソースコード

import sys

def solve():
    # 全ての入力を一度に読み込み、空白（スペース、タブ、改行）で分割してトークン化します。
    # 150,000個程度のデータ量であれば、この方法がPythonにおいて非常に高速です。
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合、何もせず終了します。
    if not input_data:
        return
    
    # 入力の1行目には N, M, K が含まれています。
    # ここでは、上位 K 個を選ぶための K の値を取得します。
    # N = int(input_data[0])
    # M = int(input_data[1])
    k = int(input_data[2])
    
    # 4番目の要素（インデックス3）以降が全てのフルーツの甘さ Ai および Bj です。
    # これらを整数に変換してリストに格納します。
    fruits = list(map(int, input_data[3:]))
    
    # 甘さの大きい順に並べるため、リストを降順（大きい順）にソートします。
    # Pythonの sort() は非常に高速な Timsort アルゴリズムを使用しています。
    fruits.sort(reverse=True)
    
    # 先頭から K 個の要素（甘さの大きい順に K 個）を取り出し、その合計を計算します。
    # 制約により K <= N + M であることが保証されています。
    result = sum(fruits[:k])
    
    # 合計値を出力します。
    print(result)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。