Overview

Given a snack tastiness array \(A\) and a drink tastiness array \(B\), among all \(N\times M\) products \(A_iB_j\), we take the \(K\) largest ones and find their sum.

Analysis

Naively generating and sorting all \(N\times M\) combinations would result in up to \((2\times 10^5)^2=4\times 10^{10}\) elements, making even generation alone impossible (TLE / memory limit exceeded).

The key observation is as follows:

• If we sort \(A\) and \(B\) in descending order, then for a fixed \(i\),
  $\(A_iB_0,\ A_iB_1,\ \dots,\ A_iB_{M-1}\)\( is **non-increasing from left to right (large → small)** (since \)B$ is in descending order).
• In other words, for each \(i\), we can think of it as having \(N\) “rows (or columns) sorted in descending order.”
• What we want is the “top \(K\) elements overall” when combining these \(N\) descending sequences.

This is a problem of “extracting the largest elements in order from \(N\) descending sequences,” so extracting \(K\) times using a priority queue (heap) (a so-called k-way merge) is effective.

Furthermore, since the number of elements in the heap is proportional to the “number of sequences,” making the smaller of \(N\) and \(M\) the number of sequences results in faster execution and less memory usage (the if len(A) > len(B): A,B = B,A in the code).

Algorithm

1. Sort \(A\) and \(B\) each in descending order.
2. Insert only the “first element of each sequence \(i\)” into the heap:
   • Specifically, for each \(i\), insert \((A_iB_0, i, 0)\).
     (Since Python’s heapq is a min-heap, we negate the values to simulate a max-heap)
3. Repeat the following \(K\) times:
   • Extract the current maximum product \((A_iB_j)\) from the heap and add it to the answer.
   • If the next element \(A_iB_{j+1}\) in the same sequence \(i\) exists, add it to the heap.
     • This way, only the “largest candidate not yet extracted” from each sequence remains in the heap at all times.

Small Example

Given \(A=[5,3]\), \(B=[4,2,1]\) (already in descending order), each sequence is: - \(i=0\): \(20,10,5\) - \(i=1\): \(12,6,3\)

Initial heap: \(20(i=0,j=0),\ 12(i=1,j=0)\)
The extraction order is \(20 \to 12 \to 10 \to 6 \to 5 \to 3 \dots\), correctly generating the overall descending order.

Complexity

• Time complexity:
  Sorting is \(O(N\log N + M\log M)\), heap operations consist of initialization \(O(\min(N,M))\) and \(K\) push/pop operations at \(O(K\log \min(N,M))\).
  Therefore, the overall complexity is
  $\(O(N\log N + M\log M + K\log \min(N,M))\)$
• Space complexity:
  The heap size is at most \(\min(N,M)\) elements, so
  $\(O(\min(N,M))\)$

Implementation Notes

• Since heapq is a min-heap, we negate the product values to extract the maximum ((-value, i, j)).

• To keep the number of heap elements small, we swap the arrays so that the longer one becomes the \(B\) side (the horizontal direction of the sequences).

• Products and sums can be as large as \(10^5 \times 10^5 \times 2\times 10^5=2\times 10^{15}\), so Python’s int (arbitrary precision) handles this safely.

• Since the input is large, we use sys.stdin.buffer.read() for fast input.

  Source Code

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()

This editorial was generated by gpt-5.2-high.