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):
a, b, c, d = map(int, input().split())
al = list(map(int, input().split()))
bl = list(map(int, input().split()))
cl = list(map(int, input().split()))
al = sorted(al, reverse=True)
bl = sorted(bl, reverse=True)
cl = sorted(cl, reverse=True)
q = [[al[0] + bl[0] + cl[0], 0, 0, 0]]
ans = [[al[0] + bl[0] + cl[0], 0, 0, 0]]
c = 0
while True:
    c += 1

    print(c)
    #print(len(ans))
    s, aq, bq, cq = map(int, q.pop())
    if len(al) > aq+1:
        if [al[aq+1] + bl[bq] + cl[cq], aq+1, bq, cq] not in ans:
            q.append([al[aq+1] + bl[bq] + cl[cq], aq+1, bq, cq])
            ans.append([al[aq+1] + bl[bq] + cl[cq], aq+1, bq, cq])

    if len(bl) > bq+1:
        if [al[aq] + bl[bq+1] + cl[cq], aq, bq+1, cq] not in ans:
            q.append([al[aq] + bl[bq+1] + cl[cq], aq, bq+1, cq])
            ans.append([al[aq] + bl[bq+1] + cl[cq], aq, bq+1, cq])

    if len(cl) > cq+1:
        if [al[aq] + bl[bq] + cl[cq+1], aq, bq, cq+1] not in ans:
            q.append([al[aq] + bl[bq] + cl[cq+1], aq, bq, cq+1])
            ans.append([al[aq] + bl[bq] + cl[cq+1], aq, bq, cq+1])

    q = sorted(q)

    if len(ans) > d:
        ans = sorted(ans, reverse=True)
        if ans[d-2][0] > q[len(q)-1][0]:
            break

ans = sorted(ans, reverse=True)
print(len(ans))
for i in range(d):
    print(ans[i][0])

import heapq
a, b, c, d = map(int, input().split())
al = list(map(int, input().split()))
bl = list(map(int, input().split()))
cl = list(map(int, input().split()))
al = sorted(al, reverse=True)
bl = sorted(bl, reverse=True)
cl = sorted(cl, reverse=True)
q = []
heapq.heappush(q, [-(al[0] + bl[0] + cl[0]), 0, 0, 0])
ans = []
heapq.heappush(ans, [-(al[0] + bl[0] + cl[0]), 0, 0, 0])

while True:

    s, aq, bq, cq = heapq.heappop(q)
    if len(al) > aq+1:
        if [-(al[aq+1] + bl[bq] + cl[cq]), aq+1, bq, cq] not in ans:
            heapq.heappush(q, [-(al[aq+1] + bl[bq] + cl[cq]), aq+1, bq, cq])
            heapq.heappush(ans, [-(al[aq+1] + bl[bq] + cl[cq]), aq+1, bq, cq])
            
            

    if len(bl) > bq+1:
        if [-(al[aq] + bl[bq+1] + cl[cq]), aq, bq+1, cq] not in ans:
            heapq.heappush(q, [-(al[aq] + bl[bq+1] + cl[cq]), aq, bq+1, cq])
            heapq.heappush(ans, [-(al[aq] + bl[bq+1] + cl[cq]), aq, bq+1, cq])
            
            

    if len(cl) > cq+1:
        if [-(al[aq] + bl[bq] + cl[cq+1]), aq, bq, cq+1] not in ans:
            heapq.heappush(q, [-(al[aq] + bl[bq] + cl[cq+1]), aq, bq, cq+1])
            heapq.heappush(ans, [-(al[aq] + bl[bq] + cl[cq+1]), aq, bq, cq+1])
            
            

    #q = sorted(q)

    if len(ans) > d:
        ans = sorted(ans, reverse=True)
        if ans[d][0] > q[len(q)-1][0]:
            break

for i in range(d):
    print(-heapq.heappop(ans)[0])


