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

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

A=[0]+list(accumulate(A))
ans=A[N]
for j in range(2,N-1):
    S=A[j]-A[0]
    start=1
    end=j-1
    while end-start>1:
        t=(end+start)//2
        if S>=2*A[t]:
            start=t
        else:
            end=t
    i1=start
    i2=end

    T=A[N]-A[j]
    start=j+1
    end=N-1
    while end-start>1:
        t=(end+start)//2
        if T>=2*(A[t]-A[j]):
            start=t
        else:
            end=t

    k1=start
    k2=end

    data=[A[N]-A[k1],A[k1]-A[j],A[j]-A[i1],A[i1]-A[0]]
    test1=max(data)-min(data)

    data=[A[N]-A[k2],A[k2]-A[j],A[j]-A[i1],A[i1]-A[0]]
    test2=max(data)-min(data)

    data=[A[N]-A[k1],A[k1]-A[j],A[j]-A[i2],A[i2]-A[0]]
    test3=max(data)-min(data)

    data=[A[N]-A[k2],A[k2]-A[j],A[j]-A[i2],A[i2]-A[0]]
    test4=max(data)-min(data)

    ans=min(ans,test1,test2,test3,test4)

print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
score=[a[0],0,a[1]+a[2],sum(a[3:])]
ans=10**18
i,k=1,3
for j in range(2,n-1):
  score[1]+=a[j-1]
  score[2]-=a[j-1]
  while abs(score[0]-score[1])>abs(score[0]+a[i]-score[1]+a[i]):
    score[0]+=a[i]
    score[1]-=a[i]
    i+=1
  while abs(score[2]-score[3])>abs(score[2]+a[k]-score[3]+a[k]):
    score[2]+=a[k]
    score[3]-=a[k]
    k+=1
  ans=min(ans,max(score)-min(score))
print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
AA=[0]*(N)
AA[0]=A[0]
for i in range(1,N):
  AA[i]=AA[i-1]+A[i]
l=0
r=2
p=[]
for m in range(1,N-2):
  sl=AA[m]
  sr=AA[N-1]-sl
  while abs(sl-2*AA[l])>abs(sl-2*AA[l+1]):
    l+=1
  while abs(AA[N-1]+sl-2*AA[r])>abs(AA[N-1]+sl-2*AA[r+1]):
    r+=1
  P=AA[l]
  Q=sl-P
  R=AA[r]-sl
  S=sr-R
  ans=max(P,Q,R,S)-min(P,Q,R,S)
  p.append(ans)
print(min(p))

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    S = [0] * len(A)
    s = 0
    for i, a in enumerate(A):
        s += a
        S[i] = s 
    l = 0
    b = 2
    m = S[-1]
    for c in range(1, N - 2):
        p, q = S[l], S[c] - S[l]
        while l + 1 < c:
            pn, qn = S[l + 1], S[c] - S[l + 1]
            if abs(pn - qn) >= abs(p - q):
                break
            p, q = pn, qn
            l += 1
        if b <= c:
            b = c + 1
        r, s = S[b] - S[c], S[-1] - S[b]
        while b + 1 < N - 1:
            rn, sn = S[b + 1] - S[c], S[-1] - S[b + 1]
            if abs(rn - sn) >= abs(r - s):
                break
            r, s = rn, sn
            b += 1
        m = min(m, max(p, q, r, s) - min(p, q, r, s))
    return m


print(main())

Solution (Python):

def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        t = fn(m+1) - fn(m)
        if t == 0:
            return fn(m)
        if t < 0:
            l = m + 1
        else:
            r = m
    if fn(l) < fn(r):
        return l
    else:
        return r
def main():
    N = int(input())
    A = list(map(int, input().split()))
    Al = [A[0]]
    r = (10**9)*(2*(10**5))
    for i in A[1:]:
        Al.append(Al[-1] + i)
    for t in range(2, N-1):
        def fn1(i):
            return abs(Al[t-1] - Al[i-1] - Al[i-1])
        t1 = binsearch(1, t, fn1)
        def fn2(i):
            return abs(Al[-1] - Al[i-1] - Al[i-1] + Al[t-1])
        t2 = binsearch(t+1, N, fn2)
        x = Al[-1] - Al[t2-1]
        y = Al[t2-1] - Al[t-1]
        z = Al[t-1] - Al[t1-1]
        w = Al[t1-1]
        r = min(max(x,y,z,w) - min(x,y,z,w), r)
    return r
