Buggy python submission (verdict: Time Limit Exceeded):
#PypyでもTLE A[:half]のような箇所が遅い？
# -->二分探索のスタート地点を変えるだけで処理すると毎回新規リストを作らなくなる

N = int(input())
A = list(map(int, input().split()))
for i in range(1, N):
    A[i] += A[i - 1]

def calc(lb, ub):
    max_num = A[ub]
    lb -= 1
    if lb == -1:
        min_num = 0
    else:
        min_num = A[lb]
    total = A[ub] - min_num
    # print (total)
    while (ub - lb) > 1:
        mid = (lb + ub)//2
        if A[mid] - min_num > total/2:
            ub = mid
        else:
            lb = mid
    # print ('ub', ub)
    a1, b1 = A[ub] - min_num, max_num - A[ub]
    diff1 = abs(b1 - a1)
    # print ('diff1', diff1)
    a2, b2 = A[ub - 1] - min_num, max_num - A[ub - 1]
    diff2 = abs(b2 - a2)
    # print ('diff2', diff2)
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1

# print (calc(A, 0))
# half = 2
# P, Q = calc(0, half - 1)
# print (P, Q)

ans = 10 ** 9
for half in range(2, N - 1):
    # print (A[:half], end = ' ')
    # print (A[half:])
    P, Q = calc(0, half - 1)
    R, S = calc(half, N - 1)
    # print (P, Q, R, S)
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    # print (tmp)
    ans = min(tmp, ans)

# print ('ans', ans)
print (ans)


Fixed submission:
#PypyでもTLE A[:half]のような箇所が遅い？

N = int(input())
A = list(map(int, input().split()))
for i in range(1, N):
    A[i] += A[i - 1]

def calc(lb, ub):
    max_num = A[ub]
    lb -= 1
    if lb == -1:
        min_num = 0
    else:
        min_num = A[lb]
    total = A[ub] - min_num
    # print (total)
    while (ub - lb) > 1:
        mid = (lb + ub)//2
        if A[mid] - min_num > total/2:
            ub = mid
        else:
            lb = mid
    # print ('ub', ub)
    a1, b1 = A[ub] - min_num, max_num - A[ub]
    diff1 = abs(b1 - a1)
    # print ('diff1', diff1)
    a2, b2 = A[ub - 1] - min_num, max_num - A[ub - 1]
    diff2 = abs(b2 - a2)
    # print ('diff2', diff2)
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1

# print (calc(A, 0))
# half = 2
# P, Q = calc(0, half - 1)
# print (P, Q)

ans = 10 ** 9
for half in range(2, N - 1):
    # print (A[:half], end = ' ')
    # print (A[half:])
    P, Q = calc(0, half - 1)
    R, S = calc(half, N - 1)
    # print (P, Q, R, S)
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    # print (tmp)
    ans = min(tmp, ans)

