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())
K = min(x * y * z, K)
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)


def check(p, return_array=False):
    cnt = 0
    results = []
    for i in a:
        for j in b:
            for k in c:
                ijk = i + j + k
                if ijk < p:
                    break
                results.append(ijk)
                cnt += 1
                if cnt >= K:
                    return True, results
    return False, results


left = 10**10 * 3
right = 0

while left - right > 1:
    center = (left + right) // 2
    flg, results = check(center)
    if flg:
        right = center
    else:
        left = center

print("\n".join(map(str, (check(left) if flg else check(right))[1])))


import heapq
x, y, z, k = map(int, input().split())
k = min(x * y * z, k)
a = sorted(list(map(int, input().split())), reverse=True)[:k]
b = sorted(list(map(int, input().split())), reverse=True)[:k]
c = sorted(list(map(int, input().split())), reverse=True)[:k]

results = []
pque = [(-(a[0] + b[0] + c[0]), (0, 0, 0))]
for _ in range(k):
    value, position = heapq.heappop(pque)
    print(-value)
    results.append(value)
    for pattern in [[0, 0, 1], [0, 1, 0], [1, 0, 0]]:
        i, j, k = [v1 + v2 for v1, v2 in zip(pattern, position)]
        if i < x and j < y and k < z:
            heapq.heappush(pque, (-(a[i] + b[j] + c[k]), (i, j, k)))


import heapq
x, y, z, K = map(int, input().split())
k = min(x * y * z, K)
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

results = []
pque = [(-(a[0] + b[0] + c[0]), (0, 0, 0))]
visited = {}
cnt = 0
while pque:
    value, position = heapq.heappop(pque)
    if visited.get(position) is None:
        visited[position] = True
        cnt += 1
        if cnt > K:
            break
    else:
        continue

    print(-value)
    results.append(value)
    for pattern in [[0, 0, 1], [0, 1, 0], [1, 0, 0]]:
        i, j, k = [v1 + v2 for v1, v2 in zip(pattern, position)]
        if i < x and j < y and k < z:
            heapq.heappush(pque, (-(a[i] + b[j] + c[k]), (i, j, k)))


Verdicts: Wrong Answer

Wrong Answer

Accepted