a, b, c, d = map(int, input().split())
al = list(map(int, input().split()))
bl = list(map(int, input().split()))
cl = list(map(int, input().split()))
al = sorted(al, reverse=True)
bl = sorted(bl, reverse=True)
cl = sorted(cl, reverse=True)
q = [[al[0] + bl[0] + cl[0], 0, 0, 0]]
ans = [[al[0] + bl[0] + cl[0], 0, 0, 0]]
c = -1
while True:
    c += 1

    print(c)
    #print(len(ans))
    s, aq, bq, cq = map(int, q.pop())
    if len(al) > aq+1:
        if [al[aq+1] + bl[bq] + cl[cq], aq+1, bq, cq] not in ans:
            q.append([al[aq+1] + bl[bq] + cl[cq], aq+1, bq, cq])
            ans.append([al[aq+1] + bl[bq] + cl[cq], aq+1, bq, cq])

    if len(bl) > bq+1:
        if [al[aq] + bl[bq+1] + cl[cq], aq, bq+1, cq] not in ans:
            q.append([al[aq] + bl[bq+1] + cl[cq], aq, bq+1, cq])
            ans.append([al[aq] + bl[bq+1] + cl[cq], aq, bq+1, cq])

    if len(cl) > cq+1:
        if [al[aq] + bl[bq] + cl[cq+1], aq, bq, cq+1] not in ans:
            q.append([al[aq] + bl[bq] + cl[cq+1], aq, bq, cq+1])
            ans.append([al[aq] + bl[bq] + cl[cq+1], aq, bq, cq+1])

    q = sorted(q)

    if len(ans) > d:
        ans = sorted(ans, reverse=True)
        if ans[d-1][0] > q[len(q)-1][0]:
            break

ans = sorted(ans, reverse=True)
for i in range(d):
    print(ans[i][0])


a, b, c, d = map(int, input().split())
al = list(map(int, input().split()))
bl = list(map(int, input().split()))
cl = list(map(int, input().split()))
al = sorted(al, reverse=True)
bl = sorted(bl, reverse=True)
cl = sorted(cl, reverse=True)
ad = [al[i] - al[i-1] for i in range(1, len(al))]
ad.insert(0, 0)
ad.append(-(10**15))
bd = [bl[i] - bl[i-1] for i in range(1, len(al))]
bd.insert(0, 0)
bd.append(-(10**15))
cd = [cl[i] - cl[i-1] for i in range(1, len(al))]
cd.insert(0, 0)
cd.append(-(10**15))
q = [[al[0] + bl[0] + cl[0], 0, 0, 0]]
ans = [[al[0] + bl[0] + cl[0], 0, 0, 0]]
while True:
    q = sorted(q)
    score, aq, bq, cq = map(int, q.pop())
    if [score + ad[aq+1], aq+1, bq, cq] not in ans:
        q.append([score + ad[aq+1], aq+1, bq, cq])
        ans.append([score + ad[aq+1], aq+1, bq, cq])
    if [score + bd[bq+1], aq, bq+1, cq] not in ans:
        q.append([score + bd[bq+1], aq, bq+1, cq])
        ans.append([score + bd[bq+1], aq, bq+1, cq])
    if [score + cd[cq+1], aq, bq, cq+1] not in ans:
        q.append([score + cd[cq+1], aq, bq, cq+1])
        ans.append([score + cd[cq+1], aq, bq, cq+1])

    ans = sorted(ans, reverse=True)
    q = sorted(q, reverse=True)

    if len(ans) > d:
        if ans[d] > q[0]:
            break

ans = sorted(ans, reverse=True)
for i in range(d):
    print(ans[i][0])


import heapq
a, b, c, d = map(int, input().split())
al = list(map(int, input().split()))
bl = list(map(int, input().split()))
cl = list(map(int, input().split()))
al = sorted(al, reverse=True)
bl = sorted(bl, reverse=True)
cl = sorted(cl, reverse=True)
q = []
heapq.heappush(q, [-(al[0] + bl[0] + cl[0]), 0, 0, 0])
ans = []
heapq.heappush(ans, [-(al[0] + bl[0] + cl[0]), 0, 0, 0])