# print ('ans', ans)
print (ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
for i in range(1, N):
    A[i] += A[i - 1]

def calc(lst, min_num):
    total = lst[-1] - min_num
    # print (total)
    lb = -1
    ub = len(lst)
    while (ub - lb) > 1:
        mid = (lb + ub)//2
        if lst[mid] - min_num > total/2:
            ub = mid
        else:
            lb = mid
    # print ('ub', ub)
    a1, b1 = lst[ub] - min_num, lst[-1] - lst[ub]
    diff1 = abs(b1 - a1)
    # print ('diff1', diff1)
    a2, b2 = lst[ub - 1] - min_num, lst[-1] - lst[ub - 1]
    diff2 = abs(b2 - a2)
    # print ('diff2', diff2)
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1

# print (calc(A, 0))

ans = 10 ** 9
for half in range(2, N - 1):
    # print (A[:half], end = ' ')
    # print (A[half:])
    P, Q = calc(A[:half], 0)
    R, S = calc(A[half:], A[half - 1])
    # print (P, Q, R, S)
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    # print (tmp)
    ans = min(tmp, ans)

# print ('ans', ans)
print (ans)


Fixed submission:
#PypyでもTLE A[:half]のような箇所が遅い？

N = int(input())
A = list(map(int, input().split()))
for i in range(1, N):
    A[i] += A[i - 1]

def calc(lb, ub):
    max_num = A[ub]
    lb -= 1
    if lb == -1:
        min_num = 0
    else:
        min_num = A[lb]
    total = A[ub] - min_num
    # print (total)
    while (ub - lb) > 1:
        mid = (lb + ub)//2
        if A[mid] - min_num > total/2:
            ub = mid
        else:
            lb = mid
    # print ('ub', ub)
    a1, b1 = A[ub] - min_num, max_num - A[ub]
    diff1 = abs(b1 - a1)
    # print ('diff1', diff1)
    a2, b2 = A[ub - 1] - min_num, max_num - A[ub - 1]
    diff2 = abs(b2 - a2)
    # print ('diff2', diff2)
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1

# print (calc(A, 0))
# half = 2
# P, Q = calc(0, half - 1)
# print (P, Q)

ans = 10 ** 9
for half in range(2, N - 1):
    # print (A[:half], end = ' ')
    # print (A[half:])
    P, Q = calc(0, half - 1)
    R, S = calc(half, N - 1)
    # print (P, Q, R, S)
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    # print (tmp)
    ans = min(tmp, ans)

# print ('ans', ans)
print (ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
for i in range(1, N):
    A[i] += A[i - 1]

def calc(lst, min_num):
    total = lst[-1] - min_num
    # print (total)
    lb = -1
    ub = len(lst)
    while (ub - lb) > 1:
        mid = (lb + ub)//2
        if lst[mid] - min_num > total/2:
            ub = mid
        else:
            lb = mid
    # print ('ub', ub)
    a1, b1 = lst[ub] - min_num, lst[-1] - lst[ub]
    diff1 = abs(b1 - a1)
    # print ('diff1', diff1)
    a2, b2 = lst[ub - 1] - min_num, lst[-1] - lst[ub - 1]
    diff2 = abs(b2 - a2)
    # print ('diff2', diff2)
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1

# print (calc(A, 0))

ans = 10 ** 9
for half in range(2, N - 1):
    # print (A[:half], end = ' ')
    # print (A[half:])
    P, Q = calc(A[:half], 0)
    R, S = calc(A[half:], A[half - 1])
    # print (P, Q, R, S)
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    # print (tmp)
    ans = min(tmp, ans)

# print ('ans', ans)
print (ans)


Fixed submission:
#PypyでもTLE A[:half]のような箇所が遅い？

N = int(input())
A = list(map(int, input().split()))
for i in range(1, N):
    A[i] += A[i - 1]

def calc(lb, ub):
    max_num = A[ub]
    lb -= 1
    if lb == -1:
        min_num = 0
    else:
        min_num = A[lb]
    total = A[ub] - min_num
    # print (total)
    while (ub - lb) > 1:
        mid = (lb + ub)//2
        if A[mid] - min_num > total/2:
            ub = mid
        else:
            lb = mid
    # print ('ub', ub)
    a1, b1 = A[ub] - min_num, max_num - A[ub]
    diff1 = abs(b1 - a1)
    # print ('diff1', diff1)
    a2, b2 = A[ub - 1] - min_num, max_num - A[ub - 1]
    diff2 = abs(b2 - a2)
    # print ('diff2', diff2)
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1

# print (calc(A, 0))
# half = 2
# P, Q = calc(0, half - 1)
# print (P, Q)

ans = 10 ** 9
for half in range(2, N - 1):
    # print (A[:half], end = ' ')
    # print (A[half:])
    P, Q = calc(0, half - 1)
    R, S = calc(half, N - 1)
    # print (P, Q, R, S)
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    # print (tmp)
    ans = min(tmp, ans)

# print ('ans', ans)
print (ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [0] + list(map(int, input().split()))
for i in range(1, N + 1):
    A[i] += A[i - 1]


# print (A)

ans = 10 ** 9

#基準を求める
stan = A[N]//4

for i in range(2 ** 3):
    PQRS = [0, 0, 0, 0]
    index = 1
    prev_index = 0
    for j in range(3):
        if (i >> j) & 1: #基準以上にするとき
            while A[index] - A[prev_index] < stan and index < N:
                index += 1
            PQRS[j] = A[index] - A[prev_index]
            prev_index = index
            # print (1, end = '')
        else: #基準以下にするとき
            while A[index] - A[prev_index] < stan and index < N:
                index += 1
            PQRS[j] = A[index - 1] - A[prev_index]
            prev_index = index - 1
            # print (0, end = '')
    PQRS[3] = A[N] - A[prev_index]
    # print (PQRS, end = ' ')
    # print (max(PQRS) - min(PQRS))
    ans = min((max(PQRS) - min(PQRS)), ans)

stan = (A[N] + 3)//4

for i in range(2 ** 3):
    PQRS = [0, 0, 0, 0]
    index = 1
    prev_index = 0
    for j in range(3):
        if (i >> j) & 1: #基準以上にするとき
            while A[index] - A[prev_index] < stan and index < N:
                index += 1
            PQRS[j] = A[index] - A[prev_index]
            prev_index = index
            # print (1, end = '')
        else: #基準以下にするとき
            while A[index] - A[prev_index] < stan and index < N + 1:
                index += 1
                if index == N + 1:
                    break
            PQRS[j] = A[index - 1] - A[prev_index]
            prev_index = index - 1
            # print (0, end = '')
    PQRS[3] = A[N] - A[prev_index]
    # print (PQRS, end = ' ')
    # print (max(PQRS) - min(PQRS))
    ans = min((max(PQRS) - min(PQRS)), ans)


print (ans)

Fixed submission:
#PypyでもTLE A[:half]のような箇所が遅い？

N = int(input())
A = list(map(int, input().split()))
for i in range(1, N):
    A[i] += A[i - 1]

def calc(lb, ub):
    max_num = A[ub]
    lb -= 1
    if lb == -1:
        min_num = 0
    else:
        min_num = A[lb]
    total = A[ub] - min_num
    # print (total)
    while (ub - lb) > 1:
        mid = (lb + ub)//2
        if A[mid] - min_num > total/2:
            ub = mid
        else:
            lb = mid
    # print ('ub', ub)
    a1, b1 = A[ub] - min_num, max_num - A[ub]
    diff1 = abs(b1 - a1)
    # print ('diff1', diff1)
    a2, b2 = A[ub - 1] - min_num, max_num - A[ub - 1]
    diff2 = abs(b2 - a2)
    # print ('diff2', diff2)
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1

# print (calc(A, 0))
# half = 2
# P, Q = calc(0, half - 1)
# print (P, Q)

ans = 10 ** 9
for half in range(2, N - 1):
    # print (A[:half], end = ' ')
    # print (A[half:])
    P, Q = calc(0, half - 1)
    R, S = calc(half, N - 1)
    # print (P, Q, R, S)
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    # print (tmp)
    ans = min(tmp, ans)

# print ('ans', ans)
print (ans)