Problem:


Score: 400 points

Problem Statement

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.

Constraints

1 \leq X \leq 1 \ 000

1 \leq Y \leq 1 \ 000

1 \leq Z \leq 1 \ 000

1 \leq K \leq \min(3 \ 000, X \times Y \times Z)

1 \leq A_i \leq 10 \ 000 \ 000 \ 000

1 \leq B_i \leq 10 \ 000 \ 000 \ 000

1 \leq C_i \leq 10 \ 000 \ 000 \ 000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y Z K
A_1 \ A_2 \ A_3 \ ... \ A_X
B_1 \ B_2 \ B_3 \ ... \ B_Y
C_1 \ C_2 \ C_3 \ ... \ C_Z

Output

Print K lines. The i-th line should contain the i-th value stated in the problem statement.

Sample Input 1

2 2 2 8
4 6
1 5
3 8

Sample Output 1

19
17
15
14
13
12
10
8

There are 2 \times 2 \times 2 = 8 ways to choose three cakes, as shown below in descending order of the sum of the deliciousness of the cakes:

(A_2, B_2, C_2): 6 + 5 + 8 = 19

(A_1, B_2, C_2): 4 + 5 + 8 = 17

(A_2, B_1, C_2): 6 + 1 + 8 = 15

(A_2, B_2, C_1): 6 + 5 + 3 = 14

(A_1, B_1, C_2): 4 + 1 + 8 = 13

(A_1, B_2, C_1): 4 + 5 + 3 = 12

(A_2, B_1, C_1): 6 + 1 + 3 = 10

(A_1, B_1, C_1): 4 + 1 + 3 = 8

Sample Input 2

3 3 3 5
1 10 100
2 20 200
1 10 100

Sample Output 2

400
310
310
301
301

There may be multiple combinations of cakes with the same sum of the deliciousness. For example, in this test case, the sum of A_1, B_3, C_3 and the sum of A_3, B_3, C_1 are both 301.
However, they are different ways of choosing cakes, so 301 occurs twice in the output.

Sample Input 3

10 10 10 20
7467038376 5724769290 292794712 2843504496 3381970101 8402252870 249131806 6310293640 6690322794 6082257488
1873977926 2576529623 1144842195 1379118507 6003234687 4925540914 3902539811 3326692703 484657758 2877436338
4975681328 8974383988 2882263257 7690203955 514305523 6679823484 4263279310 585966808 3752282379 620585736

Sample Output 3

23379871545
22444657051
22302177772
22095691512
21667941469
21366963278
21287912315
21279176669
21160477018
21085311041
21059876163
21017997739
20703329561
20702387965
20590247696
20383761436
20343962175
20254073196
20210218542
20150096547

Note that the input or output may not fit into a 32-bit integer type.



Sample input:
2 2 2 8
4 6
1 5
3 8


Sample output:
19
17
15
14
13
12
10
8

Submission status: Time Limit Exceeded

Solution code:
x, y, z, k = map(int, input().split())
a = map(int, input().split())
b = list(map(int, input().split()))
c = map(int, input().split())
d = sorted((ai + bi for ai in a for bi in b), reverse=True)[:k]
e = sorted((ci + di for ci in c for di in d), reverse=True)
i = 0
while i != k:
    print(e[i])
    i += 1

Submission status: Time Limit Exceeded

Solution code:
def islice(it, cnt):
    for x in it:
        if cnt:
            yield x
            cnt -= 1
        else:
            return

x, y, z, k = map(int, input().split())
a = map(int, input().split())
b = list(map(int, input().split()))
c = map(int, input().split())
d = sorted((ai + bi for ai in a for bi in b), reverse=True)
e = sorted((ci + di for ci in c for di in islice(d, k)), reverse=True)
print('\n'.join(map(str, islice(e, k))))

Submission status: Time Limit Exceeded

