概要

お菓子の美味しさ配列 \(A\) と飲み物の美味しさ配列 \(B\) からできる全 \(N\times M\) 個の積 \(A_iB_j\) のうち、大きい方から \(K\) 個を取り、その合計を求めます。

考察

素朴に全ての組み合わせ \(N\times M\) 個の積を作って並べ替えると、最大で \((2\times 10^5)^2=4\times 10^{10}\) 個になり、生成だけで不可能（TLE・メモリ不足）です。

ここで重要な観察は次の通りです。

• \(A\) と \(B\) を降順にソートすると、固定した \(i\) に対して
  $\(A_iB_0,\ A_iB_1,\ \dots,\ A_iB_{M-1}\)\( は **左から右へ非増加（大きい→小さい）** になります（\)B$ が降順なので）。
• つまり、各 \(i\) について「降順に並んだ列（または行）」が \(N\) 本あるとみなせます。
• 求めたいのは、これら \(N\) 本の降順列をまとめたときの「全体の上位 \(K\) 個」。

これは「\(N\) 本の降順列から大きいものを順に取り出す」問題なので、優先度付きキュー（ヒープ）での \(K\) 回取り出し（いわゆる k-way merge）が有効です。

さらに、ヒープに入れる要素数は「列の本数」に比例するため、\(N\) と \(M\) のうち 小さい方を列の本数にすると高速・省メモリになります（コードの if len(A) > len(B): A,B = B,A）。

アルゴリズム

1. \(A\) と \(B\) をそれぞれ降順にソートする。
2. ヒープには「各 \(i\) の列の先頭要素」だけを入れる：
   • 具体的に、各 \(i\) について \((A_iB_0, i, 0)\) を入れる。
     （Python の heapq は最小ヒープなので、値を負にして最大ヒープ相当にする）
3. 次を \(K\) 回繰り返す：
   • ヒープから現在最大の積 \((A_iB_j)\) を取り出し、答えに加算する。
   • 同じ \(i\) の次の要素 \(A_iB_{j+1}\) が存在するなら、それをヒープに追加する。
     • こうすると、その列からは常に「まだ取り出していない中で最大の候補」だけがヒープに載り続ける。

小さな例

\(A=[5,3]\), \(B=[4,2,1]\)（すでに降順）とすると、各列は - \(i=0\): \(20,10,5\) - \(i=1\): \(12,6,3\)

ヒープ初期：\(20(i=0,j=0),\ 12(i=1,j=0)\)
取り出し順は \(20 \to 12 \to 10 \to 6 \to 5 \to 3 \dots\) と、全体の大きい順を正しく生成できます。

計算量

• 時間計算量:
  ソートが \(O(N\log N + M\log M)\)、ヒープ操作が初期化 \(O(\min(N,M))\) と \(K\) 回の push/pop で \(O(K\log \min(N,M))\)。
  よって全体で
  $\(O(N\log N + M\log M + K\log \min(N,M))\)$
• 空間計算量:
  ヒープのサイズは最大で \(\min(N,M)\) 個なので
  $\(O(\min(N,M))\)$

実装のポイント

• heapq は最小ヒープなので、最大値を取り出すために積にマイナスを付けて管理します（(-value, i, j)）。

• ヒープの要素数を抑えるため、配列の長い方を \(B\) 側（列の横方向）に回すように入れ替えています。

• 積や合計は最大で \(10^5 \times 10^5 \times 2\times 10^5=2\times 10^{15}\) 程度になりうるので、Python の int（任意精度）で安全です。

• 入力が大きいので sys.stdin.buffer.read() による高速入力を使っています。

  ソースコード

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M, K = data[0], data[1], data[2]
    A = data[3:3 + N]
    B = data[3 + N:3 + N + M]

    A.sort(reverse=True)
    B.sort(reverse=True)

    if len(A) > len(B):
        A, B = B, A

    a_len = len(A)
    b_len = len(B)

    heap = [(-A[i] * B[0], i, 0) for i in range(a_len)]
    heapq.heapify(heap)

    ans = 0
    for _ in range(K):
        neg_val, i, j = heapq.heappop(heap)
        ans += -neg_val
        j += 1
        if j < b_len:
            heapq.heappush(heap, (-A[i] * B[j], i, j))

    print(ans)

if __name__ == "__main__":
    main()

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