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 sys
def input(): return sys.stdin.readline().rstrip()

def main():
    X, Y, Z, K = map(int, input().split())
    A, B, C = [sorted(map(int, input().split())) for _ in range(3)]

    AB = []
    for i, a in enumerate(A):
        for j, b in enumerate(B):
            AB.append(a + b)
    AB = sorted(AB, reverse=True)[:K]

    ans = []
    for i, ab in enumerate(AB):
        for j, c in enumerate(C):
            ans.append(ab + c)
    ans = sorted(ans, reverse=True)[:K]
    print(ans)
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()


import sys
import heapq
def input(): return sys.stdin.readline().rstrip()

def main():
    X, Y, Z, K = map(int, input().split())
    A, B, C = [sorted(map(int, input().split()), reverse=True) for _ in range(3)]

    hp = []
    heapq.heappush(hp, (- A[0] - B[0] - C[0], 0, 0, 0))
    exists = set([(0, 0, 0)])
    for _ in range(K):
        v, x, y, z = heapq.heappop(hp)
        print(-v)
        if x + 1 < X and (x + 1, y, z) not in exists:
            heapq.heappush(hp, (v + A[x] - A[x+1], x + 1, x, z))
        if y + 1 < Y and (x, y + 1, z) not in exists:
            heapq.heappush(hp, (v + B[y] - B[y+1], x, y + 1, z))
        if z + 1 < Z and (x, y, z + 1) not in exists:
            heapq.heappush(hp, (v + C[z] - C[z+1], x, y, z + 1))

if __name__ == '__main__':
    main()


import sys
import heapq
def input(): return sys.stdin.readline().rstrip()

def main():
    X, Y, Z, K = map(int, input().split())
    A, B, C = [sorted(map(int, input().split()), reverse=True) for _ in range(3)]

    hp = []
    heapq.heappush(hp, (- A[0] - B[0] - C[0], 0, 0, 0))
    exists = set([(0, 0, 0)])
    for _ in range(K):
        v, x, y, z = heapq.heappop(hp)
        print(-v)
        if x + 1 < X and (x + 1, y, z) not in exists:
            heapq.heappush(hp, (v + A[x] - A[x+1], x + 1, y, z))
            exists.add((x + 1, y, z))
        if y + 1 < Y and (x, y + 1, z) not in exists:
            heapq.heappush(hp, (v + B[y] - B[y+1], x, y + 1, z))
            exists.add((x, y + 1, z))
        if z + 1 < Z and (x, y, z + 1) not in exists:
            heapq.heappush(hp, (v + C[z] - C[z+1], x, y, z + 1))
            exists.add((x, y, z + 1))

if __name__ == '__main__':
    main()


Verdicts: Wrong Answer

Wrong Answer

Accepted