Solution code:
from itertools import islice
x, y, z, k = map(int, input().split())
a = map(int, input().split())
b = list(map(int, input().split()))
c = map(int, input().split())
d = sorted((ai + bi for ai in a for bi in b), reverse=True)
e = sorted((ci + di for ci in c for di in islice(d, k)), reverse=True)
print(*islice(e, k), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
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()))
d = sorted((ai + bi for ai in a for bi in b), reverse=True)[:k]
e = sorted((ci + di for ci in c for di in d), reverse=True)[:k]
print(*e, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readline_s = sys.stdin.readline
readlines = sys.stdin.buffer.readlines

INF = 10 ** 10 + 7


def main():
    X, Y, Z, K = map(int, readline().split())
    A = sorted(list(map(int, readline().split())), reverse=True)
    B = sorted(list(map(int, readline().split())), reverse=True)
    C = sorted(list(map(int, readline().split())), reverse=True)

    ans = solve1(X, Y, Z, K, A, B, C)
    print('\n'.join(map(str, ans)))


def solve1(X, Y, Z, K, A, B, C):

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

    AB.sort(reverse=True)
    AB = AB[:min(X * Y, K)]

    ABC = []
    for i in range(len(AB)):
        for j in range(Z):
            ABC.append(AB[i] + C[j])

    ABC.sort(reverse=True)

    return ABC[:K]


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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()))
X=[]

for i in A:
    for j in B:
        for k in C:
            X.append(i+j+k)

X=sorted(X,reverse=True)

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

Submission status: Time Limit Exceeded

Solution code:
x,y,z,k=map(int,input().split())
a,b,c=[list(map(int,input().split())) for i in range(3)]
l=sorted([bb+cc for bb in b for cc in c],reverse=1)[:k]
t=sorted([ll+aa for aa in a for ll in l],reverse=1)
for i in range(k):
    print(t[i])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    X, Y, Z, K = list(map(int, input().split()))
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    C = sorted(list(map(int, input().split())))

    AB = []
    for a in A:
        for b in B:
            AB.append(a+b)
    AB = sorted(AB, reverse=True)[:K]
    ABC = []
    for ab in AB:
        for c in C:
            ABC.append(ab+c)
    ABC = sorted(ABC, reverse=True)
    [print(ABC[i]) for i in range(K)]


if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

x, y, z, t = map(int, readline().split())
a = sorted(map(int, readline().split()), reverse=True)
b = sorted(map(int, readline().split()), reverse=True)
c = sorted(map(int, readline().split()), reverse=True)

ans = []

for i in range(len(a)):
    for j in range(len(b)):
        ans.append(a[i] + b[j])

ans = sorted(ans, reverse=True)
fin_ans = []
for j in range(len(c)):
    for i in range(min(len(ans), t)):
        fin_ans.append(ans[i] + c[j])

fin_ans = sorted(fin_ans, reverse=True)

for i in fin_ans[:t]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:

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()))

E = []
for a in range(len(A)):
    for b in range(len(B)):
        E.append(A[a]+B[b])

E.sort(reverse=True)
E = E[:K]

ans = []
for c in range(len(C)):
    for e in range(len(E)):
        ans.append(C[c]+E[e])
        
ans.sort(reverse=True)

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

Submission status: Time Limit Exceeded

Solution code:

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)

A = A[:K+1]
B = B[:K+1]
C = C[:K+1]

E = []
for a in range(len(A)):
    for b in range(len(B)):
        E.append(A[a]+B[b])

E.sort(reverse=True)
E = E[:K+1]

ans = []
for c in range(len(C)):
    for e in range(len(E)):
        ans.append(C[c]+E[e])
        
ans.sort(reverse=True)

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

Submission status: Time Limit Exceeded

Solution code:

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()))

sum = []
for x in range(X):
    for y in range(Y):
        for z in range(Z):
            sum.append(A[x] + B[y] + C[z])

sum.sort(reverse=True)

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

Submission status: Time Limit Exceeded

Solution code:
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()
b.sort()
c.sort()

from bisect import bisect_left, bisect_right

def C(x):
    # count "abc <= x"
    ret = 0
    for aa in a:
        for bb in b:
            idx = bisect_right(c, x - aa - bb)
            ret += idx
    return ret

kk = x * y * z - k + 1
lb = 0
ub = (10 ** 10) * 4
while ub - lb > 1:
    mid = (ub + lb) // 2
    if C(mid) >= kk:
        ub = mid
    else:
        lb = mid

kth = ub


