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 = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a.sort()
a.reverse()
b.sort()
b.reverse()
c.sort()
c.reverse()


memo = {}

def next_step(i,j,k):
    cand = []
    for dx, dy, dz in ((1,0,0),
                       (0,1,0),
                       (0,0,1),
                       (1,-1,0),
                       (-1,1,0),
                       (0,1,-1),
                       (0,-1,1),
                       (1,0,-1),
                       (-1,0,1),
                       (2,-1,0),
                       (-1,2,0),
                       (0,-1,2),
                       (0,2,-1),
                       (2,0,-1),
                       (-1,0,2),
                       (1,-2,0),
                       (-2,1,0),
                       (0,-2,1),
                       (0,1,-2),
                       (1,0,-2),
                       (-2,0,1),
                       (2,-2,0),
                       (-2,2,0),
                       (0,-2,2),
                       (0,2,-2),
                       (2,0,-2),
                       (-2,0,2)):
        if 0<=i+dx and i+dx<x\
        and 0<=j+dy and j+dy<y\
        and 0<=k+dz and k+dz<z\
        and not (i+dx,j+dy,k+dz) in memo:
            cand.append([-(a[i+dx]+b[j+dy]+c[k+dz]), [i+dx,j+dy,k+dz]])
    cand.sort()
    return cand[0][1]

i = j = k = 0
print(a[i]+b[j]+c[k])
#print(i,j,k)
memo[(i,j,k)] = 0

for _ in range(K-1):
    i,j,k = next_step(i,j,k)
    memo[(i,j,k)] = 0
#    print(i,j,k)
    print(a[i]+b[j]+c[k])




#include <string>

#include <algorithm>
#include <functional>

using namespace std;
typedef long long ll;

int main()
{
  ll x,y,z,K;
  cin >> x >> y >> z >> K;

  vector<ll>a(x);
  vector<ll>b(y);
  vector<ll>c(z);  
  
  for( int i=0;i<x;++i)
    cin >> a[i];
  for( int i=0;i<y;++i)
    cin >> b[i];
  for( int i=0;i<z;++i)
    cin >> c[i];

  sort(a.begin(), a.end(), greater<ll>());
  sort(b.begin(), b.end(), greater<ll>());
  sort(c.begin(), c.end(), greater<ll>());

  int i,j,k;
  cout << a[i]+b[j]+c[k] << endl;
  for( int v=1;v<K;++v )
    {
      if( i<x-1 && j<y-1 && k<z-1 )
	{
	  ll s = a[i]+b[j]+c[k+1];
	  ll t = a[i]+b[j+1]+c[k];
	  ll u = a[i+1]+b[j]+c[k];       
	  if( s>t && s>u )
	    k++;
	  else if ( t>s && t>u )
	    j++;
	  else
	    i++;
	}
      else if( i<x-1 && j<y-1 )
	{
	  ll t = a[i+1]+b[j]+c[k];
	  ll u = a[i]+b[j+1]+c[k];       
	  if( t>u )
	    i++;
	  else
	    j++;
	}
      else if( i<x-1 && k<z-1 )
	{
	  ll s = a[i+1]+b[j]+c[k];
	  ll t = a[i]+b[j]+c[k+1];
	  if( s>t )
	    i++;
	  else
	    k++;
	}
      else if( j<y-1 && k<z-1 )
	{
	  ll s = a[i]+b[j+1]+c[k];
	  ll t = a[i]+b[j]+c[k+1];
	  if( s>t )
	    j++;
	  else
	    k++;
	}
      else if( i<x-1 )
	i++;
      else if( j<y-1 )
	j++;
      else
	k++;
      
      cout << a[i]+b[j]+c[k] << endl;	 
    }
  return 0;
}


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()
a.reverse()
b.sort()
b.reverse()
c.sort()
c.reverse()


memo = {}
i = j = k = 0

h = []
heapq.heappush(h, (-(a[i]+b[j]+c[k]), i,j,k))
for _ in range(K):
    cost, i, j, k = heapq.heappop(h)
    print(-cost)
    for dx, dy, dz in ((1,0,0), (0,1,0), (0,0,1)):
        if (i+dx, j+dy, k+dz) in memo:
            continue
        if i+dx<x and j+dy<y and k+dz<z:
            heapq.heappush(h, (-(a[i+dx]+b[j+dy]+c[k+dz]), i+dx, j+dy, k+dz))
            memo[(i+dx,j+dy,k+dz)] = 1         
        


Verdicts: Runtime Error

Runtime Error

Accepted