Overview

This problem asks you to find the sum of the top K satisfaction values (product of deliciousness) among all combinations of snacks and drinks.

Analysis

A naive approach would be to compute the satisfaction for all combinations (\(N \times M\) pairs), sort them, and select the top K. However, since \(N\) and \(M\) can be as large as \(2 \times 10^5\), the number of combinations can reach up to \(4 \times 10^{10}\), making this computationally infeasible.

Therefore, we need an efficient method to explore combinations in order of decreasing satisfaction. By sorting the snacks and drinks each in descending order of deliciousness, we can generate candidate combinations starting from those with the highest satisfaction. Specifically, for each drink, we start with the combination involving the most delicious snack, then manage the next most delicious snack combinations using a priority queue, allowing us to efficiently retrieve the top K values.

Algorithm

1. Sort the snack list \(A\) and the drink list \(B\) each in descending order.
2. Initialize a priority queue (min-heap). Initially, for each drink \(B_j\), add the satisfaction of the combination with the most delicious snack \(A_0\) (i.e., \(A_0 \times B_j\)) to the queue as a negative value (to use the min-heap as a max-heap), along with index information.
3. Pop the combination with the maximum satisfaction from the queue and add it to the running total.
4. If the popped combination has snack index \(i\) and drink index \(j\), add the combination of the next snack at index \(i+1\) with the same drink \(j\) (i.e., \(A_{i+1} \times B_j\)) to the queue.
5. Repeat the above operation K times and output the total.

With this approach, by exploring snacks in descending order of deliciousness for each drink, we can efficiently retrieve the top K values without generating all combinations.

Complexity

• Time complexity: \(O(N \log N + M \log M + K \log M)\)
  • Sorting takes \(O(N \log N + M \log M)\)
  • Priority queue operations take \(O(K \log M)\) (the queue size is at most \(M\))
• Space complexity: \(O(N + M)\)

Implementation Notes

• Use a priority queue as a min-heap, storing negative values to efficiently retrieve the maximum value.

• Store index information along with each combination so that the next candidate can be generated.

• For each drink, manage the index of the current best snack in the queue, and only add the next candidate if the next index exists.

  Source Code

import sys
import heapq

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    K = int(data[2])
    A = list(map(int, data[3:3+n]))
    B = list(map(int, data[3+n:3+n+m]))
    
    A.sort(reverse=True)
    B.sort(reverse=True)
    
    heap = []
    for j in range(m):
        heapq.heappush(heap, (-A[0] * B[j], 0, j))
    
    total = 0
    count = 0
    while count < K and heap:
        val, i, j = heapq.heappop(heap)
        total += -val
        count += 1
        if i + 1 < n:
            heapq.heappush(heap, (-A[i+1] * B[j], i+1, j))
    
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.