l = []
for aa in a:
    for bb in b:
        idx = bisect_left(c, kth - aa - bb)
        # print(aa, bb, idx)
        for i in range(idx, z):
            l.append(aa + bb + c[i])


l.sort(reverse=True)
for ll in l:
    print(ll)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

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

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

# AとBを組み合わせたケーキの上位K位を作る
AB = []
for a in range(len(A)):
  for b in range(len(B)):
    AB += [A[a] + B[b]]
    
AB = sorted(AB,reverse = True)[:K]

# ABとCを組み合わせたケーキの上位K位を作る
ans = []
for ab in range(len(AB)):
  for c in range(len(C)):
    ans += [AB[ab] + C[c]]
    
ans = sorted(ans,reverse = True)[:K]
for a in ans:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

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

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

# Aからa個、Bからb個、Cからc個選ぶ
# a * b * c >= Kとなること
# 全探索する上で、条件から外れるものを除外する

ans = []
for a in range(min(K,len(A))):
  for b in range(len(B)):
    for c in range(len(C)):
      ans.append(A[a] + B[b] + C[c])
      if a * b * c > K:
        break

ans = sorted(ans,reverse = True)
for i in range(K):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

x, y, z, k = list(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 a:
    for j in b:
        ab.append(i+j)
ab.sort(reverse=True)

ab = ab[:k]

abc = []
for i in ab:
    for j in c:
        abc.append(i+j)
abc.sort(reverse=True)

for i in range(k):
    print(abc[i])

Submission status: Time Limit Exceeded

Solution code:
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 xi in range(x):
  for yi in range(y):
    AB.append(A[xi]+B[yi])

AB = sorted(AB,reverse=True)
C = sorted(C,reverse=True)

i=0
j=0

ABC = []
for ab in AB[:k]:
  for c in C[:k]:
    ABC.append(ab+c)

ABC = sorted(ABC,reverse=True)
for abc in ABC[:k]:
  print(abc)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
X,Y,Z,K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
B = [int(x) for x in stdin.readline().rstrip().split()]
C = [int(x) for x in stdin.readline().rstrip().split()]

AB = []
for a in A:
    for b in B:
        AB.append(a+b)
        
AB.sort(reverse=True)
C.sort(reverse=True)
ABC = []

for ab in AB[:K]:
    for c in C[:K]:
        ABC.append(ab+c)
        
ABC.sort(reverse=True)

for abc in ABC[:K]:
    print(abc)

Submission status: Time Limit Exceeded

Solution code:
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()))

'''
必ず3つからそれぞれ1つずつ取らないといけないので、a,bの組み合わせの大きい順
とa,b,cの組の大きい順で見たときの(a,b)の順は一致している
a,bの組み合わせのうち上からk番目以降は考える必要がない
'''
ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])
ab.sort(reverse=True)
ab = ab[:k]
rec = []
for i in range(min(x*y, k)):
    for j in range(z):
        rec.append(ab[i] + c[j])

rec.sort(reverse=True)
rec = rec[:k]
print(*rec, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
X, Y, Z, K = map(int, input().split())

A = sorted(list(map(int, input().split())))[::-1]
B = sorted(list(map(int, input().split())))[::-1]
C = sorted(list(map(int, input().split())))[::-1]

A_B = []
for a in A:
    for b in B:
        A_B.append(a + b)

A_B = sorted(A_B)

def bin_search(mid):
    res = 0
    idx = 0
    ans = []
    for c in C:
        while idx < len(A_B):
            if c + A_B[idx] >= mid:
                res += len(A_B) - idx
                ans += [i + c for i in A_B[idx:]]
                break
            else:
                idx += 1
    
    return res, ans

ok = 0
ng = pow(10, 10) * 3 + 1

while ok + 1 < ng:
    mid = (ok + ng) // 2
    res, ans = bin_search(mid)
    if res >= K:
        ok = mid
    else:
        ng = mid

res, ans = bin_search(ok)
for a in sorted(ans)[::-1][:K]:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
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)
To = [[[True] * Z for _ in range(Y)] for __ in range(X)]
Q = []
To[0][0][0] = False
heapq.heappush(Q, (-(A[0] + B[0] + C[0]), 0, 0, 0))
cnt = K
while cnt > 0:
    cnt -= 1
    ans, a, b, c = heapq.heappop(Q)
    print(-ans)
    if (a + 1 < X) and (To[a+1][b][c]):
        heapq.heappush(Q, (-(A[a + 1] + B[b] + C[c]), a + 1, b, c))
        To[a+1][b][c] = False
    if (b + 1 < Y) and (To[a][b+1][c]):
        heapq.heappush(Q, (-(A[a] + B[b + 1] + C[c]), a, b + 1, c))
        To[a][b+1][c] = False
    if (c + 1 < Z) and (To[a][b][c+1]):
        heapq.heappush(Q, (-(A[a] + B[b] + C[c + 1]), a, b, c + 1))
        To[a][b][c+1] = False

