Problem:
 Score : 600 points    Problem Statement Snuke has an integer sequence A of length N .  He will make three cuts in A and divide it into four (non-empty) contiguous subsequences B, C, D and E .
The positions of the cuts can be freely chosen.  Let P,Q,R,S be the sums of the elements in B,C,D,E , respectively.
Snuke is happier when the absolute difference of the maximum and the minimum among P,Q,R,S is smaller.
Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S .      Constraints  4 \leq N \leq 2 \times 10^5  1 \leq A_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  A_1  A_2  ...  A_N       Output Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S .        Sample Input 1 5
3 2 4 1 2      Sample Output 1 2  If we divide A as B,C,D,E=(3),(2),(4),(1,2) , then P=3,Q=2,R=4,S=1+2=3 .
Here, the maximum and the minimum among P,Q,R,S are 4 and 2 , with the absolute difference of 2 .
We cannot make the absolute difference of the maximum and the minimum less than 2 , so the answer is 2 .       Sample Input 2 10
10 71 84 33 6 47 23 25 52 64      Sample Output 2 36       Sample Input 3 7
1 2 3 1000000000 4 5 6      Sample Output 3 999999994

Solution (Python):
from itertools import accumulate


def run(n, a):
    
    sum_a = list(accumulate(a))
    li = 0
    ri = 2
    t = sum_a[-1]
    diff = sum_a[-1]
    
    
    
    
    
    
    
    for i in range(1, n-2):
        while sum_a[i] > sum_a[li+1] + sum_a[li]:
            li += 1
        while t + sum_a[i] > sum_a[ri+1] + sum_a[ri]:
            ri += 1
        p = sum_a[li]
        q = sum_a[i] - p
        r = sum_a[ri] - q - p
        s = t - sum_a[ri]
        diff = min(diff, max(p, q, r, s) - min(p, q, r, s))
    return diff


def read_line():
    n = int(input())
    a = list(map(int, input().split()))
    return (n, a)


def main():
    n, a = read_line()
    print(run(n, a))


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = [int(_) for _ in input().split()]

i, j, k = 1, 2, 3
B, C, D, E = A[0], A[1], A[2], sum(A[3:])

result = 10 ** 20

while 1:

    while 1:   
        newB, newC = B + A[i], C - A[i]
        if abs(B - C) < abs(newB - newC):
            break
        i += 1
        B, C = newB, newC

    while 1:   
        newD, newE = D + A[k], E - A[k]
        if abs(D - E) < abs(newD - newE):
            break
        k += 1
        D, E = newD, newE

    r = max(B, C, D, E) - min(B, C, D, E)
    result = min(result, r)

    C, D = C + A[j], D - A[j]
    j += 1
    if j == N - 1:
        break
    
print(result)

Solution (Python):
from itertools import accumulate, islice
from bisect import bisect_left

n = int(input())
xs = [int(x) for x in input().split()]

ys = list(accumulate(xs))
zs, total = ys[:-1], ys[-1]

