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 = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
b.sort()
c.sort()
a.reverse()
b.reverse()
c.reverse()

a_idx = 0
b_idx = 0
c_idx = 0
output = []
output.append((a_idx, b_idx, c_idx))
while len(output) < k:
    current = 0
    cand = (0, 0, 0)
    for tup in output:
        a_idx, b_idx, c_idx = tup
        if a_idx < len(a) - 1:
            if (a_idx + 1, b_idx, c_idx) not in output and current < a[a_idx + 1] + b[b_idx] + c[c_idx]:
                current = a[a_idx + 1] + b[b_idx] + c[c_idx]
                cand = (a_idx + 1, b_idx, c_idx)
        if b_idx < len(b) - 1:
            if (a_idx, b_idx + 1, c_idx) not in output and current < a[a_idx] + b[b_idx + 1] + c[c_idx]:
                current = a[a_idx] + b[b_idx + 1] + c[c_idx]
                cand = (a_idx, b_idx + 1, c_idx)
        if c_idx < len(c) - 1:
            if (a_idx, b_idx, c_idx + 1) not in output and current < a[a_idx] + b[b_idx] + c[c_idx + 1]:
                current = a[a_idx] + b[b_idx] + c[c_idx + 1]
                cand = (a_idx, b_idx, c_idx + 1)
    print(cand)
    output.append(cand)

for tup in output:
    a_idx, b_idx, c_idx = tup
    print(a[a_idx] + b[b_idx] + c[c_idx])


x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.reverse()
b.reverse()
c.reverse()

counter = 0
a_idx = 0
b_idx = 0
c_idx = 0
while counter < k:
    print(a[a_idx] + b[b_idx] + b[b_idx])
    counter += 1

    a_diff = -1
    b_diff = -1
    c_diff = -1
    diff = []
    if a_idx < len(a) - 1:
        a_diff = a[a_idx] - a[a_idx + 1]
        diff.append(a_diff)
    if b_idx < len(b) - 1:
        b_diff = b[b_idx] - b[b_idx + 1]
        diff.append(b_diff)
    if c_idx < len(c) - 1:
        c_diff = c[c_idx] - c[c_idx + 1]
        diff.append(c_diff)
    min_diff = min(diff)

    for i, d in enumerate([a_diff, b_diff, c_diff]):
        if d == min_diff:
            if i == 0:
                a_idx += 1
            elif i == 1:
                b_idx += 1
            else:
                c_idx += 1

import heapq

x, y, z, k = list(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, key=lambda x: x * -1)
b = sorted(b, key=lambda x: x * -1)
c = sorted(c, key=lambda x: x * -1)

counter = 0
a_idx = 0
b_idx = 0
c_idx = 0
pque = []
heapq.heappush(pque, (-1 * (a[a_idx] + b[b_idx] + c[c_idx]), (a_idx, b_idx, c_idx)))

while counter < k:
    counter += 1
    output = heapq.heappop(pque)
    print(output[0] * -1)
    a_idx, b_idx, c_idx = output[1]
    if a_idx < len(a) - 1:
        current = a[a_idx + 1] + b[b_idx] + c[c_idx]
        cand = (a_idx + 1, b_idx, c_idx)
        if (-1 * current, cand) not in pque:
            heapq.heappush(pque, (-1 * current, cand))
    if b_idx < len(b) - 1:
        current = a[a_idx] + b[b_idx + 1] + c[c_idx]
        cand = (a_idx, b_idx + 1, c_idx)
        if (-1 * current, cand) not in pque:
            heapq.heappush(pque, (-1 * current, cand))
    if c_idx < len(c) - 1:
        current = a[a_idx] + b[b_idx] + c[c_idx + 1]
        cand = (a_idx, b_idx, c_idx + 1)
        if (-1 * current, cand) not in pque:
            heapq.heappush(pque, (-1 * current, cand))

Verdicts: Wrong Answer

Runtime Error

Accepted