Submission status: Time Limit Exceeded

Solution code:
import heapq


X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))+[-100]*10
B = list(map(int, input().split()))+[-100]*10
C = list(map(int, input().split()))+[-100]*10
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
Done = [[[False] * Z for _ in range(Y)] for __ in range(X)]
Q = []
Done[0][0][0] = True
heapq.heappush(Q, (-(A[0] + B[0] + C[0]), 0, 0, 0))
cnt = K
while cnt > 0:
    cnt -= 1
    ans, a, b, c = heapq.heappop(Q)
    print(-ans)
    if (a + 1 < X) and not(Done[a+1][b][c]):
        heapq.heappush(Q, (-(A[a + 1] + B[b] + C[c]), a + 1, b, c))
        Done[a+1][b][c] = True
    if (b + 1 < Y) and not (Done[a][b+1][c]):
        heapq.heappush(Q, (-(A[a] + B[b + 1] + C[c]), a, b + 1, c))
        Done[a][b+1][c] = True
    if (c + 1 < Z) and not(Done[a][b][c+1]):
        heapq.heappush(Q, (-(A[a] + B[b] + C[c + 1]), a, b, c + 1))
        Done[a][b][c+1] = True

Submission status: Time Limit Exceeded

Solution code:
import heapq
x,y,z,k = map(int,input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
al = [[[0 for i in range(z)] for j in range(y)] for jj in range(x)]

hq = []
heapq.heappush(hq,(-(a[0]+b[0]+c[0]),0,0,0))
for i in range(k):
    hqi,ai,bi,ci = heapq.heappop(hq)
    print(-hqi)
    if ai+1 < x and al[ai+1][bi][ci] == 0:
        heapq.heappush(hq,(-(a[ai+1]+b[bi]+c[ci]),ai+1,bi,ci))
        al[ai+1][bi][ci] = -1
    if bi+1 < y and al[ai][bi+1][ci] == 0:
        heapq.heappush(hq,(-(a[ai]+b[bi+1]+c[ci]),ai,bi+1,ci))
        al[ai][bi+1][ci] = -1
    if ci+1 < z and al[ai][bi][ci+1] == 0:
        heapq.heappush(hq,(-(a[ai]+b[bi]+c[ci+1]),ai,bi,ci+1))
        al[ai][bi][ci+1] = -1

Submission status: Time Limit Exceeded

Solution code:
import heapq
X, Y, Z, K = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)
B = sorted([int(i) for i in input().split()], reverse=True)
C = sorted([int(i) for i in input().split()], reverse=True)

done = [[[False for k in range(Z)] for j in range(Y)] for i in range(X)]
done[0][0][0] = True

hq = [(-(A[0]+B[0]+C[0]), 0, 0, 0)]
heapq.heapify(hq)  # リストhqのheap化

ans = 0
D = [(1, 0, 0), (0, 1, 0), (0, 0, 1)]

for _ in range(K):
    s, i, j, k = heapq.heappop(hq)  # heap化されたリストhqから最小値を削除＆その最小値を出力
    print(-s)
    for d in D:
        ni, nj, nk = i+d[0], j+d[1], k+d[2]
        if ni < X and nj < Y and nk < Z and done[ni][nj][nk] is False:
            # heap化されたリストhqに要素xを追加
            heapq.heappush(hq, (-(A[ni]+B[nj]+C[nk]), ni, nj, nk))
            done[ni][nj][nk] = True

Submission status: Time Limit Exceeded

Solution code:



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)