print(main())

Solution (Python):
import bisect
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
acc = list(accumulate(a))
ans = 10**18
for i in range(1,n-2):
  suml = acc[i]
  sumr = acc[n-1]-acc[i]
  ql = bisect.bisect_left(acc,suml/2)
  if ql == 0:
    ansl1 = [suml-acc[ql],acc[ql]]
    ansl2 = [suml-acc[ql],acc[ql]]
  else:
    ansl1 = [suml-acc[ql],acc[ql]]
    ansl2 = [suml-acc[ql-1],acc[ql-1]]
  qr = bisect.bisect_left(acc,sumr/2+suml)
  if qr == i:
    ansr1 = [acc[n-1]-acc[qr],acc[qr]-suml]
    ansr2 = [acc[n-1]-acc[qr],acc[qr]-suml]
  else:
    ansr1 = [acc[n-1]-acc[qr],acc[qr]-suml]
    ansr2 = [acc[n-1]-acc[qr-1],acc[qr-1]-suml]
  for ansl in (ansl1,ansl2):
    for ansr in (ansr1,ansr2):
      ans = min(ans,max(ansl+ansr)-min(ansl+ansr))
print(ans)

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

S = [0] * (N + 1)
for i in range(N):
    S[i + 1] = S[i] + A[i]

X = [0] * N
Y = [0] * N
x = 1
y = 3

for i in range(2, N - 1):
    L = S[i]
    R = S[N] - S[i]
    while abs(L - 2 * S[x + 1]) <= abs(L - 2 * S[x]):
        x += 1
    X[i] = x
    while abs(R - 2 * (S[y + 1] - L)) <= abs(R - 2 * (S[y] - L)):
        y += 1
    Y[i] = y

ans = S[N]
for i in range(2, N - 1):
    x = X[i]
    y = Y[i]
    B = S[x]
    C = S[i] - S[x]
    D = S[y] - S[i]
    E = S[N] - S[y]
    P = [B, C, D, E]
    ans = min(ans, max(P) - min(P))

print(ans)

Solution (Python):
N, *A = map(int, open(0).read().split())
B = [A[0]]
for i in range(1,N):
  B += [B[-1]+A[i]]
j = 1
a = A[0]
b = A[1]
c = A[2]
d = B[-1]-B[2]
j = 0
h = 2
while h<N:
  if abs(d-c)>abs(d-c-2*A[h+1]):
    h += 1
    c += A[h]
    d -= A[h]
    continue
  break
x = max(a,b,c,d)
y = min(a,b,c,d)
ans = x-y
for i in range(2,N-2):
  b += A[i]
  c -= A[i]
  while j<i:
    if abs(b-a)>abs(b-a-2*A[j+1]):
      j += 1
      a += A[j]
      b -= A[j]
      continue
    break
  while h<N:
    if abs(d-c)>abs(d-c-2*A[h+1]):
      h += 1
      c += A[h]
      d -= A[h]
      continue
    break
  x = max(a,b,c,d)
  y = min(a,b,c,d)
  ans = min(ans,x-y)
print(ans)

Solution (Python):
N = int(input())
A_list = [int(i) for i in input().split()]

Total_list = []
s = 0
for num in A_list:
  s += num
  Total_list.append(s)

L = 0
R = 2
ans = Total_list[N-1]+1
for Mid in range(1, N-2):
  sum_L = Total_list[Mid]
  sum_R = Total_list[N-1] - sum_L

  while abs(sum_L - 2*Total_list[L]) > abs(sum_L - 2*Total_list[L+1]):
    L += 1
  
  while abs((Total_list[N-1]-Total_list[R])-(Total_list[R] - sum_L)) > abs((Total_list[N-1]-Total_list[R+1])-(Total_list[R+1] - sum_L)):
    R += 1
  
  P = Total_list[L]
  Q = sum_L - Total_list[L]
  S = Total_list[R] - sum_L
  T = Total_list[N-1] - Total_list[R]

  ans = min(ans, max(P, Q, S, T) - min(P, Q, S, T))

print(ans)

Solution (Python):

N = int(input())
A = [int(i) for i in input().split()]
s = 0
AS = []
for i in range(N):
    s += A[i]
    AS.append(s)

