Problem: The Patisserie AtCoder sells cakes with number-shaped candles. There are X, Y and Z kinds of cakes with 1-shaped, 2-shaped and 3-shaped candles, respectively. Each cake has an integer value called _deliciousness_ , as follows:    * The deliciousness of the cakes with 1-shaped candles are A_1, A_2, ..., A_X.   * The deliciousness of the cakes with 2-shaped candles are B_1, B_2, ..., B_Y.   * The deliciousness of the cakes with 3-shaped candles are C_1, C_2, ..., C_Z.  Takahashi decides to buy three cakes, one for each of the three shapes of the candles, to celebrate ABC 123.   There are X \times Y \times Z such ways to choose three cakes.   We will arrange these X \times Y \times Z ways in descending order of the sum of the deliciousness of the cakes.   Print the sums of the deliciousness of the cakes for the first, second, ..., K-th ways in this list.

Submission attempts (in order):
from heapq import heappush, heappop
from collections import defaultdict


def main():
    X, Y, Z, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    B = list(map(int, input().split(' ')))
    C = list(map(int, input().split(' ')))
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)
    que = [(- A[0] - B[0] - C[0], 0, 0, 0)]  # multiply -1 to change min to max
    already_inserted = defaultdict(int)
    answer = list()
    for _ in range(K):
        q, i, j, k = heappop(que)
        answer.append(-q)
        if i + 1 < X:
            item_a = (- A[i + 1] - B[j] - C[k], i + 1, j, k)
            if already_inserted[item_a] == 0:
                heappush(que, item_a)
        if j + 1 < Y:
            item_b = (- A[i] - B[j + 1] - C[k], i, j + 1, k)
            if already_inserted[item_b] == 0:
                heappush(que, item_b)
        if k + 1 < Z:
            item_c = (- A[i] - B[j] - C[k + 1], i, j, k + 1)
            if already_inserted[item_c] == 0:
                heappush(que, item_c)
    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()

from heapq import heappush, heappop
from collections import defaultdict


def main():
    X, Y, Z, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    B = list(map(int, input().split(' ')))
    C = list(map(int, input().split(' ')))
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)
    que = [(- A[0] - B[0] - C[0], 0, 0, 0)]  # multiply -1 to change min to max
    already_inserted = defaultdict(int)
    answer = list()
    for _ in range(K):
        q, i, j, k = heappop(que)
        answer.append(-q)
        if i + 1 < X:
            item_a = (- A[i + 1] - B[j] - C[k], i + 1, j, k)
            if already_inserted[item_a] == 0:
                heappush(que, item_a)
                already_inserted[item_a] = 1
        if j + 1 < Y:
            item_b = (- A[i] - B[j + 1] - C[k], i, j + 1, k)
            if already_inserted[item_b] == 0:
                heappush(que, item_b)
                already_inserted[item_b] = 1
        if k + 1 < Z:
            item_c = (- A[i] - B[j] - C[k + 1], i, j, k + 1)
            if already_inserted[item_c] == 0:
                heappush(que, item_c)
                already_inserted[item_c] = 1
    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()

Verdicts: Wrong Answer

Accepted