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 = sorted(list(map(int,input().split())))
A.reverse()
B = sorted(list(map(int,input().split())))
B.reverse()
C = sorted(list(map(int,input().split())))
C.reverse()

ia,ib,ic = 0,0,0
_min_ = 10000000000001
for ida,a in enumerate(A) :
    for idb,b in enumerate(B):
        idc = int(K/(ida+1)/(idb+1)) -1
        if  idc < len(C) and a+b+C[idc] < _min_:
            _min_ = a+b+C[idc]
            ia,ib,ic = ida,idb,idc

import itertools
#print(list(itertools.product(A[:s_a], B[:s_b],C[:s_c])))
for idx,value in enumerate(sorted([sum(i) for i in  list(itertools.product(A[:ia], B[:ib],C[:ic]))])[::-1]):
    if idx > K-1:
        break
    print(value)



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

A = sorted(list(map(int,input().split())))
A.reverse()
B = sorted(list(map(int,input().split())))
B.reverse()
C = sorted(list(map(int,input().split())))
C.reverse()

ia,ib,ic = 0,0,0
_min_ = 10000000000001
for ida,a in enumerate(A) :
    for idb,b in enumerate(B[:int(K/(ida+1))]):
        idc = int(K/(ida+1)/(idb+1)) -1
        if  idc < len(C) and a+b+C[idc] < _min_:
            _min_ = a+b+C[idc]
            ia,ib,ic = ida,idb,idc

import itertools
#print(list(itertools.product(A[:s_a], B[:s_b],C[:s_c])))
for idx,value in enumerate(sorted([sum(i) for i in  list(itertools.product(A[:ia], B[:ib],C[:ic]))])[::-1]):
    if idx > K-1:
        break
    print(value)



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

A = sorted(list(map(int,input().split())))
A.reverse()
B = sorted(list(map(int,input().split())))
B.reverse()
C = sorted(list(map(int,input().split())))
C.reverse()

ia,ib,ic = 0,0,0
_min_ = 10000000000001
for ida,a in enumerate(A) :
    for idb,b in enumerate(B[:int(K/ida+1)]):
        idc = int(K/(ida+1)/(idb+1)) -1
        if  idc < len(C) and a+b+C[idc] < _min_:
            _min_ = a+b+C[idc]
            ia,ib,ic = ida,idb,idc

import itertools
#print(list(itertools.product(A[:s_a], B[:s_b],C[:s_c])))
for idx,value in enumerate(sorted([sum(i) for i in  list(itertools.product(A[:ia], B[:ib],C[:ic]))])[::-1]):
    if idx > K-1:
        break
    print(value)



X,Y,Z,K = list(map(int,input().split()))
A = [(sorted(list(map(int,input().split())))[::-1]) for i in range(3)]

import heapq

heap = []
item = (0,(0,0,0))
heapq.heappush(heap, item)

considered_dict = set()

ret = []
max_ = A[0][0]+A[1][0]+A[2][0]
while len(considered_dict) < K:
    task  = heapq.heappop(heap)
    score,(x,y,z) =task
    ret.append(score)
    considered_dict |= {(x,y,z)}
    
    if x+1 != X-1 and (x+1,y,z) not in considered_dict:
        heapq.heappush(heap, (max_-A[0][x+1]-A[1][y]-A[2][z],(x+1,y,z) ))
                       
    if y+1 != Y-1 and (x,y+1,z) not in considered_dict:
        heapq.heappush(heap, (max_-A[0][x]-A[1][y+1]-A[2][z],(x,y+1,z) ))
                       
    if z+1 != Z-1 and (x,y,z+1) not in considered_dict:
        heapq.heappush(heap, (max_-A[0][x]-A[1][y]-A[2][z+1],(x,y,z+1) ))


for i in ret:
    print(max_-i)

X,Y,Z,K = list(map(int,input().split()))
A = [(sorted(list(map(int,input().split())))[::-1]) for i in range(3)]

import heapq

heap = []
item = (0,(0,0,0))
heapq.heappush(heap, item)
considered_dict = set(item[1])