"""
愚直解
X*Y*Z全部作って上から順にK個書き出す。普通に間に合わない
愚直解のいけてない部分として、X*Yを作った段階で、他のX*Yよりずっと小さいときに、Zとの積を見るまでもなくK番目までに入らないケースがある。
なんというか、　X*Y*Z　を　W*Z (W=X*Y)と置き換えたときに、Wの中で順位が低いものとZとの積を計算して他と比較する意味がない。
W = [9,8,7,6,5,4,3]
Z = [6,4,3,2,1]
K = 5
とかで考えると、Wが3や4のものは見る必要がない。
というのも、それより大きいWがK個以上あることが分かっているので、W*ZもK個以上大きいものが存在するといえるので。

なので、先にX*Yを計算して、その中で上位K個とZの積をとってさらにK個選べばいけそう


"""
W = []
for a in A:
    for b in B:
        W.append(a+b)

W.sort(reverse=True)
if len(W) > K:
    W = W[:K]
ans = []
for w in W:
    for c in C:
        ans.append(w+c)

ans.sort(reverse=True)
print(*ans[:K], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
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()))

li  = []

for i in a:
    for j in b:
        li.append(i+j)

li.sort(reverse=True)
li = li[:k]

lin = []

for i in li:
    for j in c:
        lin.append(i+j)

lin.sort(reverse=True)

for i in range(k):
    print(lin[i])

Submission status: Time Limit Exceeded

Solution code:
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()))
import heapq
ans = []
heapq.heapify(ans)
for a in A:
    for b in B:
        for c in C:
          heapq.heappush(ans,-(a+b+c))
for _ in range(K):
    i = heapq.heappop(ans)
    print(-i)

Submission status: Time Limit Exceeded

Solution code:
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()))

ans = []
for a in A:
    for b in B:
        for c in C:
          ans.append(-(a+b+c))
        
import heapq
heapq.heapify(ans)
for _ in range(K):
    i = heapq.heappop(ans)
    print(-i)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

X, Y, Z , K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))

ans_heapq = []

for i in range(X):
    for j in range(Y):
        for k in range(Z):
            abc = -1 * (A[i] + B[j] + C[k])
            heapq.heappush(ans_heapq, abc)
            