res = max(xs) - min(xs)
for i, z in islice(enumerate(zs), 1, n-1):
    j = bisect_left(zs, z//2)
    splits = ((zs[j+k], z - zs[j+k]) for k in (-1, 0, 1) if 0 <= j+k <= i)
    a, b = min(splits, key=lambda s:abs(s[0]-s[1]))

    j = bisect_left(zs, (total - z)//2 + z)
    splits = ((zs[j+k] - z, total - zs[j+k]) for k in (-1, 0, 1) if i <= j+k <= n-2)
    c, d = min(splits, key=lambda s:abs(s[0]-s[1]))

    minn, _, _, maxx = sorted((a,b,c,d))
    if maxx - minn < res:
        res = maxx - minn

print(res)

Solution (Python):
from itertools import accumulate, islice
from bisect import bisect_left

n = int(input())
xs = [int(x) for x in input().split()]
ys = list(accumulate(xs))
zs, total = ys[:-1], ys[-1]

rs = range(2, n-2)
v = []
for i, z in islice(enumerate(zs), 1, n-1):
    j = bisect_left(zs, z//2)
    splits = ((zs[j+k], z - zs[j+k]) for k in (-1, 0, 1) if 0 <= j+k <= i)
    a, b = min(splits, key=lambda s:abs(s[0]-s[1]))

    j = bisect_left(zs, (total - z)//2 + z)
    splits = ((zs[j+k] - z, total - zs[j+k]) for k in (-1, 0, 1) if i <= j+k <= n-2)
    c, d = min(splits, key=lambda s:abs(s[0]-s[1]))

    minn, _, _, maxx = sorted((a,b,c,d))
    v.append(maxx - minn)

print(min(v) if v else max(xs) - min(xs))

Solution (Python):
from itertools import accumulate
import bisect

N=int(input())
A=[int(x) for x in input().split()]
S=list(accumulate(A))

def solve(x):
  cnt=S[x]
  L=bisect.bisect_left(S,cnt/2)
  R=bisect.bisect_left(S,(cnt+S[N-1])/2)
  L2=L-1
  R2=R-1
  res=10**10
  if R < N:
    ans=[S[L],cnt-S[L],S[R]-cnt,S[N-1]-S[R]]
    ans2=[S[L2],cnt-S[L2],S[R]-cnt,S[N-1]-S[R]]
    res=min(res,max(ans)-min(ans),max(ans2)-min(ans2))
  if R2 < N:
    ans3=[S[L],cnt-S[L],S[R2]-cnt,S[N-1]-S[R2]]
    ans4=[S[L2],cnt-S[L2],S[R2]-cnt,S[N-1]-S[R2]]
    res=min(res,max(ans3)-min(ans3),max(ans4)-min(ans4))
  return res

res=10**10
for i in range(N):
  a=solve(i)
  res=min(res,a)
print(res)

Solution (Python):


N = int(input())
A = [int(t) for t in input().split()]
if len(A) != N: raise

def left_sum_cut(A):
    """左部分和と左部分列を均等に分ける位置を返す"""
    A = list(A)

    
    leftsum = [0] * len(A)
    leftsum[0] = A[0]
    for i in range(1, len(A)):
        leftsum[i] = leftsum[i-1] + A[i]

    
    leftcut = [0] * len(A)
    leftcut[0] = None
    leftcut[1] = 0
    for i in range(2, len(A)):
        j = leftcut[i-1]
        m = float('inf')
        while j <= i - 1:
            suml = leftsum[j]
            sumr = leftsum[i] - suml
            if m <= abs(suml - sumr): break
            m = abs(suml - sumr)
            j += 1
        leftcut[i] = j - 1
    return leftsum, leftcut

leftsum,  leftcut  = left_sum_cut(A)
rightsum, rightcut = left_sum_cut(reversed(A))


m = float('inf')
for i in range(1, N - 2):
    P = leftsum[leftcut[i]]
    Q = leftsum[i] - P
    S = rightsum[rightcut[N - 1 - (i + 1)]]
    R = rightsum[N - 1 - (i + 1)] - S
    m = min(max(P, Q, R, S) - min(P, Q, R, S), m)
print(m)

Solution (Python):
from itertools import accumulate
input()
*s, = accumulate(map(int, input().split()))
l,r,t = 0,2,s[-1]
c = t
for m in s[1:-2]:
    while t+m > s[r]+s[r+1]:
        r += 1
    while m > s[l]+s[l+1]:
        l += 1
    x = sorted([s[l],m-s[l],s[r]-m,t-s[r]])
    c = min(c,x[-1]-x[0])
print(c)

Solution (Python):
from itertools import accumulate
n=int(input())
a=list(map(int, input().split()))
acc=list(accumulate(a))
left=0; center=1; right=2
ans=float('inf')
score=[acc[left], acc[center]-acc[left], acc[right]-acc[center], acc[n-1]-acc[right]]
nextS=[acc[left+1], acc[center]-acc[left+1], acc[right+1]-acc[center], acc[n-1]-acc[right+1]]
for center in range(1,n-1):
    while abs(score[1]-score[0]) > abs(nextS[1]-nextS[0]):
        left+=1
        score[0]+=a[left]
        score[1]-=a[left]
        nextS[0]+=a[left+1]
        nextS[1]-=a[left+1]
    while abs(score[3]-score[2]) > abs(nextS[3]-nextS[2]):
        right+=1
        score[2]+=a[right]
        score[3]-=a[right]
        nextS[2]+=a[right+1]
        nextS[3]-=a[right+1]
    ans=min(ans, max(score)-min(score))
    score[1]+=a[center+1]
    score[2]-=a[center+1]
    nextS[1]+=a[center+1]
    nextS[2]-=a[center+1]
print(ans)

Solution (Python):
from itertools import accumulate
n=int(input())
a=list(map(int, input().split()))
acc=list(accumulate(a))
left=0; right=2
ans=float('inf')
for center in range(1,n-1):
    while abs(acc[center]-acc[left]-acc[left]) > abs(acc[center]-acc[left+1]-acc[left+1]):
        left+=1 
    while abs(acc[n-1]-acc[right]-(acc[right]-acc[center])) > abs(acc[n-1]-acc[right+1]-(acc[right+1]-acc[center])):
        right+=1
    score=acc[left], acc[center]-acc[left], acc[right]-acc[center], acc[n-1]-acc[right]
    ans=min(ans, max(score)-min(score))

print(ans)

Solution (Python):
from itertools import accumulate
n=int(input())
a=list(map(int, input().split()))
acc=list(accumulate(a))
sumA=acc[-1]
cut=[0, 1, 2, len(a)-1]
score=[acc[cut[0]], acc[cut[1]]-acc[cut[0]], acc[cut[2]]-acc[cut[1]], acc[cut[3]]-acc[cut[2]]]
ans=max(score)-min(score)
for i in range(1,len(a)-1):
    cut[1]=i    
    while abs(acc[cut[1]]-acc[cut[0]]-acc[cut[0]]) > abs(acc[cut[1]]-acc[cut[0]+1]-acc[cut[0]+1]):
        cut[0]+=1 
    while abs(acc[cut[3]]-acc[cut[2]]-(acc[cut[2]]-acc[cut[1]])) > abs(acc[cut[3]]-acc[cut[2]+1]-(acc[cut[2]+1]-acc[cut[1]])):
        cut[2]+=1
    score=[acc[cut[0]], acc[cut[1]]-acc[cut[0]], acc[cut[2]]-acc[cut[1]], acc[cut[3]]-acc[cut[2]]]
    ans=min(ans, max(score)-min(score))

print(ans)

Solution (Python):
from itertools import *
input()
s=list(accumulate(map(int,input().split())))
l,r,t=0,2,s[-1];a=t
for m in s[1:-2]:
    while abs(t-2*s[r]+m)>abs(t-2*s[r+1]+m):r+=1
    while abs(m-2*s[l])>abs(m-2*s[l+1]):l+=1
    x=sorted([s[l],m-s[l],s[r]-m,t-s[r]])
    a=min(a,x[3]-x[0])
print(a)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

ans = float('inf')
cumsum = []
sum = 0
for a in A:
    sum += a
    cumsum.append(sum)

l = 0
r = 2
for m in range(1, N-2):
    
    P = cumsum[l]
    Q = cumsum[m] - cumsum[l]
    dist = abs(P-Q)
    while True:
        P_ = cumsum[l+1]
        Q_ = cumsum[m] - cumsum[l+1]
        dist_ = abs(P_ - Q_)
        if dist < dist_: break
        P, Q, dist = P_, Q_, dist_
        l += 1

    
    R = cumsum[r] - cumsum[m]
    S = cumsum[-1] - cumsum[r]
    dist = abs(S-R)
    while True:
        R_ = cumsum[r+1] - cumsum[m]
        S_ = cumsum[-1] - cumsum[r+1]
        dist_ = abs(R_ - S_)
        if dist < dist_: break
        R, S, dist = R_, S_, dist_
        r += 1

    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
print(ans)

Solution (Python):
from itertools import *
n=int(input())
sumA=[0]+list(accumulate(map(int,input().split())))
def check(l,m,r):
    if m==r:return False
    tmp=sumA[r]+sumA[l]
    return abs(tmp-sumA[m+1]*2)<abs(tmp-sumA[m]*2)
res=float('inf')
li,ri=1,3
for mid in range(2,n-1):
    while check(0,li,mid):li+=1
    while check(mid,ri,n):ri+=1
    x=sorted([sumA[li],sumA[mid]-sumA[li],sumA[ri]-sumA[mid],sumA[n]-sumA[ri]])
    tmp=x[3]-x[0]
    if tmp<res:res=tmp
print(res)

Solution (Python):

n = int(input())
a = list(map(int, input().split()))
s = [a[0]]
for i in range(n-1):
    s.append(s[i] + a[i+1])
ans = s[n-1]



j = 0
k = 2             
for i in range(1, (n - 3) + 1):
    
    
    

    
    
    
    
    
    while abs(s[i] - 2 * s[j]) > abs(s[i] - 2 * s[j+1]):
        j += 1

    
    
    
    
    
    while abs(s[n-1] - 2 * s[k] + s[i]) > abs(s[n-1] - 2 * s[k+1] + s[i]):
        k += 1
             
    pqrs = list((s[j],s[i]-s[j],s[k]-s[i],s[n-1]-s[k]))
    ans = min(ans, max(pqrs) - min(pqrs))
print(ans)

Solution (Python):
def d_equal_cut(N, A):
    import itertools
    import bisect

    cumsum = [0] + list(itertools.accumulate(A))  

    def get_sum(left, right):
        
        return cumsum[right+1] - cumsum[left]

    def get_optimum_division(left, right):
        
        total = get_sum(left, right)
        
        
        
        mid = bisect.bisect_right(
            cumsum, cumsum[left] + total/2, left+1, right+1) - 1

        
        
        
        diff1, diff2 = float('inf'), float('inf')
        if mid != left:
            sum_L1 = get_sum(left, mid-1)
            sum_R1 = get_sum(mid, right)
            diff1 = abs(sum_L1 - sum_R1)
        if mid != right:
            sum_L2 = get_sum(left, mid)
            sum_R2 = get_sum(mid+1, right)
            diff2 = abs(sum_L2 - sum_R2)
        return [sum_L1, sum_R1] if diff1 <= diff2 else [sum_L2, sum_R2]

    
    ans = float('inf')
    
    
    
    for mid_cut in range(1, (N-3) + 1):
        total = []
        total.extend(get_optimum_division(0, mid_cut))
        total.extend(get_optimum_division(mid_cut+1, N-1))
        ans = min(ans, abs(max(total) - min(total)))
    return ans

N = int(input())
A = [int(i) for i in input().split()]
print(d_equal_cut(N, A))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))

pre = [0]
for i in range(1,N+1):
    pre.append(pre[i-1] + A[i-1])

L = 1
r = 3
ans = 10**18
        
for i in range(2,N-1):
    while L + 1 < i and abs(pre[L+1] - pre[i] + pre[L+1]) < abs(pre[L] - pre[i] + pre[L]):
        L += 1

    while r <= i or (r + 1 < N and abs(pre[r+1] - pre[i] - pre[N] + pre[r+1]) < abs(pre[r] - pre[i] - pre[N] + pre[r])):
        r += 1

    ans = min(ans,max(pre[L],pre[i]-pre[L],pre[r]-pre[i],pre[N]-pre[r]) - \
          min(pre[L],pre[i]-pre[L],pre[r]-pre[i],pre[N]-pre[r]))

print(ans)

Solution (Python):
n=int(input())
xs=[int(s) for s in input().split()]
for i in range(1,n):
    xs[i]+=xs[i-1]
xs_last=xs[n-1]
ans=xs_last
l=0
r=2
for c in range(1,n-2):
    xs_center=xs[c]
    while l<c-1:
        if xs_center<xs[l+1]*2:
            if (xs[l+1]+xs[l])<xs_center:
                l+=1
            break
        l+=1
    while r<n-2:
        if xs_last+xs_center<2*xs[r+1]:
            if (xs[r+1]+xs[r])<xs_last+xs_center:
                r+=1
            break
        r+=1
    pqrs=[xs[l],xs_center-xs[l],xs[r]-xs_center,xs_last-xs[r]]
    ans=min(ans,max(pqrs)-min(pqrs))
print(ans)

Solution (Python):
N = int(input())
A_list = [int(elem) for elem in input().split(' ')]
assert N >= 4
assert len(A_list) == N


cuml_A_list = [0] * N
cuml_A_list[0] = A_list[0]
for i in range(1, N):
    cuml_A_list[i] = cuml_A_list[i-1] + A_list[i]

best_diff = max(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])\
        - min(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])

