Problem p03078 (python)

Fixed submission:
# coding: utf-8
#解法1 ABのK番まで　＋　CのK番まで
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()))

AB=[]

for i in range(X):
    for j in range(Y):
        AB.append(A[i]+B[j])

AB.sort(reverse=True)
C.sort(reverse=True)

ABC=[]

for i in range(min(K,X*Y)):
    for j in range(min(K,Z)):
        ABC.append(AB[i]+C[j])

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])

Buggy submission (verdict: Runtime Error):
# coding: utf-8
#解法2 ヒープを使う
import heapq
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)

used=[]

heap=[]

heapq.heappush(heap,(-(A[0]+B[0]+C[0]),0,0,0))
used.append((0,0,0))

for i in range(K):
    u=heapq.heappop(heap)
    if not((u[1]+1,u[2],u[3]) in used):
        used.append((u[1]+1,u[2],u[3]))
        heapq.heappush(heap,(-(A[u[1]+1]+B[u[2]]+C[u[3]]),u[1]+1,u[2],u[3]))
        
    if not((u[1],u[2]+1,u[3]) in used):
        used.append((u[1],u[2]+1,u[3]))
        heapq.heappush(heap,(-(A[u[1]]+B[u[2]+1]+C[u[3]]),u[1],u[2]+1,u[3]))
        
    if not((u[1],u[2],u[3]+1) in used):
        used.append((u[1],u[2],u[3]+1))
        heapq.heappush(heap,(-(A[u[1]]+B[u[2]]+C[u[3]+1]),u[1],u[2],u[3]+1))
    print(-u[0])

Buggy submission (verdict: Runtime Error):
# coding: utf-8
#解法2 ヒープを使う
import heapq
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)

un_used=[[[True for i in range(Z)] for j in range(Y)] for k in range(X)]

heap=[]

heapq.heappush(heap,(-(A[0]+B[0]+C[0]),0,0,0))

un_used[0][0][0]=False

for i in range(K):
    u=heapq.heappop(heap)
    if un_used[u[1]+1][u[2]][u[3]]:
        un_used[u[1]+1][u[2]][u[3]]=False
        heapq.heappush(heap,(-(A[u[1]+1]+B[u[2]]+C[u[3]]),u[1]+1,u[2],u[3]))
        
    if un_used[u[1]][u[2]+1][u[3]]:
        un_used[u[1]][u[2]+1][u[3]]=False
        heapq.heappush(heap,(-(A[u[1]]+B[u[2]+1]+C[u[3]]),u[1],u[2]+1,u[3]))
        
    if un_used[u[1]][u[2]][u[3]+1]:
        un_used[u[1]][u[2]][u[3]+1]=False
        heapq.heappush(heap,(-(A[u[1]]+B[u[2]]+C[u[3]+1]),u[1],u[2],u[3]+1))
    print(-u[0])

Buggy submission (verdict: Runtime Error):
# coding: utf-8
#解法2 ヒープを使う
import heapq
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)

un_used=[[[True for i in range(Z)] for j in range(Y)] for k in range(X)]

heap=[]

heapq.heappush(heap,(-(A[0]+B[0]+C[0]),0,0,0))

un_used[0][0][0]=False

for i in range(K):
    u=heapq.heappop(heap)
    if un_used[u[1]+1][u[2]][u[3]]:
        un_used[u[1]+1][u[2]][u[3]]=False
        heapq.heappush(heap,(-(A[u[1]+1]+B[u[2]]+C[u[3]]),u[1]+1,u[2],u[3]))
        
    if un_used[u[1]][u[2]+1][u[3]]:
        un_used[u[1]][u[2]+1][u[3]]=False
        heapq.heappush(heap,(-(A[u[1]]+B[u[2]+1]+C[u[3]]),u[1],u[2]+1,u[3]))
        
    if un_used[u[1]][u[2]][u[3]+1]:
        un_used[u[1]][u[2]][u[3]+1]=False
        heapq.heappush(heap,(-(A[u[1]]+B[u[2]]+C[u[3]+1]),u[1],u[2],u[3]+1))
    print(-u[0])

Buggy submission (verdict: Runtime Error):
# coding: utf-8
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)

INF=10**12

DA=[]
DB=[]
DC=[]

for i in range(X-1):
    DA.append(A[i]-A[i+1])
    
for i in range(Y-1):
    DB.append(B[i]-B[i+1])
    
for i in range(Z-1):
    DC.append(C[i]-C[i+1])

SA=[DA[0]]
SB=[DB[0]]
SC=[DC[0]]

for i in range(X-2):
    SA.append(SA[i]+DA[i+1])
    
for i in range(Y-2):
    SB.append(SB[i]+DB[i+1])
    
for i in range(Z-2):
    SC.append(SC[i]+DC[i+1])

SA.append(INF)
SB.append(INF)
SC.append(INF)

A_m=[0]
B_m=[0]
C_m=[0]

A_num=1
B_num=1
C_num=1

while A_num*B_num*C_num<K:
    if SA[0]==min(SA[0],SB[0],SC[0]):
        tmp = SA.pop(0)
        A_m.append(tmp)
        A_num+=1
        
    if SB[0]==min(SA[0],SB[0],SC[0]):
        tmp = SB.pop(0)
        B_m.append(tmp)
        B_num+=1
        
    if SC[0]==min(SA[0],SB[0],SC[0]):
        tmp = SC.pop(0)
        C_m.append(tmp)
        C_num+=1

max_val=A[0]+B[0]+C[0]
cake=[]

for i in range(A_num):
    for j in range(B_num):
        for k in range(C_num):
            cake.append(max_val - A_m[i] - B_m[j] - C_m[k])

cake.sort(reverse=True)

# print(DA,DB,DC)
# print(SA,SB,SC)
# print(A_m,B_m,C_m)

for i in range(K):
    print(cake[i])