Ans = AS[N-1]+1
L = 0
R = 2
for Mid in range(1, N-2):
    Sum_L = AS[Mid]
    Sum_R = AS[N-1]-Sum_L
    while abs((Sum_L - AS[L]) - AS[L]) > abs((Sum_L - AS[L+1]) - AS[L+1]):
        L += 1

    while abs((AS[N-1]-AS[R]) - (AS[R]-Sum_L)) > abs((AS[N-1]-AS[R+1]) - (AS[R+1]-Sum_L)):
        R += 1
    P = AS[L]
    Q = Sum_L-AS[L]
    S = AS[R]-Sum_L
    T = AS[N-1]-AS[R]
    
    Ans = min(Ans, abs(max(P, Q, S, T)-min(P, Q, S, T)))
print(Ans)

Solution (Python):




















    
























N = int(input())
A = list(map(int, input().split()))
s = 0
AS = []
for i in range(N):
    s += A[i]
    AS.append(s)

Ans = AS[N-1]+1
L = 0
R = 2
for Mid in range(1, N-2):
    Sum_L = AS[Mid]
    Sum_R = AS[N-1]-Sum_L
    while abs(Sum_L-2*AS[L]) > abs(Sum_L-2*AS[L+1]):
        L += 1

    while abs(AS[N-1]-2*AS[R]+AS[Mid]) > abs(AS[N-1]-2*AS[R+1]+AS[Mid]):
        R += 1
    P = AS[L]
    Q = AS[Mid]-AS[L]
    S = AS[R]-AS[Mid]
    T = AS[N-1]-AS[R]
    
    Ans = min(Ans, abs(max(P, Q, S, T)-min(P, Q, S, T)))
print(Ans)

Solution (Python):

N=int(input())
A=list(map(int,input().split()))
s=0
AS=[]
for i in range(N):
    s+=A[i]
    AS.append(s)

Ans=AS[N-1]+1
L=0
R=2
for Mid in range(1,N-2):
    Sum_L=AS[Mid]
    Sum_R=AS[N-1]-Sum_L
    while abs(Sum_L-2*AS[L])>abs(Sum_L-2*AS[L+1]):
        L+=1
    
    while R<=N-3 and abs(AS[N-1]-2*AS[R]+AS[Mid])>abs(AS[N-1]-2*AS[R+1]+AS[Mid]):
        R+=1
    P=AS[L]
    Q=AS[Mid]-AS[L]
    S=AS[R]-AS[Mid]
    T=AS[N-1]-AS[R]
    
    Ans=min(Ans,abs(max(P,Q,S,T)-min(P,Q,S,T)))
print(Ans)

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

A2 = [0] * (N + 1)

for i in range(1, N + 1):
    A2[i] = A2[i - 1] + A[i - 1]


def find(_l, _r):
    l, r = _l, _r
    lv, rv = A2[l - 1], A2[r]
    while l < r - 1:
        m = (r + l) // 2
        a = A2[m] - lv
        if a <= (rv - lv) / 2:
            l = m
        else:
            r = m
    if l < _r:
        if abs((A2[l] - lv) - (rv - A2[l])) > abs((A2[l + 1] - lv) - (rv - A2[l + 1])):
            return A2[l + 1] - lv, rv - A2[l + 1]
    return A2[l] - lv, rv - A2[l]


ans = 1e10
for i in range(2, N - 1):
    p, q = find(1, i)
    r, s = find(i + 1, N)
    
    ans = min(ans, abs(max(p, q, r, s) - min(p, q, r, s)))
print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
S=[0]*(N+1)

for i in range(N):
    S[i+1]=S[i]+A[i]
    
ans=10**20

sp=S[1]
sq=0
sr=S[3]-S[1]
ss=S[-1]-S[3]

th_pq=1
th_rs=3