left_sep = 0
right_sep = 2


for mid_sep in range(1, N - 2):
    left_sum = cuml_A_list[mid_sep - 1]
    right_sum = cuml_A_list[-1] - cuml_A_list[mid_sep - 1]

    while abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep]) > abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep + 1]):
        left_sep += 1
    while abs(cuml_A_list[-1] - 2*cuml_A_list[right_sep] + cuml_A_list[mid_sep]) > abs(cuml_A_list[-1] - 2*cuml_A_list[right_sep + 1] + cuml_A_list[mid_sep]):
        right_sep += 1
    diff = max(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])\
        - min(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])
    best_diff = min(best_diff, diff)
print(best_diff)

Solution (Python):
N = int(input())
A_list = [int(elem) for elem in input().split(' ')]
assert N >= 4
assert len(A_list) == N


cuml_A_list = [0] * N
cuml_A_list[0] = A_list[0]
for i in range(1, N):
    cuml_A_list[i] = cuml_A_list[i-1] + A_list[i]

best_diff = max(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])\
        - min(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])

left_sep = 0
right_sep = 2


for mid_sep in range(1, N - 2):
    left_sum = cuml_A_list[mid_sep - 1]
    right_sum = cuml_A_list[-1] - cuml_A_list[mid_sep - 1]

    while abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep]) > abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep + 1]):
        left_sep += 1
    while abs(cuml_A_list[-1] - 2*cuml_A_list[right_sep] + cuml_A_list[mid_sep]) > abs(cuml_A_list[-1] - 2*cuml_A_list[right_sep + 1] + cuml_A_list[mid_sep]):
        right_sep += 1
    diff = max(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])\
        - min(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])
    best_diff = min(best_diff, diff)
