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 = 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]

R  = [sum([A[0], B[0], C[0]])]
Q  = {(0, 0, 1), (0, 1, 0), (1, 0, 0)}
D  = {(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0)}
iS = [((a, b, c), sum([A[a], B[b], C[c]])) for a, b, c in Q if (a < X) and (b < Y) and (c < Z)]

while len(R) < K:
    R.append(iS[0][1])
    abc     = iS[0][0]
    a, b, c = abc[0], abc[1], abc[2]
    iS      = iS[1:]
    if a + 1 < X:
        if not (a + 1, b, c) in D:
            s = sum([A[a + 1], B[b], C[c]])
            for i in range(len(iS)):
                if iS[i][1] <= s:
                    break
            iS = iS[:i+1] + [((a + 1, b, c), s)] + iS[i+1:]
            D.add((a + 1, b, c))
    if b + 1 < Y:
        if not (a, b + 1, c) in D:
            s = sum([A[a], B[b + 1], C[c]])
            for i in range(len(iS)):
                if iS[i][1] <= s:
                    break
            iS = iS[:i+1] + [((a, b + 1, c), s)] + iS[i+1:]
            D.add((a, b + 1, c))
    if c + 1 < Z:
        if not (a, b, c + 1) in D:
            s = sum([A[a], B[b], C[c + 1]])
            for i in range(len(iS)):
                if iS[i][1] <= s:
                    break
            iS = iS[:i+1] + [((a, b, c + 1), s)] + iS[i+1:]
            D.add((a, b, c + 1))

for r in R:
    print(r)


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

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]

R  = [sum([A[0], B[0], C[0]])]
Q  = {(0, 0, 1), (0, 1, 0), (1, 0, 0)}
D  = {(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0)}
iS = [((a, b, c), sum([A[a], B[b], C[c]])) for a, b, c in Q if (a < X) and (b < Y) and (c < Z)]

while len(R) < K:
    
    
    R.append(iS[0][1])
    abc     = iS[0][0]
    a, b, c = abc[0], abc[1], abc[2]
    iS      = iS[1:]
    if a + 1 < X:
        if not (a + 1, b, c) in D:
            iS.append(((a + 1, b, c), sum([A[a + 1], B[b], C[c]])))
            D.add(     (a + 1, b, c))
    if b + 1 < Y:
        if not (a, b + 1, c) in D:
            iS.append(((a, b + 1, c), sum([A[a], B[b + 1], C[c]])))
            D.add(     (a, b + 1, c))
    if c + 1 < Z:
        if not (a, b, c + 1) in D:
            iS.append(((a, b, c + 1), sum([A[a], B[b], C[c + 1]])))
            D.add(     (a, b, c + 1))

for r in R:
    print(r)


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

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]

R  = [sum([A[0], B[0], C[0]])]
Q  = {(0, 0, 1), (0, 1, 0), (1, 0, 0)}
D  = {(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0)}
iS = [((a, b, c), sum([A[a], B[b], C[c]])) for a, b, c in Q if (a < X) and (b < Y) and (c < Z)]
iS = sorted(iS, key=lambda x: [x[1], x[0]], reverse=True)

while len(R) < K:
    R.append(iS[0][1])
    abc     = iS[0][0]
    a, b, c = abc[0], abc[1], abc[2]
    iS      = iS[1:]
    if a + 1 < X:
        if not (a + 1, b, c) in D:
            s = sum([A[a + 1], B[b], C[c]])
            is_done = False
            for i in range(len(iS)):
                if iS[i][1] < s:
                    iS = iS[:i] + [((a + 1, b, c), s)] + iS[i:]
                    is_done = True
                    break
            if is_done == False:
                iS = iS + [((a + 1, b, c), s)]
            D.add((a + 1, b, c))
    if b + 1 < Y:
        if not (a, b + 1, c) in D:
            s = sum([A[a], B[b + 1], C[c]])
            is_done = False
            for i in range(len(iS)):
                if iS[i][1] < s:
                    iS = iS[:i] + [((a, b + 1, c), s)] + iS[i:]
                    is_done = True
                    break
            if is_done == False:
                iS = iS + [((a, b + 1, c), s)]
            D.add((a, b + 1, c))
    if c + 1 < Z:
        if not (a, b, c + 1) in D:
            s = sum([A[a], B[b], C[c + 1]])
            is_done = False
            for i in range(len(iS)):
                if iS[i][1] < s:
                    iS = iS[:i] + [((a, b, c + 1), s)] + iS[i:]
                    is_done = True
                    break
            if is_done == False:
                iS = iS + [((a, b, c + 1), s)]
            D.add((a, b, c + 1))

for r in R:
    print(r)


Verdicts: Wrong Answer

Wrong Answer

Accepted