Problem p03078 (python)

Fixed submission:
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)

ab = []
for ai in a:
    for bj in b:
        ab.append(ai+bj)
ab.sort(reverse=True)
ab = ab[:K]
cond = []
for abi in ab:
    for cj in c:
        cond.append(abi+cj)
cond = sorted(cond, reverse=True)[:K]
for condi in cond:
    print(condi)

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

def f(thres:int)->bool:
    """return (おいしさが thres を超える組み合わせ) >= K
    """
    global K
    cnt = 0
    for a in range(X):
        for b in range(Y):
            for c in range(Z):
                if A[a]+B[b]+C[c]<thres:
                    break
                cnt += 1
                if cnt > K:
                    return False
    return True

def binary_search(f, s:int, t:int)->int:
    """f: function(x:int)->bool
    f(s)=False, f(t)=True，f は広義単調増加
    return : [s, t) での f(x)=True なる最小のx
    """
    ng = s-1
    ok = t
    while ok - ng > 1:
        mid = (ok + ng)//2
        if f(mid): ok = mid
        else:      ng = mid
        # print(ng, ok, ok-ng)

    if ok==t:
        raise(ValueError("For all x, f(x)=False"))
    return ok

M = A[0]+B[0]+C[0]
m = A[-1]+B[-1]+C[-1]
# print(f(m), f(M))
thres = binary_search(f, m, M+1)
ans = []
for a in range(X):
    for b in range(Y):
        for c in range(Z):
            if A[a]+B[b]+C[c]<thres:
                break
            ans.append(A[a]+B[b]+C[c])
            if len(ans)==K:
                ans.sort(reverse=True)
                print("\n".join(map(str, ans)))

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

def f(thres:int)->bool:
    """return (おいしさが thres を超える組み合わせ) >= K
    """
    global K
    cnt = 0
    for a in range(X):
        for b in range(Y):
            for c in range(Z):
                if A[a]+B[b]+C[c]<thres:
                    break
                cnt += 1
                if cnt > K:
                    return False
    return True

def binary_search(f, s:int, t:int)->int:
    """f: function(x:int)->bool
    f(s)=False, f(t)=True，f は広義単調増加
    return : [s, t) での f(x)=True なる最小のx
    """
    ng = s-1
    ok = t
    while ok - ng > 1:
        mid = (ok + ng)//2
        if f(mid): ok = mid
        else:      ng = mid
        # print(ng, ok, ok-ng)

    if ok==t:
        raise(ValueError("For all x, f(x)=False"))
    return ok

M = A[0]+B[0]+C[0]
m = A[-1]+B[-1]+C[-1]
# print(f(m), f(M))
thres = binary_search(f, m, M+1)
ans = []
for a in range(X):
    for b in range(Y):
        for c in range(Z):
            if A[a]+B[b]+C[c]<thres:
                break
            ans.append(A[a]+B[b]+C[c])
            if len(ans)==K:
                ans.sort(reverse=True)
                print("\n".join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
imort 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)

ABC = []
for a in range(X):
    for b in range(Y):
        if (a+1)*(b+1) > K:
            break
        for c in range(Z):
            if (a+1)*(b+1)*(c+1) > K:
                break
            ABC.append(A[a] + B[b] + C[c])
ABC.sort(reverse=True)
print("\n".join(map(str, ABC[:K])))

Buggy submission (verdict: Runtime Error):
if __name__=="__main__":
    import sys
    import heapq
    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)

    sums = heapq([])
    lower = a[min(X-1,14)]+b[min(Y-1,14)]+c[min(Z-1,14)]
    b_max,c_max = max(b),max(c)
    for i in range(X):
        if a[i]+b_max+c_max<lower:
            break
        for j in range(Y):
            if a[i]+b[j]+c_max<lower:
                break
            for k in range(Z):
                s = a[i]+b[j]+c[k]
                if s<lower:
                    break
                heapq.heappush(sums, s)
    for si in sums[:K]:
        print(si)