print(best_diff)

Solution (Python):
import numpy
from bisect import bisect_left, bisect_right
from itertools import accumulate

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

ans=A[N-1]
for m in range(2,N-1):
  sum_left=A[m-1]
  i=bisect_left(A,sum_left/2)
  sum1=A[i]
  if i!=0:
    if A[i]+A[i-1]>sum_left:
      sum1=A[i-1]
  sum2=sum_left-sum1

  sum_right=A[N-1]-sum_left
  i=bisect_left(A,sum_left+sum_right/2)
  sum3=A[i]-sum_left
  if i!=m:
    if A[i]+A[i-1]-2*sum_left>sum_right:
      sum3=A[i-1]-sum_left
  sum4=sum_right-sum3
  max_sum=max(sum1,sum2,sum3,sum4)
  min_sum=min(sum1,sum2,sum3,sum4)
  dif=max_sum-min_sum
  if dif<ans:
    ans=dif

print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

from itertools import accumulate
accum = list(accumulate(a))

i_left = 0
i_right = 2
ans = 10**18
for i in range(1, n-2):
    while True:
        p = accum[i_left]
        q = accum[i] - p
        p_new = accum[i_left+1]
        q_new = accum[i] - p_new
        if abs(p_new - q_new) < abs(p - q):
            i_left += 1
        else:
            break
    while True:
        r = accum[i_right] - accum[i]
        s = accum[-1] - accum[i_right]
        r_new = accum[i_right+1] - accum[i]
        s_new = accum[-1] - accum[i_right+1]
        if abs(r_new - s_new) < abs(r - s):
            i_right += 1
        else:
            break

    
    diff = max([p, q, r, s]) - min([p, q, r, s])
    ans = min(ans, diff)