for _ in range(K):
    print(heapq.heappop(ans_heapq) * (-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

def main():
    X, Y, Z, K = map(int, readline().rstrip().split())
    A = list(map(int, readline().rstrip().split()))
    B = list(map(int, readline().rstrip().split()))
    C = list(map(int, readline().rstrip().split()))
    
    ab = [A[i] + B[j] for i in range(len(A)) for j in range(len(B))]
    ab = sorted(ab, reverse=True)[:K]

    abc = [ab[i] + C[j] for i in range(len(ab)) for j in range(len(C))]
    print(*sorted(abc, reverse=True)[:K], sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
from itertools import combinations

def main():
    X, Y, Z, K = map(int, readline().rstrip().split())
    A = list(map(int, readline().rstrip().split()))
    B = list(map(int, readline().rstrip().split()))
    C = list(map(int, readline().rstrip().split()))
    ab = []
    for a in A:
        for b in B:
            ab.append(a + b)
    ab = sorted(ab, reverse=True)[:K]
    abc = []
    for v in ab:
        for c in C:
            abc.append(v + c)
    
    print(*sorted(abc, reverse=True)[:K], sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq  # heapqライブラリのimport
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)
check=[[0,0,0]]
lst =[(-(A[0]+B[0]+C[0]),0,0,0)]
heapq.heapify(lst)
for r in range(K):
 a=lst[0][1]
 b=lst[0][2]
 c=lst[0][3] 
 print(lst[0][0]*(-1))
 heapq.heappop(lst)
 if a<X-1 :
  if [a+1,b,c] not in check:
   heapq.heappush(lst, (-(A[a+1]+B[b]+C[c]),a+1,b,c))
   check.append([a+1,b,c])
 if b<Y-1 :
  if [a,b+1,c] not in check:
   heapq.heappush(lst, (-(A[a]+B[b+1]+C[c]),a,b+1,c))
   check.append([a,b+1,c])
 if c<Z-1 :
  if [a,b,c+1] not in check:
   heapq.heappush(lst, (-(A[a]+B[b]+C[c+1]),a,b,c+1))
   check.append([a,b,c+1])

Submission status: Time Limit Exceeded

Solution code:
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=[0]*(X*Y)
t=0
for i in A:
 for j in B:
  AB[t]=i+j
  t+=1
AB.sort(reverse=True)
ABA=AB[0:min(K,X*Y)]
D=[0]*(Z*len(ABA))
t=0
for i in ABA:
 for j in C:
  D[t]=i+j
  t+=1
D.sort(reverse=True)
for i in range(K):
 print(D[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
x,y,z,k = map(int,readline().split())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]
c = [int(i) for i in readline().split()]
from bisect import bisect_left,insort
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

stop = 0
ans = []
cn = 0
for i in a:
  for j in b:
    for l in c:
      if i+j+l <= stop:
        break
      if cn >= k:
        if bisect_left(ans,i+j+l) > 0:
          insort(ans,i+j+l)
        else:
          stop = i+j+l
      else:
        insort(ans,i+j+l)
        cn += 1
        
ans = ans[::-1]
for i in ans[:k]:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
x,y,z,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
b = sorted(list(map(int,input().split())),reverse=True)
c = sorted(list(map(int,input().split())),reverse=True)

buf = []
for i in range(x):
    for j in range(y):
        buf.append(a[i]+b[j])

buf = sorted(buf,reverse=True)[:k]
ans = []

for i in buf:
    for j in range(z):
        ans.append(i+c[j])

ans = sorted(ans,reverse=True)
[print(ans[i]) for i in range(k)]

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    x,y,z,k=map(int,readline().split())
    a=list(map(int,readline().split()))
    b=list(map(int,readline().split()))
    c=list(map(int,readline().split()))

    d=list()
    for i in range(x):
        for j in range(y):
            d.append(a[i]+b[j])

    d.sort(reverse=True)
    if x*y>=k:
        d=d[:k]

    e=list()
    for i in range(len(d)):
        for j in range(z):
            e.append(d[i]+c[j])

    e.sort(reverse=True)
    for i in range(k):
        print(e[i])

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
x,y,z,k = map(int,input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
lst = [a+b for a in A for b in B]
lst.sort(reverse=True)
lst = [e+c for e in lst[:k] for c in C]
lst.sort(reverse=True)
for i in range(k): print(lst[i])

Submission status: Time Limit Exceeded

Solution code:
import itertools


def main():
    X, Y, Z, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    B = list(map(int, input().split(' ')))
    C = list(map(int, input().split(' ')))
    AB = list(map(sum, itertools.product(A, B)))
    AB.sort(reverse=True)
    AB = AB[:min([K, X * Y])]
    ABC = list(map(sum, itertools.product(AB, C)))
    ABC.sort(reverse=True)
    for ans in ABC[:K]:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():
    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()))

    AA = list(map(lambda x:x*(-1), A))
    BB = list(map(lambda x:x*(-1), B))
    CC = list(map(lambda x:x*(-1), C))

    ans = []
    heapq.heapify(ans)
    for a in AA:
        for b in BB:
            for c in CC:
                heapq.heappush(ans, a+b+c)
    
    for i in range(K):
        print(heapq.heappop(ans)*(-1))
main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify,heappop,heappush

X,Y,Z,K=map(int,input().split())
A=sorted(map(int,input().split()),reverse=True)
B=sorted(map(int,input().split()),reverse=True)
C=sorted(map(int,input().split()),reverse=True)
que=[[-(A[0]+B[0]+C[0]),0,0,0]];heapify(que)
Count=[[[0]*(Z+1) for i in range(Y+1)] for j in range(X+1)]

for i in range(K):
    p=heappop(que)
    print(-p[0])
    if p[1]<X-1 and Count[p[1]+1][p[2]][p[3]]==0:
        heappush(que,[-sum([A[p[1]+1],B[p[2]],C[p[3]]]),p[1]+1,p[2],p[3]])
        Count[p[1]+1][p[2]][p[3]]+=1
    if p[2]<Y-1 and Count[p[1]][p[2]+1][p[3]]==0:
        heappush(que,[-sum([A[p[1]],B[p[2]+1],C[p[3]]]),p[1],p[2]+1,p[3]])
        Count[p[1]][p[2]+1][p[3]]+=1
    if p[3]<Z-1 and Count[p[1]][p[2]][p[3]+1]==0:
        heappush(que,[-sum([A[p[1]],B[p[2]],C[p[3]+1]]),p[1],p[2],p[3]+1])
        Count[p[1]][p[2]][p[3]+1]+=1

Submission status: Time Limit Exceeded

Solution code:
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()))
taste = []
for i1 in a:
    for i2 in b:
        for i3 in c:
            taste.append(i1 + i2 + i3)
print(*(sorted(taste)[::-1])[:k], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
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)

ans = []
for i in range(min(K, len(AB))):
  for j in range(Z):
    ans.append(AB[i] + C[j])
ans.sort(reverse=True)

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

Submission status: Time Limit Exceeded

Solution code:
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()))
D=[]
for i in range(X):
    for j in range(Y):
        D.append(A[X-1-i]+B[Y-1-j])
