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 heappop, heappush

X, Y, Z, K = [int(s) for s in input().split()]
A = [int(s) for s in input().split()]
B = [int(s) for s in input().split()]
C = [int(s) for s in input().split()]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
a, b, c = 1, 1, 1
while a * b  < K or a * c < K or b * c < K:
    da = A[a-1] - A[a] if X > a else float('Inf')
    db = B[b-1] - B[b] if Y > b else float('Inf')
    dc = C[c-1] - C[c] if Z > c else float('Inf')
    if da <= db and da <= dc:
        a += 1
    elif db <= da and db <= dc:
        b += 1
    else:
        c += 1
print(a, b, c)
h = []
for i in range(a):
    for j in range(b):
        for k in range(c):
            heappush(h, -(A[i] + B[j] + C[k]))
for _ in range(K):
    print(-heappop(h))


from heapq import heappop, heappush

X, Y, Z, K = [int(s) for s in input().split()]
A = [int(s) for s in input().split()]
B = [int(s) for s in input().split()]
C = [int(s) for s in input().split()]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
a, b, c = 1, 1, 1
while (a * b * c) / max(a, b, c) <= K:
    da = A[a-1] - A[a] if X > a else float('Inf')
    db = B[b-1] - B[b] if Y > b else float('Inf')
    dc = C[c-1] - C[c] if Z > c else float('Inf')
    if da <= db and da <= dc:
        a += 1
    elif db <= da and db <= dc:
        b += 1
    else:
        c += 1
h = []
for i in range(a):
    for j in range(b):
        for k in range(c):
            heappush(h, -(A[i] + B[j] + C[k]))
for _ in range(K):
    print(-heappop(h))


from heapq import heappop, heappush

X, Y, Z, K = [int(s) for s in input().split()]
A = [int(s) for s in input().split()]
B = [int(s) for s in input().split()]
C = [int(s) for s in input().split()]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
counted = set()
h = [(-(A[0] + B[0] + C[0]), 0, 0, 0)]
for _ in range(K):
    s, i, j, k = heappop(h)
    print(-s)
    if X > i+1 and (i+1, j, k) not in counted:
        heappush(h, (-(A[i+1] + B[j] + C[k]), i+1, j, k))
        counted.add((i+1, j, k))
    if Y > j+1 and (i, j+1, k) not in counted:
        heappush(h, (-(A[i] + B[j+1] + C[k]), i, j+1, k))
        counted.add((i, j+1, k))
    if Z > k+1 and (i, j, k+1) not in counted:
        heappush(h, (-(A[i] + B[j] + C[k+1]), i, j, k+1))
        counted.add((i, j, k+1))
    

Verdicts: Wrong Answer

Wrong Answer

Accepted