print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right
from itertools import accumulate

N = int(input())
A = list(map(int, input().split()))
A_sum = list(accumulate(A))

ans=A_sum[N-1]
for m in range(2,N-1):
  sum_left=A_sum[m-1]
  i=bisect_left(A_sum,sum_left/2)
  sum1=A_sum[i]
  if i!=0:
    if A_sum[i]+A_sum[i-1]>sum_left:
      sum1=A_sum[i-1]
  sum2=sum_left-sum1

  sum_right=A_sum[N-1]-sum_left
  i=bisect_left(A_sum,sum_left+sum_right/2)
  sum3=A_sum[i]-sum_left
  if i!=m:
    if A_sum[i]+A_sum[i-1]-2*sum_left>sum_right:
      sum3=A_sum[i-1]-sum_left
  sum4=sum_right-sum3
  max_sum=max(sum1,sum2,sum3,sum4)
  min_sum=min(sum1,sum2,sum3,sum4)
  dif=max_sum-min_sum
  if dif<ans:
    ans=dif

print(ans)

Solution (Python):
n=int(input())
a=[int(i) for i in input().split()]

s=[a[0]]
for i in range(n-1):
	s.append(s[i]+a[i+1])
ans=s[n-1]
j=0
k=2
for i in range(1,n-2):
	while abs(s[i]-2*s[j]) > abs(s[i]-2*s[j+1]):
		j=j+1
	while abs(s[n-1]-2*s[k]+s[i]) > abs(s[n-1]-2*s[k+1]+s[i]):
		k=k+1
	t=max(s[j],s[i]-s[j],s[k]-s[i],s[n-1]-s[k])-min(s[j],s[i]-s[j],s[k]-s[i],s[n-1]-s[k])
	if ans>t:
		ans=t