D.sort()
ans=[]
for i in range(min(K,len(D))):
    for j in range(min(K,Z)):
        ans.append(D[len(D)-1-i]+C[Z-1-j])
ans.sort()
for i in range(K):
    print(ans[len(ans)-1-i])

Submission status: Time Limit Exceeded

Solution code:
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()
B.sort()
C.sort()
D=[]
for i in range(min(K,X)):
    for j in range(min(K,Y)):
        D.append(A[X-1-i]+B[Y-1-j])
D.sort()
ans=[]
for i in range(min(K,len(D))):
    for j in range(min(K,Z)):
        ans.append(D[len(D)-1-i]+C[Z-1-j])
ans.sort()
for i in range(K):
    print(ans[len(ans)-1-i])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

x, y, z, k = map(int, readline().split())
a = list(map(int, readline().split()))
b = list(map(int, readline().split()))
c = list(map(int, read().split()))
ab = [0] * x * y
for i, aa in enumerate(a):
    for j, bb in enumerate(b):
        ab[i * y + j] = aa + bb
ab = sorted(ab, reverse=True)[:k]
c = sorted(c, reverse=True)[:k]
ans = [0] * (k ** 2)
for i, abab in enumerate(ab):
    for j, cc in enumerate(c):
        ans[i * k + j] = abab + cc
ans.sort(reverse=True)
print('\n'.join(map(str, ans[:k])))

Submission status: Time Limit Exceeded

Solution code:
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)
E = []
for a in A:
    for b in B:
        E.append(a + b)
E.sort(reverse=True)
E = E[:K]
ans = []
for e in E:
    for c in C:
        ans.append(e + c)
ans.sort(reverse=True)
ans = ans[:K]
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
x, y, z, K = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)
B = sorted(map(int, input().split()), reverse=True)
C = sorted(map(int, input().split()), reverse=True)


def check(P):
    cnt = 0
    for i in range(x):
        for j in range(y):
            for k in range(z):
                if A[i]+B[j]+C[k] < P:
                    break
                cnt += 1
                if K <= cnt:
                    return True
    return False


L = 1
R = 10**14
while L != R-1:
    M = (L+R)//2
    if check(M):
        L = M
    else:
        R = M

ans = []
for i in range(x):
    for j in range(y):
        for k in range(z):
            if A[i]+B[j]+C[k] <= L:
                break
            ans.append(A[i]+B[j]+C[k])

ans.sort(reverse=True)
for i in range(K):
    if i < len(ans):
        print(ans[i])
    else:
        print(L)

Submission status: Time Limit Exceeded

Solution code:
x, y, z, K = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)
B = sorted(map(int, input().split()), reverse=True)
C = sorted(map(int, input().split()), reverse=True)


def check(P):
    cnt = 0
    for i in range(x):
        for j in range(y):
            for k in range(z):
                if A[i]+B[j]+C[k] < P:
                    break
                cnt += 1
                if K <= cnt:
                    return True
    return False


L = 1
R = 10**14
while L != R-1:
    M = (L+R)//2
    if check(M):
        L = M
    else:
        R = M

ans = []
for i in range(x):
    for j in range(y):
        for k in range(z):
            if A[i]+B[j]+C[k] < L:
                break
            ans.append(A[i]+B[j]+C[k])
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])