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):
# -*- coding: utf-8 -*-
"""
Created on Wed Apr 10 22:30:07 2019

@author: Yamazaki Kenichi
"""
import heapq
import random

X,Y,Z,K = 1000,1000,1000,3000
A = random.sample(range(10**9),1000)
B = random.sample(range(10**9),1000)
C = random.sample(range(10**9),1000)

#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.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
Q = []
T = [[-1 for i in range(X)] for i in range(Y)]
T[0][0] = 0
heapq.heappush(Q,[-(A[0]+B[0]+C[0]),0,0,0])
for i in range(K-1):
    k = heapq.heappop(Q)
    s1,s2,s3 = k[1],k[2],k[3]
    if s1 + 1 != X and T[s1+1][s2] <= s3:
        heapq.heappush(Q,[-(A[s1+1]+B[s2]+C[s3]),s1+1,s2,s3])
        T[s1+1][s2] += 1
    if s2 + 1 != Y and T[s1][s2+1] <= s3:
        heapq.heappush(Q,[-(A[s1]+B[s2+1]+C[s3]),s1,s2+1,s3])
        T[s1][s2+1] += 1
    if s3 + 1 != Z and T[s1][s2] <= s3 + 1:
        heapq.heappush(Q,[-(A[s1]+B[s2]+C[s3+1]),s1,s2,s3+1])
        T[s1][s2] += 1
    print(-k[0])
k = heapq.heappop(Q)
print(-k[0])


# -*- coding: utf-8 -*-
"""
Created on Wed Apr 10 22:30:07 2019

@author: Yamazaki Kenichi
"""
import heapq
#import random
#X,Y,Z,K = 1000,1000,1000,3000
#A = random.sample(range(10**9),1000)
#B = random.sample(range(10**9),1000)
#C = random.sample(range(10**9),1000)

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.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
Q = []
T = [[-1 for i in range(X)] for i in range(Y)]
T[0][0] = 0
heapq.heappush(Q,[-(A[0]+B[0]+C[0]),0,0,0])
for i in range(K-1):
    k = heapq.heappop(Q)
    s1,s2,s3 = k[1],k[2],k[3]
    if s1 + 1 != X and T[s1+1][s2] <= s3:
        heapq.heappush(Q,[-(A[s1+1]+B[s2]+C[s3]),s1+1,s2,s3])
        T[s1+1][s2] += 1
    if s2 + 1 != Y and T[s1][s2+1] <= s3:
        heapq.heappush(Q,[-(A[s1]+B[s2+1]+C[s3]),s1,s2+1,s3])
        T[s1][s2+1] += 1
    if s3 + 1 != Z and T[s1][s2] <= s3 + 1:
        heapq.heappush(Q,[-(A[s1]+B[s2]+C[s3+1]),s1,s2,s3+1])
        T[s1][s2] += 1
    print(-k[0])
k = heapq.heappop(Q)
print(-k[0])


# -*- coding: utf-8 -*-
"""
Created on Wed Apr 10 22:30:07 2019

@author: Yamazaki Kenichi
"""
import heapq
#import random
#X,Y,Z,K = 1000,1000,1000,3000
#A = random.sample(range(10**9),1000)
#B = random.sample(range(10**9),1000)
#C = random.sample(range(10**9),1000)

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.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
Q = []
T = [[-1 for i in range(X)] for i in range(Y)]
T[0][0] = 0
heapq.heappush(Q,[-(A[0]+B[0]+C[0]),0,0,0])
for i in range(K-1):
    k = heapq.heappop(Q)
    s1,s2,s3 = k[1],k[2],k[3]
    if s1 + 1 != X and T[s1+1][s2] < s3:
        heapq.heappush(Q,[-(A[s1+1]+B[s2]+C[s3]),s1+1,s2,s3])
        T[s1+1][s2] += 1
    if s2 + 1 != Y and T[s1][s2+1] < s3:
        heapq.heappush(Q,[-(A[s1]+B[s2+1]+C[s3]),s1,s2+1,s3])
        T[s1][s2+1] += 1
    if s3 + 1 != Z and T[s1][s2] < s3 + 1:
        heapq.heappush(Q,[-(A[s1]+B[s2]+C[s3+1]),s1,s2,s3+1])
        T[s1][s2] += 1
    print(-k[0])
k = heapq.heappop(Q)
print(-k[0])


Verdicts: Wrong Answer

Wrong Answer

Accepted