print(ans)

Solution (Python):
def solve(xs, n):
    for i in range(1, n):
        xs[i] += xs[i - 1]
    l, r = (0, 2)
    xs_last = xs[n - 1]
    ans = xs_last
    for c in range(1, n - 2):
        xs_center = xs[c]
        while l < c - 1:
            if xs_center < 2 * xs[l + 1]:
                if (xs[l + 1] + xs[l]) < xs_center:
                    l += 1
                break
            l += 1
        while r < n - 2:
            if xs_last + xs_center < 2 * xs[r + 1]:
                if (xs[r + 1] + xs[r]) < xs_last + xs_center:
                    r += 1
                break
            r += 1
        pqrs = (xs[l], xs_center - xs[l], xs[r] - xs_center, xs_last - xs[r])
        ans = min(ans, max(pqrs) - min(pqrs))
    return ans

if __name__ == "__main__":
    n = int(input())
    xs = [int(s) for s in input().split()]
    print(solve(xs, n))

Solution (Python):
from itertools import accumulate
from bisect import bisect_left, bisect_right

n = int(input())
a = list(map(int, input().split()))

ts = list(accumulate(a))+[0]
r = 0

def calc(st, ed):
    t0 = ts[ed-1] - ts[st-1]
    i1 = bisect_left(ts, (ts[ed-1]+ts[st-1])/2, st+1, ed-1)
    t11 = ts[i1-1] - ts[st-1]
    t12 = t0 - t11
    t21 = ts[i1] - ts[st-1]
    t22 = t0 - t21
    if abs(t22-t21) > abs(t12-t11):
        return t11, t12
    else:
        return t21, t22

ans = 10**18
for i in range(2, n-1):
    r1, r2 = calc(0, i)
    r3, r4 = calc(i, n)
    
    diff = max([r1, r2, r3, r4]) - min([r1, r2, r3, r4])
    ans = min(ans, diff)

print(ans)

Solution (Python):
N = int(input())
A = [int(_) for _ in input().split()]

from itertools import accumulate
from bisect import bisect_left, bisect_right

ts = list(accumulate(A)) + [0]

r = 0

def calc(st, ed):
    t0 = ts[ed-1] - ts[st-1]
    i1 = bisect_left(ts, (ts[ed-1] + ts[st-1]) / 2, st + 1, ed - 1)
    t11 = ts[i1-1] - ts[st-1]
    t12 = t0 - t11
    t21 = ts[i1] - ts[st-1]
    t22 = t0 - t21
    
    if abs(t22-t21) > abs(t12-t11):
        return t11, t12
    else:
        return t21, t22

result = 999999999999999999999999
for i in range(2, N-1):
    r1, r2 = calc(0, i)
    r3, r4 = calc(i, N)
    
    r = max(r1, r2, r3, r4) - min(r1, r2, r3, r4)
    result = min(result, r)

print(result)

Solution (Python):
from inspect import currentframe

def chkprint(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

from functools import reduce
from math import floor, ceil

N = int(input())
A = list(map(int, input().split()))

left = 1
center = 2
right = 3

res = 10**16



p = sum(A[0:left])
q = sum(A[left:center])
r = sum(A[center:right])
s = sum(A[right:])



while center <= N - 2:
  while True:
    if abs(p-q) < abs(p-q+2*A[left]):
      break

    if left == center-1:
      break

    p += A[left]
    q -= A[left]
    left += 1

  while True:
    if abs(r-s) < abs(r-s+2*A[right]):
      break

    if right == N-1:
      break

    r += A[right]
    s -= A[right]
    right += 1

  res = min(max(p,q,r,s)-min(p,q,r,s),res)

  
  q += A[center]
  r -= A[center]
  center += 1

print(res)