概要

全フルーツ（既存 \(N\) 個 + 新規 \(M\) 個）の甘さをまとめて、大きい順に並べたときの先頭 \(K\) 個の合計を求める問題です。
つまり「上位 \(K\) 個を選ぶ」操作をそのまま実装すれば解けます。

考察

重要な観察は次の1点です。

• もともとのフルーツか新しく来たフルーツかは関係なく、選ぶ基準は「甘さの大きさだけ」

したがって、配列 \(A\) と \(B\) を別々に扱う必要はありません。
全部を1つの配列に入れて降順ソートし、先頭 \(K\) 個を足すのが最も素直です。

素朴なアプローチとの比較

• 例えば「毎回最大値を1個ずつ探して \(K\) 回足す」という方法だと、1回探すのに \(O(N+M)\) かかるため、全体で \(O(K(N+M))\) となり非効率です。
• 制約は \(N+M \le 150000\) なので、全体を1回ソートする \(O((N+M)\log(N+M))\) なら十分高速です。

具体例

たとえば
\(A = [5, 1, 4],\ B = [3, 10],\ K=3\) のとき、
まとめると \([5,1,4,3,10]\)、降順で \([10,5,4,3,1]\)。
先頭3個の合計は \(10+5+4=19\) です。

アルゴリズム

1. \(N, M, K\) を読む。
2. 続く \(N+M\) 行の甘さを1つの配列 vals に読む。
3. vals を降順にソートする。
4. vals[:K] の総和を出力する。

提示コードはこの手順をそのまま実装しています。

計算量

• 時間計算量: \(O((N+M)\log(N+M))\)（ソートが支配的）
• 空間計算量: \(O(N+M)\)（全要素を配列に保持）

実装のポイント

• 入力行数が多いので sys.stdin.readline を使うと安定して高速です。

• Python では vals.sort(reverse=True) と sum(vals[:K]) で簡潔に書けます。

• 合計値は最大で \(K \times 10^9\) 程度ですが、Python の整数はオーバーフローしないので安心です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    vals = [int(input()) for _ in range(N + M)]
    vals.sort(reverse=True)
    print(sum(vals[:K]))

if __name__ == "__main__":
    main()

この解説は gpt-5.3-codex によって生成されました。