while True:

    s, aq, bq, cq = heapq.heappop(q)
    if len(al) > aq+1:
        if [-(al[aq+1] + bl[bq] + cl[cq]), aq+1, bq, cq] not in ans:
            heapq.heappush(q, [-(al[aq+1] + bl[bq] + cl[cq]), aq+1, bq, cq])
            heapq.heappush(ans, [-(al[aq+1] + bl[bq] + cl[cq]), aq+1, bq, cq])
            
            

    if len(bl) > bq+1:
        if [-(al[aq] + bl[bq+1] + cl[cq]), aq, bq+1, cq] not in ans:
            heapq.heappush(q, [-(al[aq] + bl[bq+1] + cl[cq]), aq, bq+1, cq])
            heapq.heappush(ans, [-(al[aq] + bl[bq+1] + cl[cq]), aq, bq+1, cq])
            
            

    if len(cl) > cq+1:
        if [-(al[aq] + bl[bq] + cl[cq+1]), aq, bq, cq+1] not in ans:
            heapq.heappush(q, [-(al[aq] + bl[bq] + cl[cq+1]), aq, bq, cq+1])
            heapq.heappush(ans, [-(al[aq] + bl[bq] + cl[cq+1]), aq, bq, cq+1])
            
            

    #q = sorted(q)

    if len(ans) > d:
       ans = sorted(ans, reverse=True)
        if ans[d][0] > q[len(q)-1][0]:
            break

for i in range(d):
    print(-heapq.heappop(ans)[0])


a, b, c, d = map(int, input().split())
al = list(map(int, input().split()))
bl = list(map(int, input().split()))
cl = list(map(int, input().split()))
al = sorted(al, reverse=True)
bl = sorted(bl, reverse=True)
cl = sorted(cl, reverse=True)
ad = [al[i] - al[i-1] for i in range(1, len(al))]
ad.insert(0, 0)
bd = [bl[i] - bl[i-1] for i in range(1, len(al))]
bd.insert(0, 0)
cd = [cl[i] - cl[i-1] for i in range(1, len(al))]
cd.insert(0, 0)
q = [[al[0] + bl[0] + cl[0], 0, 0, 0]]
ans = [[al[0] + bl[0] + cl[0], 0, 0, 0]]
while True:
    q = sorted(q)
    score, aq, bq, cq = map(int, q.pop())
    if len(ad) > aq+1:
        if [score + ad[aq+1], aq+1, bq, cq] not in ans:
            q.append([score + ad[aq+1], aq+1, bq, cq])
            ans.append([score + ad[aq+1], aq+1, bq, cq])
    if len(bd) > aq + 1:
        if [score + bd[bq+1], aq, bq+1, cq] not in ans:
            q.append([score + bd[bq+1], aq, bq+1, cq])
            ans.append([score + bd[bq+1], aq, bq+1, cq])
    if len(cd) > aq + 1:
        if [score + cd[cq+1], aq, bq, cq+1] not in ans:
            q.append([score + cd[cq+1], aq, bq, cq+1])
            ans.append([score + cd[cq+1], aq, bq, cq+1])

    ans = sorted(ans, reverse=True)
    q = sorted(q, reverse=True)
    if len(ans) > d:
        if ans[d] > q[0]:
            break

ans = sorted(ans, reverse=True)
for i in range(d):
    print(ans[i][0])


a, b, c, d = map(int, input().split())
al = list(map(int, input().split()))
bl = list(map(int, input().split()))
cl = list(map(int, input().split()))
al = sorted(al, reverse=True)
bl = sorted(bl, reverse=True)
cl = sorted(cl, reverse=True)
q = [[al[0] + bl[0] + cl[0], 0, 0, 0]]
ans = [[al[0] + bl[0] + cl[0], 0, 0, 0]]
c = -1
while True:
    #c += 1

    #print(c)
    #print(len(ans))
    s, aq, bq, cq = map(int, q.pop())
    if len(al) > aq+1:
        if [al[aq+1] + bl[bq] + cl[cq], aq+1, bq, cq] not in ans:
            q.append([al[aq+1] + bl[bq] + cl[cq], aq+1, bq, cq])
            ans.append([al[aq+1] + bl[bq] + cl[cq], aq+1, bq, cq])

    if len(bl) > bq+1:
        if [al[aq] + bl[bq+1] + cl[cq], aq, bq+1, cq] not in ans:
            q.append([al[aq] + bl[bq+1] + cl[cq], aq, bq+1, cq])
            ans.append([al[aq] + bl[bq+1] + cl[cq], aq, bq+1, cq])

    if len(cl) > cq+1:
        if [al[aq] + bl[bq] + cl[cq+1], aq, bq, cq+1] not in ans:
            q.append([al[aq] + bl[bq] + cl[cq+1], aq, bq, cq+1])
            ans.append([al[aq] + bl[bq] + cl[cq+1], aq, bq, cq+1])

    q = sorted(q)

    if len(ans) > d:
        ans = sorted(ans, reverse=True)
        if ans[d-1][0] > q[len(q)-1][0]:
            break