for i in range(2,N-1):
    sq+=A[i-1]
    sr-=A[i-1]
    while th_pq!=i-1:
        diff_pq=abs(sp-sq)
        sp2=sp+A[th_pq]
        sq2=sq-A[th_pq]
        diff_pq2=abs(sp2-sq2)
        if diff_pq2 <= diff_pq:
            sp=sp2
            sq=sq2
            th_pq+=1
        else:
            break
        
    while th_rs!=N-1:
        diff_rs=abs(sr-ss)
        sr2=sr+A[th_rs]
        ss2=ss-A[th_rs]
        diff_rs2=abs(sr2-ss2)
        if diff_rs2 <= diff_rs:
            sr=sr2
            ss=ss2
            th_rs+=1
        else:
            break
    temp=max(sp,sr,sq,ss) - min(sp,sq,sr,ss)
    ans=min(ans,temp)
    
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from itertools import accumulate
from bisect import bisect_left

INF = 10 ** 18
MOD = 10 ** 9 + 7

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

Acum = [0] + list(accumulate(A))
answer = INF

for i in range(2, N - 1):
  bpq = bisect_left(Acum,  (Acum[i] - Acum[0]) // 2)
  brs = bisect_left(Acum,  (Acum[N] - Acum[i]) // 2 + Acum[i])
  
  P1, Q1 = Acum[bpq] - Acum[0], Acum[i] - Acum[bpq]
  P2, Q2 = Acum[bpq - 1] - Acum[0], Acum[i] - Acum[bpq - 1]
  R1, S1 = Acum[brs] - Acum[i], Acum[N] - Acum[brs]
  R2, S2 = Acum[brs - 1] - Acum[i], Acum[N] - Acum[brs - 1]  
  
  tmp = INF
  tmp = min(tmp, max(P1, Q1, R1, S1) - min(P1, Q1, R1, S1))
  tmp = min(tmp, max(P1, Q1, R2, S2) - min(P1, Q1, R2, S2))
  tmp = min(tmp, max(P2, Q2, R1, S1) - min(P2, Q2, R1, S1))
  tmp = min(tmp, max(P2, Q2, R2, S2) - min(P2, Q2, R2, S2))
  
  answer = min(answer, tmp)
  
print(answer)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from itertools import accumulate
from bisect import bisect_left

INF = 10 ** 18
MOD = 10 ** 9 + 7

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

Acum = [0] + list(accumulate(A))
answer = INF

for i in range(2, N - 1):
  bpq = bisect_left(Acum,  (Acum[i] - Acum[0]) // 2)
  brs = bisect_left(Acum,  (Acum[N] - Acum[i]) // 2 + Acum[i])
  
  P1, Q1 = Acum[bpq] - Acum[0], Acum[i] - Acum[bpq]
  P2, Q2 = Acum[bpq - 1] - Acum[0], Acum[i] - Acum[bpq - 1]
  R1, S1 = Acum[brs] - Acum[i], Acum[N] - Acum[brs]
  R2, S2 = Acum[brs - 1] - Acum[i], Acum[N] - Acum[brs - 1]  
  
  tmp = INF
  tmp = min(tmp, max(P1, Q1, R1, S1) - min(P1, Q1, R1, S1))
  tmp = min(tmp, max(P1, Q1, R2, S2) - min(P1, Q1, R2, S2))
  tmp = min(tmp, max(P2, Q2, R1, S1) - min(P2, Q2, R1, S1))
  tmp = min(tmp, max(P2, Q2, R2, S2) - min(P2, Q2, R2, S2))
  
  answer = min(answer, tmp)
  
print(answer)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from itertools import accumulate
from bisect import bisect_left

INF = 10 ** 18

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

Acum = [0] + list(accumulate(A))
answer = INF

for i in range(2, N - 1):
  bpq = bisect_left(Acum,  (Acum[i] - Acum[0]) // 2)
  brs = bisect_left(Acum,  (Acum[N] - Acum[i]) // 2 + Acum[i])
  
  P1, Q1 = Acum[bpq] - Acum[0], Acum[i] - Acum[bpq]
  P2, Q2 = Acum[bpq - 1] - Acum[0], Acum[i] - Acum[bpq - 1]
  R1, S1 = Acum[brs] - Acum[i], Acum[N] - Acum[brs]
  R2, S2 = Acum[brs - 1] - Acum[i], Acum[N] - Acum[brs - 1]  
  
  tmp = []
  tmp.append(max(P1, Q1, R1, S1) - min(P1, Q1, R1, S1))
  tmp.append(max(P1, Q1, R2, S2) - min(P1, Q1, R2, S2))
  tmp.append(max(P2, Q2, R1, S1) - min(P2, Q2, R1, S1))
  tmp.append(max(P2, Q2, R2, S2) - min(P2, Q2, R2, S2))
  
  answer = min(answer, min(tmp))
  
print(answer)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    N = I()
    A = LI()
    cumsum = [0 for _ in range(N+1)]

    for i in range(N):
        cumsum[i+1] = cumsum[i] + A[i]

    def get_cumsum(a, b):
        
        return cumsum[b+1] - cumsum[a]

    def separate_opt_sum(l, r, offset):
        tot_sum = get_cumsum(l, r)
        targ = offset + tot_sum / 2
        left_i = bisect.bisect_left(cumsum, targ)

        diff1 = inf
        diff2 = inf
        diff3 = inf
        left_sum1, right_sum1, left_sum2, right_sum2 = inf, inf, inf, inf
        left_sum3, right_sum3 = inf, inf

        if l <= left_i - 2:
            left_sum3 = get_cumsum(l, left_i - 2)
            right_sum3 = tot_sum - left_sum3
            diff3 = abs(right_sum3 - left_sum3)

        if l <= left_i - 1:
            left_sum1 = get_cumsum(l, left_i - 1)
            right_sum1 = tot_sum - left_sum1
            diff1 = abs(right_sum1 - left_sum1)

        if left_i < r:
            left_sum2 = get_cumsum(l, left_i)
            right_sum2 = tot_sum - left_sum2
            diff2 = abs(right_sum2 - left_sum2)

        if min(diff1, diff2, diff3) == diff1:
            return left_sum1, right_sum1
        elif min(diff1, diff2, diff3) == diff2:
            return left_sum2, right_sum2
        return left_sum3, right_sum3

    def _separate_opt_sum(l, r):
        
        
        tot_sum = get_cumsum(l, r)
        m = (l + r) // 2
        m_min = l - 1
        m_max = r + 1
        cur_min_diff = abs(2 * get_cumsum(l, m) - tot_sum)
        cur_min_m = m
        while m_min < m and m < m_max:
            left_sum = get_cumsum(l, m)
            right_sum = tot_sum - left_sum
            cur_diff = abs(left_sum - right_sum)
            if cur_diff < cur_min_diff:
                cur_min_diff = cur_diff
                cur_min_m = m
            if left_sum < right_sum:
                m_min = m
                m = (m + r) // 2
            elif left_sum > right_sum:
                m_max = m
                m = (l + m) // 2
            else:
                break
        l_ans = get_cumsum(l, cur_min_m)
        r_ans = get_cumsum(cur_min_m + 1, r)
        return l_ans, r_ans

    ans = inf
    for sep in range(1, N-2):
        left_S = get_cumsum(0, sep)
        right_S = get_cumsum(sep+1, N-1)
        
        
        p, q = separate_opt_sum(0, sep, 0)
        r, s = separate_opt_sum(sep+1, N-1, left_S)
        
        
        
        ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
    print(ans)
main()

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    A=LI()
    *cumsum, = accumulate(A)
    l = 0
    r = 1
    ans = inf
    def calc_abs_left(mid,l):
        a,b = cumsum[l], cumsum[mid]-cumsum[l]
        return abs(a-b)
    def calc_abs_right(mid,r):
        a,b = cumsum[r]-cumsum[mid], cumsum[-1]-cumsum[r]
        return abs(a-b)
    for mid in range(1,N-1):
        while calc_abs_left(mid, l) > calc_abs_left(mid, l+1) and l<mid:
            l += 1
        while calc_abs_right(mid, r) > calc_abs_right(mid, r+1) and r<N-1:
            r += 1
        B = [cumsum[l], cumsum[mid]-cumsum[l], cumsum[r]-cumsum[mid], cumsum[-1]-cumsum[r]]
        ans = min(ans, max(B)-min(B))
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):


from itertools import accumulate

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

acc = list(accumulate(a))

l = 0
r = 2

ans = float('inf')

for y in range(1,n-2):
    for x in range(l,y-1):
        if abs(acc[y]-acc[x]*2)>=abs(acc[y]-acc[x+1]*2):
            l = x+1
            continue
        else:
            break
    r = max(y+1,r)
    for z in range(r,n-2):
        if abs(acc[n-1]-acc[z]*2+acc[y])>=abs(acc[n-1]-acc[z+1]*2+acc[y]):
            r = z+1
            continue
        else:
            break
    P = acc[l]
    Q = acc[y] - acc[l]
    R = acc[r] - acc[y]
    S = acc[n-1] - acc[r]
    ans = min(ans, max(P,Q,R,S)-min(P,Q,R,S))

print(ans)

Solution (Python):
from itertools import accumulate
import bisect


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

arev = list(reversed(a))

front = list(accumulate(a))
back = list(accumulate(arev))

ans = float('inf')
for i in range(1,n-2):
    b = bisect.bisect_left(front,front[i]//2,0,i-1)
    c = bisect.bisect_left(back,back[n-i-2]//2,0,n-i-3)

    p = front[b]
    q = front[i]-front[b]
    s = back[c]
    r = back[n-i-2]-back[c]
    ans = min(max(p,q,r,s)-min(p,q,r,s),ans)

    if b!=0:
        p = front[b-1]
        q = front[i] - front[b-1]
        s = back[c]
        r = back[n-i-2] - back[c]
        ans = min(max(p, q, r, s) - min(p, q, r, s), ans)
    if c!=0:
        p = front[b]
        q = front[i] - front[b]
        s = back[c-1]
        r = back[n-i-2] - back[c-1]
        ans = min(max(p, q, r, s) - min(p, q, r, s), ans)
    if b!=0 and c!=0:
        p = front[b-1]
        q = front[i] - front[b-1]
        s = back[c-1]
        r = back[n-i-2] - back[c-1]
        ans = min(max(p, q, r, s) - min(p, q, r, s), ans)

print(ans)

Solution (Python):
from itertools import accumulate

def binary_search(a, left, right, base):
    l,r = left, right
    while l + 1 < r:
        mid = (l+r)//2
        
        if acc[right] - base < (acc[mid] - base) * 2:
            r = mid
        else:
            l = mid
    if abs(acc[right] - base - (acc[r] - base) * 2) < abs(acc[right] - base - (acc[l] - base) * 2):
        return r
    else:
        return l

n = int(input())
a = [0] + list(map(int, input().split()))
acc = list(accumulate(a))
ans = float('INF')
for i in range(2,n-1):
    
    s = binary_search(a, 1,i, 0)
    t = binary_search(a, i+1,n, acc[i])
    o,p,q,r = acc[s], acc[i]-acc[s], acc[-1]-acc[t], acc[t] - acc[i]
    
    if max(q,p,r,o) - min(p,q,r,o) < ans:
        ans = max(p,q,r,o) - min(p,q,r,o)
print(ans)

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

ans = float('inf')
iB, iD = 1, 3
(P, Q, R), S = As[:3], sum(As[3:])


for iC in range(2, N - 1):
    while P < Q and As[iB] <= Q - P:
        P += As[iB]
        Q -= As[iB]
        iB += 1

    while R < S and As[iD] <= S - R:
        R += As[iD]
        S -= As[iD]
        iD += 1

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

    Q += As[iC]
    R -= As[iC]

print(ans)

Solution (Python):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

cum = np.array(A, dtype=int).cumsum().tolist()

left_i = [None] * N
right_i = [None] * N
l = 1
r = 3
ans = INF

for i in range(2, N - 1):
    while l + 1 < i and abs(cum[l - 1] * 2 - cum[i - 1]) > abs(cum[l] * 2 - cum[i - 1]):
        l += 1
    while r + 1 < N and abs(cum[r - 1] * 2 - cum[i - 1] - cum[N - 1]) > abs(cum[r] * 2 - cum[i - 1] - cum[N - 1]):
        r += 1

    s1 = cum[l - 1]
    s2 = cum[i - 1] - s1
    s3 = cum[r - 1] - s2 - s1
    s4 = cum[N - 1] - s3 - s2 - s1
    ans = min(ans, max(s1, s2, s3, s4) - min(s1, s2, s3, s4))
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
s = 0
S = [0]*N
for i, a in enumerate(A):
    s += a
    S[i] = s

t = S[-1]
ans = 10**20
j = 0
k = 2
for i in range(1,N-2):
    s = S[i]
    while abs(s-2*S[j+1]  ) < abs(s-2*S[j]  ): j+=1
    while abs(t-2*S[k+1]+s) < abs(t-2*S[k]+s): k+=1
    
    v = (S[j], s-S[j], S[k]-s, t-S[k])
    ans = min(ans, max(v)-min(v))
    
    
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
B = [0]
tmp = 0
for a in A:
    tmp += a
    B.append(tmp)

l = 1
r = 3
cut = []
for i in range(2,N-1):
    Lm = float("inf")
    Rm = float("inf")
    c = [0,i,0]
    for j in range(l,i):
        tmp = abs(B[i]-2*B[j])
        if tmp > Lm:
            c[0] = j-1
            l = j-1
            break
        Lm = tmp
    else:
        c[0] = i-1
        l = i-1
    for k in range(r,N):
        tmp = abs((B[N]-B[k])-(B[k]-B[i]))
        if tmp > Rm:
            c[2] = k-1
            r = k-1
            break
        Rm = tmp
    else:
        c[2] = N-1
        r = N
    cut.append(c)

ans = float("inf")
for p,q,r in cut:
    P = B[p]
    Q = B[q]-B[p]
    R = B[r]-B[q]
    S = B[N]-B[r]
    ans = min(ans,max(P,Q,R,S)-min(P,Q,R,S))
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
B = [0]
tmp = 0
for a in A:
    tmp += a
    B.append(tmp)

l = 1
r = 3
cut = []
for i in range(2,N-1):
    Lm = float("inf")
    Rm = float("inf")
    c = [0,i,0]
    for j in range(l,i):
        tmp = abs(B[i]-2*B[j])
        if tmp > Lm:
            c[0] = j-1
            l = j-1
            break
        Lm = tmp
    else:
        c[0] = i-1
        l = i-1
    for k in range(r,N):
        tmp = abs((B[N]-B[k])-(B[k]-B[i]))
        if tmp > Rm:
            c[2] = k-1
            r = k-1
            break
        Rm = tmp
    else:
        c[2] = N-1
        r = N
    cut.append(c)

ans = float("inf")
for p,q,r in cut:
    P = B[p]
    Q = B[q]-B[p]
    R = B[r]-B[q]
    S = B[N]-B[r]
    ans = min(ans,max(P,Q,R,S)-min(P,Q,R,S))
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import *

N = int(input())
A = list(map(int, input().split()))
acc = [0]

for Ai in A:
    acc.append(acc[-1]+Ai)

ans = 10**18
P_idx = 0
R_idx = 2

for i in range(1, N-2):
    PQ = acc[i+1]
    
    while abs(PQ-2*acc[P_idx+1])<abs(PQ-2*acc[P_idx]):
        P_idx += 1
    
    P = acc[P_idx]
    Q = PQ-P
    
    RS = acc[-1]-PQ
    
    while abs(RS-2*(acc[R_idx+1]-acc[i+1]))<abs(RS-2*(acc[R_idx]-acc[i+1])):
        R_idx += 1
        
    R = acc[R_idx]-acc[i+1]
    S = RS-R
    
    ans = min(ans, max(P, Q, R, S)-min(P, Q, R, S))

print(ans)

Solution (Python):
import sys
from itertools import accumulate

n, *a = map(int, sys.stdin.read().split())

def main():
    ans = float('inf')
    left = 0; right = 2
    p = a[0]; q = 0; r = sum(a[1:3]); s = sum(a[3:])
    for c in range(1, n-2):
        q += a[c]; r -= a[c]
        while left < c - 1:
            nex = a[left+1]
            if abs((q - nex) - (p + nex)) <= abs(q - p):
                q -= nex; p += nex
                left += 1
            else:
                break  
        
        while right < n - 2:
            nex = a[right+1]
            if abs((s - nex) - (r + nex)) <= abs(s - r):
                s -= nex; r += nex
                right += 1
            else:
                break

        res = sorted([p, q, r, s])
        ans = min(ans, res[-1] - res[0])

    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys
from itertools import accumulate
from bisect import bisect_left as bi_l

n, *a = map(int, sys.stdin.read().split())

def main():
    s = list(accumulate(a))

    ans = float('inf')
    for center in range(1, n-2):
        pq = s[center]
        left = bi_l(s, pq / 2)
        if left == 0:
            p = s[0]
        else:
            if pq - s[left] < s[left-1]:
                left -= 1
            p = s[left]
        q = pq - p

        rt = s[-1] - pq
        right = bi_l(s, pq + rt / 2)
        if right == center + 1:
            r = s[center+1] - pq
        else:
            if rt - (s[right] - pq) < s[right-1] - pq:
                right -= 1
            r = s[right] - pq
        t = rt - r

        res = sorted([p, q, r, t])
        ans = min(ans, res[-1] - res[0])

    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    def nibutan1(ok,ng,index):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve1(mid,index):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve1(mid,index):
        P=S[mid]
        Q=S[index]-S[mid]
        return P<Q

    def nibutan2(ok,ng,index):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve2(mid,index):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve2(mid,index):
        P=S[mid]-S[index]
        Q=S[N-1]-S[mid]
        return P<Q
    
    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=INF
    for i in range(1,N-1):
        c1=nibutan1(0,i-1,i)
        c2=nibutan2(i,N-2,i)
        if abs(S[c1]-(S[i]-S[c1]))<abs(S[c1+1]-(S[i]-S[c1+1])):
            p,q=S[c1],S[i]-S[c1]
        else:
            p,q=S[c1+1],S[i]-S[c1+1]
        if abs(S[c2]-S[i]-(S[N-1]-S[c2]))<abs(S[c2+1]-S[i]-(S[N-1]-S[c2+1])):
            r,s=S[c2]-S[i],S[N-1]-S[c2]
        else:
            r,s=S[c2+1]-S[i],S[N-1]-S[c2+1]
        ans=min(ans,max(p,q,r,s)-min(p,q,r,s))
    print(ans)
        
        
    
if __name__ == '__main__':
    main()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

l = 1
m = 2
r = 3
a = sum(A[:l])
b = sum(A[l:m])
c = sum(A[m:r])
d = sum(A[r:])
ans = max(a, b, c, d) - min(a, b, c, d)

while m < N-1:
    
    while l < m-1 and abs(a - b) > abs(a+A[l] - (b-A[l])):
        a += A[l]
        b -= A[l]
        l += 1
    
    while r < N-1 and abs(c - d) > abs(c+A[r] - (d-A[r])):
        c += A[r]
        d -= A[r]
        r += 1
    ans = min(ans, max(a, b, c, d) - min(a, b, c, d))
    
    b += A[m]
    c -= A[m]
    m += 1
    
    if m == r:
        c += A[r]
        d -= A[r]
        r += 1
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a_cs = [0] * (n + 1)
for i in range(n):
    a_cs[i + 1] = a_cs[i] + a[i]

i1 = 1
i3 = 3
ans = 10**14
for i2 in range(2, n - 1):
    while i1 + 1 < i2 and abs(a_cs[i1] * 2 - a_cs[i2]) > abs(a_cs[i1 + 1] * 2 -
                                                             a_cs[i2]):
        i1 += 1

    while i3 + 1 < n and abs(a_cs[-1] + a_cs[i2] - a_cs[i3] *
                             2) > abs(a_cs[-1] + a_cs[i2] - a_cs[i3 + 1] * 2):
        i3 += 1

    p = a_cs[i1]  
    q = a_cs[i2] - a_cs[i1]  
    r = a_cs[i3] - a_cs[i2]  
    s = a_cs[n] - a_cs[i3]  
    cand = max(p, q, r, s) - min(p, q, r, s)
    ans = min(ans, cand)

print(ans)

Solution (Python):
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
cs = [0] * N
cs[0] = a[0]
for i in range(N - 1): cs[i + 1] = cs[i] + a[i + 1]
res = float("inf")
for m in range(1, N - 1):
  l = bl(cs, cs[m] // 2, hi = m)
  r = bl(cs, cs[m] + (cs[-1] - cs[m]) // 2, lo = m)
  l -= l == m
  r += r == m
  nl = l + 0
  nr = r + 0
  for i in range(3):
    if i == 1: continue
    if 0 <= l + i - 1 < m:
      if abs(cs[m] - 2 * cs[l + i - 1]) < abs(cs[m] - 2 * cs[l]):
        nl = l + i - 1
    if m < r + i - 1 < N:
      if abs(cs[-1] - 2 * cs[r + i - 1] + cs[m]) < abs(cs[-1] - 2 * cs[r] + cs[m]):
        nr = r + i - 1
  l = nl
  r = nr
  res = min(res, max(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]) - min(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]))
print(res)