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):
X, Y, Z, K = map(int, input().split())

A = map(int, input().split())
B = map(int, input().split())
C = map(int, input().split())


def get_good(a, v):
    if v is not None:
        return max(a[a < v])
    else:
        max(a)


value = 0
a = b = c = None
for i in range(K):
    print(get_good(A, a) + get_good(B, b), get_good(C, c))
    a = get_good(a)
    b = get_good(b)
    c = get_good(c)


import numpy as np
import sys

X, Y, Z, K = map(int, input().split())

A = map(int, input().split())
B = map(int, input().split())
C = map(int, input().split())

def get_good(a, v):
    if v is not None:
        return max(a[a < v])
    else:
        max(a)

value = 0
a = b = c = None
for i in range(K):
    print(get_good(A, a) + get_good(B, b), get_good(C, c))
    a = get_good(a)
    b = get_good(b)
    c = get_good(c)


X, Y, Z, K = map(int, input().split())

A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))



#     return max(a)
#     if v is not None:
#         return max(a[a < v])
#     else:
#         max(a)



prev_a = max(A)
prev_b = max(B)
prev_c = max(C)

value = prev_a + prev_b + prev_c

A.remove(max(A))
B.remove(max(B))
C.remove(max(C))

print(value)

for i in range(K - 1):
    a = max(A)
    b = max(B)
    c = max(C)

    sub_a = prev_a - a
    sub_b = prev_b - b
    sub_c = prev_c - c

    if sub_a < sub_b and sub_a < sub_c:
        A.remove(a)
    if sub_b < sub_a and sub_b < sub_c:
        B.remove(b)
    if sub_c < sub_a and sub_c < sub_b:
        B.remove(c)


    value -= min(sub_a, sub_b, sub_c)
    print(value)


from operator import itemgetter

K = int(input().split()[-1])

A = sorted([int(e) for e in input().split()], reverse=True)
B = sorted([int(e) for e in input().split()], reverse=True)
C = sorted([int(e) for e in input().split()], reverse=True)


def get_next_iter(i, _list):
    if i < len(_list) - 1:
        return i + 1
    else:
        return i


def get_value(ia, ib, ic):
    return A[ia] + B[ib] + C[ic]


def get_next(ia, ib, ic):
    ia_n = get_next_iter(ia, A)
    ib_n = get_next_iter(ib, B)
    ic_n = get_next_iter(ic, C)

    return [(ia_n, ib, ic, get_value(ia_n, ib, ic)),
            (ia, ib_n, ic, get_value(ia, ib_n, ic)),
            (ia, ib, ic_n, get_value(ia, ib, ic_n))]


values = [(0, 0, 0, get_value(0, 0, 0))]
candidate = set(get_next(0, 0, 0))

for k in range(K - 1):
    vs = sorted(candidate, reverse=True, key=itemgetter(3))
    v = vs[0]
    values.append(v)
    candidate.remove(v)
    for each in get_next(v[0], v[1], v[2]):
        candidate.add(each)

for each in values:
    print(each[3])


K = int(input().split()[-1])

A = [int(e) for e in input().split()]
B = [int(e) for e in input().split()]
C = [int(e) for e in input().split()]
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# C = list(map(int, input().split()))



#     return max(a)
#     if v is not None:
#         return max(a[a < v])
#     else:
#         max(a)



prev_a = max(A)
prev_b = max(B)
prev_c = max(C)

value = prev_a + prev_b + prev_c

A.remove(max(A))
B.remove(max(B))
C.remove(max(C))

print(value)

for i in range(K - 1):
    a = max(A)
    b = max(B)
    c = max(C)

    sub_a = prev_a - a
    sub_b = prev_b - b
    sub_c = prev_c - c

    if sub_a < sub_b and sub_a < sub_c:
        A.remove(a)
    if sub_b < sub_a and sub_b < sub_c:
        B.remove(b)
    if sub_c < sub_a and sub_c < sub_b:
        B.remove(c)


    value -= min(sub_a, sub_b, sub_c)
    print(value)


from heapq import heappush, heappop
from operator import itemgetter

X, Y, Z, K = map(int, input().split())

A = sorted([int(e) for e in input().split()], reverse=True)
B = sorted([int(e) for e in input().split()], reverse=True)
C = sorted([int(e) for e in input().split()], reverse=True)


def get_value(ia, ib, ic):
    return -(A[ia] + B[ib] + C[ic])


def get_next(ia, ib, ic):
    s = []
    if ia < X - 1:
        s.append((get_value(ia + 1, ib, ic), ia + 1, ib, ic))
    if ib < Y - 1:
        s.append((get_value(ia, ib + 1, ic), ia, ib + 1, ic))
    if ic < Z - 1:
        s.append((get_value(ia, ib, ic + 1), ia, ib, ic + 1))
    return s


heap = []
values = []
heappush(heap, (get_value(0, 0, 0), 0, 0, 0))

for k in range(K):
    
    v = heappop(heap)
    values.append(v)
    for each in get_next(v[1], v[2], v[3]):
        heappush(heap, each)

for each in values:
    print(-each[0])


from heapq import heappush, heappop

X, Y, Z, K = map(int, input().split())

A = sorted([int(e) for e in input().split()], reverse=True)
B = sorted([int(e) for e in input().split()], reverse=True)
C = sorted([int(e) for e in input().split()], reverse=True)


def get_value(ai, bi, ci):
    return -(A[ai] + B[bi] + C[ci])


heap = []
heappush(heap, (get_value(0, 0, 0), 0, 0, 0))
used = {(0, 0, 0)}

for k in range(K):
    v, ia, ib, ic = heappop(heap)
    print(-v)

    if ia + 1 < X and (ia + 1, ib, ic) not in used:
        heappush(heap, (get_value(ia + 1, ib, ic), ia + 1, ib, ic))
        used.add((ia + 1, ib, ic))
    if ib + 1 < Y and (ia, ib + 1, ic) not in used:
        heappush(heap, (get_value(ia, ib + 1, ic), ia, ib + 1, ic))
        used.add((ia, ib + 1, ic))
    if ic + 1 < Z and (ia, ib, ic + 1) not in used:
        heappush(heap, (get_value(ia, ib, ic + 1), ia, ib, ic + 1))
        used.add((ia, ib, ic + 1))


Verdicts: Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Accepted