ret = []
max_ = A[0][0]+A[1][0]+A[2][0]
while len(ret) < K:
    task  = heapq.heappop(heap)
    score,(x,y,z) =task
    ret.append(score)
    
    if x+1 != X-1 and (x+1,y,z) not in considered_dict:
        heapq.heappush(heap, (max_-A[0][x+1]-A[1][y]-A[2][z],(x+1,y,z) ))
        considered_dict |= {(x+1,y,z)}
        
                       
    if y+1 != Y-1 and (x,y+1,z) not in considered_dict:
        heapq.heappush(heap, (max_-A[0][x]-A[1][y+1]-A[2][z],(x,y+1,z) ))
        considered_dict |= {(x,y+1,z)}
                       
    if z+1 != Z-1 and (x,y,z+1) not in considered_dict:
        heapq.heappush(heap, (max_-A[0][x]-A[1][y]-A[2][z+1],(x,y,z+1) ))
        considered_dict |= {(x,y,z+1)}


for i in ret:
    print(max_-i)


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

A = sorted(list(map(int,input().split())))
A.reverse()
B = sorted(list(map(int,input().split())))
B.reverse()
C = sorted(list(map(int,input().split())))
C.reverse()

a = [A[i] - A[i+1] for i in range(len(A)-1) ]
b = [B[i] - B[i+1] for i in range(len(B)-1) ]
c = [C[i] - C[i+1] for i in range(len(C)-1) ]

st = A[-1]+B[-1]+C[-1]

s_a,s_b,s_c = 1,1,1
for i in range(K-1):
    
    m = min(a[0] if len(a)>0 else 100000000001
            ,b[0] if len(b)>0 else 100000000001
            ,c[0] if len(c)>0 else 100000000001)
    #print(a[0],b[0],c[0])
    consider_list = [0]*3
    if len(a)>0 and a[0] == m:
        consider_list[0] = (s_a+1) * s_b * s_c

    if len(b)>0 and b[0] == m:
        consider_list[1] = (s_a) * (s_b+1) * s_c
    if len(c)>0 and c[0] == m:        
        consider_list[2] = (s_a) * (s_b) * (s_c+1)
    #print(consider_list.index(max(consider_list)))
    if consider_list.index(max(consider_list)) == 0:
        a.pop(0)
        s_a += 1
    elif consider_list.index(max(consider_list)) == 1:
        b.pop(0)
        s_b += 1
    else:
        c.pop(0)
        s_c += 1
    if (s_a-1) * (s_b-1)*(s_c-1) >= K:
        break

import itertools
#print(list(itertools.product(A[:s_a], B[:s_b],C[:s_c])))
for idx,value in enumerate(sorted([sum(i) for i in  list(itertools.product(A[:s_a+1], B[:s_b+1],C[:s_c+1]))])[::-1]):
  if idx > K-1:
    break
  print(value)
             

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

A = sorted(list(map(int,input().split())))
A.reverse()
B = sorted(list(map(int,input().split())))
B.reverse()
C = sorted(list(map(int,input().split())))
C.reverse()

ia,ib,ic = 0,0,0
_min_ = 10000000000001
for ida,a in enumerate(A) :
    for idb,b in enumerate(B[:int(K/ida)]):
        idc = int(K/(ida+1)/(idb+1)) -1
        if  idc < len(C) and a+b+C[idc] < _min_:
            _min_ = a+b+C[idc]
            ia,ib,ic = ida,idb,idc

import itertools
#print(list(itertools.product(A[:s_a], B[:s_b],C[:s_c])))
for idx,value in enumerate(sorted([sum(i) for i in  list(itertools.product(A[:ia], B[:ib],C[:ic]))])[::-1]):
    if idx > K-1:
        break
    print(value)



X,Y,Z,K = list(map(int,input().split()))
A = [(sorted(list(map(int,input().split())))[::-1]) for i in range(3)]

import heapq

heap = []
item = (0,(0,0,0))
heapq.heappush(heap, item)
considered_dict = set(item[1])

ret = []
max_ = A[0][0]+A[1][0]+A[2][0]
while len(ret) < K:
    task  = heapq.heappop(heap)
    score,(x,y,z) =task
    ret.append(score)
    
    if x+1 != X and (x+1,y,z) not in considered_dict:
        heapq.heappush(heap, (max_-A[0][x+1]-A[1][y]-A[2][z],(x+1,y,z) ))
        considered_dict |= {(x+1,y,z)}
        
                       
    if y+1 != Y and (x,y+1,z) not in considered_dict:
        heapq.heappush(heap, (max_-A[0][x]-A[1][y+1]-A[2][z],(x,y+1,z) ))
        considered_dict |= {(x,y+1,z)}
                       
    if z+1 != Z and (x,y,z+1) not in considered_dict:
        heapq.heappush(heap, (max_-A[0][x]-A[1][y]-A[2][z+1],(x,y,z+1) ))
        considered_dict |= {(x,y,z+1)}


for i in ret:
    print(max_-i)


Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted