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):
import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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()))


def calc(x, y, z):
    return [-A[x]-B[y]-C[z], x, y, z]


def solve1(A, B, C, X, Y, Z, k):
    A = sorted(A, reverse=True)
    B = sorted(B, reverse=True)
    C = sorted(C, reverse=True)
    Q = []
    Q.append(calc(0, 0, 0))

    ans = []
    
    memo = {(0, 0, 0): True}
    for _ in range(k):
        e, x, y, z = heapq.heappop(Q)
        ans.append(-e)
        if x+1 < X and (x+1, y, z) not in memo:
            heapq.heappush(Q, calc(x+1, y, z))
            memo[(x+1, y, z)] = True
        if y+1 < Y and (x, y+1, z) not in memo:
            heapq.heappush(Q, calc(x, y+1, z))
            memo[(x, y+1, z)] = True

        if z+1 < Z and (x, y, z+1) not in memo:
            heapq.heappush(Q, calc(x, y, z+1))
            memo[(x, y, z+1)] = True

    print("\n".join(map(str, ans[:k])))


solve1(A, B, C, X, Y, Z, k)


import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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()))


def solve1():
    que = []
    for a in a:
        for b in b:
            for c in c:
                heapq.heappush(que, -(a+b+c))
    for _ in range(k):
        print(-heapq.heappop(que))


solve1()


import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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()))
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)


def calc(x, y, z):
    return [-A[x]-B[y]-C[z], x, y, z]


def solve1(A, B, C, X, Y, Z, k):
    Q = []
    Q.append(calc(0, 0, 0))

    ans = []
    
    memo = {(0, 0, 0): True}
    for _ in range(k):
        e, x, y, z = heapq.heappop(Q)
        ans.append(-e)
        if x+1 < X and (x+1, y, z) not in memo:
            heapq.heappush(Q, calc(x+1, y, z))
            memo[(x+1, y, z)] = True
        if y+1 < Y and (x, y+1, z) not in memo:
            heapq.heappush(Q, calc(x, y+1, z))
            memo[(x, y+1, z)] = True

        if z+1 < Z and (x, y, z+1) not in memo:
            heapq.heappush(Q, calc(x, y, z+1))
            memo[(x, y, z+1)] = True

    print("\n".join(map(str, ans[:k])))


solve1(A, B, C, X, Y, Z, k)


Verdicts: Wrong Answer

Runtime Error

Accepted