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):
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import heapq
import numpy

def main():
  na, nb, nc, K = map(int, input().split())
  As = sorted(list(map(int, input().split())), reverse=True)
  Bs = sorted(list(map(int, input().split())), reverse=True)
  Cs = sorted(list(map(int, input().split())), reverse=True)
  
  scores = [(-(As[0]+Bs[0]+Cs[0]), 0, 0, 0)]
  used = numpy.zeros((na, nb, nc), dtype=numpy.int)
  used[0, 0, 0] = 1
  for _ in range(K):
    (score, i, j, k) = heapq.heappop(scores)
    print(-score)
    if i + 1 < na and not used[i+1][j][k]:
      heapq.heappush(scores, (-(As[i+1]+Bs[j]+Cs[k]),   i+1, j,   k))
      used[i+1, j, k] = 1
    if j + 1 < nb and not used[i][j+1][k]:
      heapq.heappush(scores, (-(As[i]+Bs[j+1]+Cs[k]),   i,   j+1, k))
      used[i, j+1, k] = 1
    if k + 1 < nc and not used[i][j][k+1]:
      heapq.heappush(scores, (-(As[i]+Bs[j]+Cs[k+1]),   i,   j,   k+1))
      used[i, j, k+1] = 1

if __name__=='__main__':
  main()



#!/usr/bin/python3
# -*- coding:utf-8 -*-

import heapq
import numpy

def main():
  na, nb, nc, k = map(int, input().split())
  As = sorted(list(map(int, input().split())), reverse=True)
  Bs = sorted(list(map(int, input().split())), reverse=True)
  Cs = sorted(list(map(int, input().split())), reverse=True)
  
  scores = [(-(As[0]+Bs[0]+Cs[0]), 0, 0, 0)]
  used = numpy.zeros((na, nb, nc), dtype=numpy.int)
  used[0, 0, 0] = 1
  for _ in range(k):
    (score, i, j, k) = heapq.heappop(scores)
    print(-score)
    if i + 1 < na and not used[i+1][j][k]:
      heapq.heappush(scores, (-(As[i+1]+Bs[j]+Cs[k]),   i+1, j,   k))
      used[i+1, j, k] = 1
    if j + 1 < nb and not used[i][j+1][k]:
      heapq.heappush(scores, (-(As[i]+Bs[j+1]+Cs[k]),   i,   j+1, k))
      used[i, j+1, k] = 1
    if k + 1 < nc and not used[i][j][k+1]:
      heapq.heappush(scores, (-(As[i]+Bs[j]+Cs[k+1]), i,   j,   k+1))
      used[i, j, k+1] = 1

if __name__=='__main__':
  main()



#!/usr/bin/python3
# -*- coding:utf-8 -*-

import heapq
import numpy

def main():
  na, nb, nc, K = map(int, input().split())
  As = sorted(list(map(int, input().split())), reverse=True)
  Bs = sorted(list(map(int, input().split())), reverse=True)
  Cs = sorted(list(map(int, input().split())), reverse=True)
  
  scores = [(-(As[0]+Bs[0]+Cs[0]), 0, 0, 0)]
  used = numpy.zeros((na, nb, nc), dtype=numpy.int)
  used[0, 0, 0] = 1
  for _ in range(K):
    if len(scores) == 0:
      break
    (score, i, j, k) = heapq.heappop(scores)
    print(-score)
    if i + 1 < na and not used[i+1][j][k]:
      heapq.heappush(scores, (-(As[i+1]+Bs[j]+Cs[k]),   i+1, j,   k))
      used[i+1, j, k] = 1
    if j + 1 < nb and not used[i][j+1][k]:
      heapq.heappush(scores, (-(As[i]+Bs[j+1]+Cs[k]),   i,   j+1, k))
      used[i, j+1, k] = 1
    if k + 1 < nc and not used[i][j][k+1]:
      heapq.heappush(scores, (-(As[i]+Bs[j]+Cs[k+1]),   i,   j,   k+1))
      used[i, j, k+1] = 1

if __name__=='__main__':
  main()



#!/usr/bin/python3
# -*- coding:utf-8 -*-

import heapq

def main():
  na, nb, nc, K = map(int, input().split())
  As = sorted(list(map(int, input().split())), reverse=True)
  Bs = sorted(list(map(int, input().split())), reverse=True)
  Cs = sorted(list(map(int, input().split())), reverse=True)
  
  scores = [(-(As[0]+Bs[0]+Cs[0]), 0, 0, 0)]
  used = [(0, 0, 0)]
  def push(i, j, k):
    heapq.heappush(scores, (-(As[i] + Bs[j] + Cs[k]), i, j, k))
    
  for _ in range(K):
    (score, i, j, k) = heapq.heappop(scores)
    print(-score)
    for di, dj, dk in [[1,0,0], [0,1,0], [0,0,1]]:
      if not (i+di < na and j+dj<nb and k+dk < nc):
        continue        
      if (i+di, j+dj, k+dk) not in used:
        push(i+di, j+dj, k+dk)
        used.append((i+di, j+dj, k+dk))

if __name__=='__main__':
  main()



Verdicts: Runtime Error

Runtime Error

Runtime Error

Accepted