ans = sorted(ans, reverse=True)
for i in range(d):
    print(ans[i][0])


import heapq
a, b, c, d = map(int, input().split())
al = list(map(int, input().split()))
bl = list(map(int, input().split()))
cl = list(map(int, input().split()))
al = sorted(al, reverse=True)
bl = sorted(bl, reverse=True)
cl = sorted(cl, reverse=True)
q = [[-(al[0] + bl[0] + cl[0]), 0, 0, 0]]
ans = [[-(al[0] + bl[0] + cl[0]), 0, 0, 0]]
heapq.heapify(q)
heapq.heapify(ans)

#while True:
for i in range(d):
    s, aq, bq, cq = heapq.heappop(q)
    if len(al) > aq+1:
        if [-(al[aq+1] + bl[bq] + cl[cq]), aq+1, bq, cq] not in ans:
            heapq.heappush(q, [-(al[aq+1] + bl[bq] + cl[cq]), aq+1, bq, cq])
            heapq.heappush(ans, [-(al[aq+1] + bl[bq] + cl[cq]), aq+1, bq, cq])
            
            

    if len(bl) > bq+1:
        if [-(al[aq] + bl[bq+1] + cl[cq]), aq, bq+1, cq] not in ans:
            heapq.heappush(q, [-(al[aq] + bl[bq+1] + cl[cq]), aq, bq+1, cq])
            heapq.heappush(ans, [-(al[aq] + bl[bq+1] + cl[cq]), aq, bq+1, cq])
            
            

    if len(cl) > cq+1:
        if [-(al[aq] + bl[bq] + cl[cq+1]), aq, bq, cq+1] not in ans:
            heapq.heappush(q, [-(al[aq] + bl[bq] + cl[cq+1]), aq, bq, cq+1])
            heapq.heappush(ans, [-(al[aq] + bl[bq] + cl[cq+1]), aq, bq, cq+1])
            
            

    #q = sorted(q)

    #if len(ans) > d:
    #   ans = sorted(ans, reverse=True)
    #    if ans[d][0] > q[len(q)-1][0]:
    #        break

ans = sorted(ans, reverse=True)
for i in range(d):
    print(-heapq.heappop(ans)[0])


import heapq

a, b, c, d = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
B = list(map(int, input().split()))
B = sorted(B, reverse=True)
C = list(map(int, input().split()))
C = sorted(C, reverse=True)
ans = []
q_list = []
n_q = []
heapq.heappush(n_q, [-(A[0] + B[0] + C[0]), 0, 0, 0])
for i in range(d):
    x, y, z, v = map(int, heapq.heappop(n_q))
    ans.append(-x)

    if y + 1 < a and [y + 1, z, v] not in q_list:
        heapq.heappush(n_q, [-(A[y + 1] + B[z] + C[v]), y + 1, z, v])
        q_list.append([y + 1, z, v])
    if z + 1 < b and [y, z + 1, v] not in q_list:
        heapq.heappush(n_q, [-(A[y] + B[z + 1] + C[v]), y, z + 1, v])
        q_list.append([y, z + 1, v])
    if v + 1 < c and [y, z, v + 1] not in q_list:
        heapq.heappush(n_q, [-(A[y] + B[z] + C[v + 1]), y, z, v + 1])
        q_list.append([y, z, v + 1])

for i in range(d):
    print(ans[i])


Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Accepted