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


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


n = int(input())
a = list(map(int, input().split()))
ca = [None] * n 
s = 0
for i,num in enumerate(a):
    s += a[i]
    ca[i] = s

diff = [None] * n

s = 0
t = 1
v1 = 0 
v2 = a[0] 
diff[t-1] = (v1,v2)
while t<n:

    t += 1
    v2 += a[t-1]
    while v1<v2 and s<t:
        if diff[t-1] is None or abs(v1-v2)<abs(diff[t-1][0] - diff[t-1][1]):
            diff[t-1] = (v1,v2)
        s += 1
        v1 += a[s-1]
        v2 -= a[s-1]
    if diff[t-1] is None or abs(v1-v2)<abs(diff[t-1][0] - diff[t-1][1]):
        diff[t-1] = (v1,v2)        
    if v1>v2 and s>=1:
        v1 -= a[s-1]
        v2 += a[s-1]
        s -= 1

diff2 = [None] * n

s = n
t = n-1
v1 = 0 
v2 = a[-1] 
diff2[t] = (v1,v2)
while t>=1:
    
    t -= 1
    v2 += a[t]
    while v1<v2 and s>t:
        if diff2[t] is None or abs(v1-v2)<abs(diff2[t][0] - diff2[t][1]):
            diff2[t] = (v1,v2)
        s -= 1
        v1 += a[s]
        v2 -= a[s]
    if diff2[t] is None or abs(v1-v2)<abs(diff2[t][0] - diff2[t][1]):
        diff2[t] = (v1,v2)        
    if v1>v2 and s<=n-2:
        v1 -= a[s]
        v2 += a[s]
        s += 1
print(min((max(diff[i][0], diff[i][1],diff2[i+1][0],diff2[i+1][1]) - min(diff[i][0], diff[i][1],diff2[i+1][0],diff2[i+1][1])) for i in range(n-1)))

Solution (Python):


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))



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

ca = [None] * n 
s = 0
for i,num in enumerate(a):
    s += a[i]
    ca[i] = s


def sub(l, start, end, init):
    if len(l)==0:
        return 0,0
    elif end-start==1:
        return 0,l[start]-init
    target = (init + l[end-1])/2
    i = bisect.bisect_right(l, target)
    p1 = (l[i]-init, l[end-1]-l[i])
    p2 = (l[i-1]-init, l[end-1]-l[i-1])
    if abs(p1[0] - p1[1]) < abs(p2[0] - p2[1]):
        return min(p1), max(p1)
    else:
        return min(p2), max(p2)
best = 10**15
for i in range(1,n):
    p1 = sub(ca, 0, i, 0)
    p2 = sub(ca, i, n, ca[i-1])
    nn = max(p1[1]-p2[0], p2[1]-p1[0], p1[1]-p1[0], p2[1]-p2[0])

    best = min(best, nn)
print(best)

Solution (Python):


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))



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

ca = [None] * n 
s = 0
for i,num in enumerate(a):
    s += a[i]
    ca[i] = s


def sub(l, start, end, init):
    if len(l)==0:
        return 0,0
    elif end-start==1:
        return 0,l[start]-init
    target = (init + l[end-1])/2
    i = bisect.bisect_right(l, target)
    p1 = (l[i]-init, l[end-1]-l[i])
    p2 = (l[i-1]-init, l[end-1]-l[i-1])
    if abs(p1[0] - p1[1]) < abs(p2[0] - p2[1]):
        return min(p1), max(p1)
    else:
        return min(p2), max(p2)
best = 10**15
for i in range(1,n):
    p1 = sub(ca, 0, i, 0)
    p2 = sub(ca, i, n, ca[i-1])
    nn = max(p1[1]-p2[0], p2[1]-p1[0], p1[1]-p1[0], p2[1]-p2[0])

    best = min(best, nn)
print(best)

Solution (Python):
n=int(input())
l=[0]+list(map(int,input().split()))
from itertools import accumulate
l=list(accumulate(l))
from bisect import bisect, bisect_left, bisect_right
ans=10**15
for i in range(2,n-1):
    x=bisect_left(l,l[i]//2)
    p1=l[x]
    p2=l[x-1]
    if abs(l[i]-p1*2)>=abs(l[i]-p2*2):
        p=p2
    else:
        p=p1
    q=l[i]-p
    x=bisect_left(l,(l[n]-l[i])//2+l[i])
    r1=l[x]-l[i]
    r2=l[x-1]-l[i]
    if abs(l[n]-l[i]-r1*2)>=abs(l[n]-l[i]-r2*2):
        r=r2
    else:
        r=r1
    s=l[n]-l[i]-r
    ans=min(ans,max(p,q,r,s)-min(p,q,r,s))
print(ans)

Solution (Python):
import bisect
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
A = list(accumulate(A))
s = A[-1]
ans = float("inf")
for i in range(1, n-2):
  left = bisect.bisect(A, A[i]//2)
  right = bisect.bisect(A, (A[i]+s)//2)
  lm = float("inf")
  lM = 0
  rm = float("inf")
  rM = 0
  ld = float("inf")
  rd = float("inf")
  for j in range(-1, 2):
    if 0 <= left+j < i:
      a = A[left+j]
      b = A[i] - a
      if ld > abs(b-a):
        ld = abs(b-a)
        lm = min(a, b)
        lM = max(a, b)
    if i <= right+j < n-1:
      a = A[right+j] - A[i]
      b = s - A[right+j]
      if rd > abs(b-a):
        rd = abs(b-a)
        rm = min(a, b)
        rM = max(a, b)
  ans = min(ans, max(lM, rM) - min(lm, rm))
print(ans)

Solution (Python):
from itertools import accumulate
import bisect

n = int(input())
a = list(map(int, input().split()))
sum_a = sum(a)
cumsum = [0]+list(accumulate(a))
ans = 10 ** 18
for d in range(2,n-1):
  f_sum = cumsum[d]
  l_sum = cumsum[n]-cumsum[d]
  c = bisect.bisect_right(cumsum, f_sum//2)
  e = bisect.bisect_right(cumsum, f_sum+l_sum//2)
  for i in [c,c+1]:
    p = cumsum[i-1]
    q = f_sum - p
    if p and q:
      for j in [e,e+1]:
        r = cumsum[j-1] - f_sum
        s = l_sum - r
        if r and s:
          sums = [p,q,r,s]
          ans = min(ans,max(sums)-min(sums))
print(ans)

Solution (Python):

import sys
from itertools import accumulate

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
Acum = list(accumulate(A))
l_cut = [None] * N  
l_cut[1] = 0
l = A[0]; r = A[1]
for i in range(2, N):
    r += A[i]
    diff = abs(r-l)
    index = l_cut[i-1]
    while index < i - 1:
        temp = abs(l + A[index+1] - (r - A[index+1]))
        if temp < diff:
            index += 1
            l += A[index]
            r -= A[index]
            diff = temp
        else:
            break
    l_cut[i] = index

r_cut = [None] * N
r_cut[-2] = N-2
l = A[-2]; r = A[-1]
for i in range(N-3, 0, -1):
    l += A[i]
    diff = abs(r-l)
    index = r_cut[i+1]
    while index > i:
        temp = abs(r + A[index] - (l - A[index]))
        if temp < diff:
            index -= 1
            r += A[index+1]
            l -= A[index+1]
            diff = temp
        else:
            break
    r_cut[i] = index

answer = 10 ** 17
for i in range(1, N-2):
    a = Acum[l_cut[i]]
    b = Acum[i] - a
    c = Acum[r_cut[i+1]] - Acum[i]
    d = Acum[-1] - (a + b + c)
    temp = max(a, b, c, d) - min(a, b, c, d)
    if temp < answer:
        answer = temp

print(answer)

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

b = [0]
for i in a:
    b.append(b[-1] + i)


def get(i, j):
    i, j = min(i, j), max(i, j)
    return b[j]-b[i]


j = 0
k = 0
ans = 10**18
for i in range(n):
    while j < n and abs(get(0, j) - get(j, i)) > abs(get(0, j + 1) - get(j + 1, i)):
        j += 1
    while k < n and abs(get(i, k) - get(k, n)) > abs(get(i, k + 1) - get(k + 1, n)):
        k += 1
    an = [get(0, j), get(j, i), get(i, k), get(k, n)]
    ans = min(ans,max(an)-min(an))
print(ans)

Solution (Python):
n=int(input())
s=list(map(int,input().split()))
a=[0]
c=0
for si in s:
    c+=si
    a.append(c)
ans=[]
f=1
g=3
for i in range(2,n-1):
    while abs(a[f]-(a[i]-a[f])) > abs(a[f+1]-(a[i]-a[f+1])):
        f+=1
    while abs(a[g]-a[i]-(a[n]-a[g])) > abs(a[g+1]-a[i]-(a[n]-a[g+1])):
        g+=1
    ls=[a[f],a[i]-a[f],a[g]-a[i],a[n]-a[g]]
    ans.append(max(ls)-min(ls))
print(min(ans))

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

from bisect import bisect
cums=[0]
for a in A:
    cums.append(cums[-1]+a)

lmn=[]
lmx=[]
for i in range(2,n-1):
    j=bisect(cums,cums[i]//2)
    a1,b1=cums[j],cums[i]-cums[j]
    a2,b2=cums[j-1],cums[i]-cums[j-1]
    if abs(a1-b1)<abs(a2-b2):
        lmn.append(min(a1,b1))
        lmx.append(max(a1,b1))
    else:
        lmn.append(min(a2,b2))
        lmx.append(max(a2,b2))
A.reverse()
cums=[0]
for a in A:
    cums.append(cums[-1]+a)

rmn=[]
rmx=[]
for i in range(2,n-1):
    j=bisect(cums,cums[i]//2)
    a1,b1=cums[j],cums[i]-cums[j]
    a2,b2=cums[j-1],cums[i]-cums[j-1]
    if abs(a1-b1)<abs(a2-b2):
        rmn.append(min(a1,b1))
        rmx.append(max(a1,b1))
    else:
        rmn.append(min(a2,b2))
        rmx.append(max(a2,b2))
rmn.reverse()
rmx.reverse()
ans=float('inf')
for ln,lx,rn,rx in zip(lmn,lmx,rmn,rmx):
    d=max(lx,rx)-min(ln,rn)
    ans=min(ans,d)
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]
s=s[1:]
l=1
ans=float("inf")
r=3
for i in range(2,n-1):
    while i-l>1 and abs(s[i-1]-s[l-1]-s[l-1])>abs(s[i-1]-s[l]-s[l]):
        l+=1
    while abs(s[n-1]-s[r-1]-(s[r-1]-s[i-1]))>abs(s[n-1]-s[r]-(s[r]-s[i-1])):
        r+=1
    ansl=[s[l-1],s[i-1]-s[l-1],s[r-1]-s[i-1],s[n-1]-s[r-1]]
    ans=min(ans,max(ansl)-min(ansl))
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]
s=s[1:]
l=1
ans=float("inf")
r=3
for i in range(2,n-1):
    while i-l>1 and abs(s[i-1]-s[l-1]-s[l-1])>abs(s[i-1]-s[l]-s[l]):
        l+=1
    while abs(s[n-1]-s[r-1]-(s[r-1]-s[i-1]))>abs(s[n-1]-s[r]-(s[r]-s[i-1])):
        r+=1
    ansl=[s[l-1],s[i-1]-s[l-1],s[r-1]-s[i-1],s[n-1]-s[r-1]]
    ans=min(ans,max(ansl)-min(ansl))
print(ans)

Solution (Python):
from collections import deque
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    aa=LI()
    p=aa[0]
    q=aa[1]
    j=1
    dl=abs(p-q)
    k=3
    r=aa[2]
    s=sum(aa[3:])
    dr=abs(r-s)
    while abs(r-s+aa[k]*2)<dr:
        r+=aa[k]
        s-=aa[k]
        dr=abs(r-s)
        k+=1
    ans=max(p,q,r,s)-min(p,q,r,s)
    for i in range(3,n-1):
        q += aa[i - 1]
        dl = abs(p - q)
        while abs(p - q + aa[j] * 2) < dl:
            p += aa[j]
            q -= aa[j]
            dl = abs(p - q)
            j += 1

        r -= aa[i - 1]
        dr = abs(r - s)
        while abs(r-s+aa[k]*2)<dr:
            r+=aa[k]
            s-=aa[k]
            dr=abs(r-s)
            k+=1
        cur=max(p,q,r,s)-min(p,q,r,s)
        if cur<ans:ans=cur
    print(ans)

main()

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

N = int(input())
A = list(map(int, input().split()))
cum = list(accumulate(A))
ans = float('inf')
for i in range(1, N-2):
    lb, ub = 0, i + 1
    while ub - lb > 2:
        m1 = (lb * 2 + ub) // 3
        m2 = (lb + ub * 2) // 3
        v1 = abs(2*cum[m1] - cum[i])
        v2 = abs(2*cum[m2] - cum[i])
        if v1 >= v2:
            lb = m1
        else:
            ub = m2
    P = min(cum[lb], cum[lb+1], key=lambda x: abs(2*x - cum[i]))
    Q = cum[i] - P

    lb, ub = i+1, N
    while ub - lb > 2:
        m1 = (lb * 2 + ub) // 3
        m2 = (lb + ub * 2) // 3
        v1 = abs(2*(cum[m1]-cum[i]) - (cum[-1]-cum[i]))
        v2 = abs(2*(cum[m2]-cum[i]) - (cum[-1]-cum[i]))
        if v1 >= v2:
            lb = m1
        else:
            ub = m2
    R = min(cum[lb] - cum[i], cum[lb+1] - cum[i], key=lambda x: abs(2*x - (cum[-1] - cum[i])))
    S = cum[-1] - cum[i] - R

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

Solution (Python):
import bisect
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
A = list(accumulate(A))
s = A[-1]
ans = float("inf")
for i in range(1, n-2):
  left = bisect.bisect(A, A[i]//2)
  right = bisect.bisect(A, (A[i]+s)//2)
  lm = float("inf")
  lM = 0
  rm = float("inf")
  rM = 0
  ld = float("inf")
  rd = float("inf")
  for j in range(-1, 2):
    if 0 <= left+j < i:
      a = A[left+j]
      b = A[i] - a
      if ld > abs(b-a):
        ld = abs(b-a)
        lm = min(a, b)
        lM = max(a, b)
    if i <= right+j < n-1:
      a = A[right+j] - A[i]
      b = s - A[right+j]
      if rd > abs(b-a):
        rd = abs(b-a)
        rm = min(a, b)
        rM = max(a, b)
  ans = min(ans, max(lM, rM) - min(lm, rm))
print(ans)

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

from bisect import bisect
cums = [0]
for a in A:
    cums.append(cums[-1] + a)
lmn = []
lmx = []
for i in range(2,N-1):
    j = bisect(cums, cums[i]//2)
    a1,b1 = cums[j],cums[i]-cums[j]
    a2,b2 = cums[j-1],cums[i]-cums[j-1]
    if abs(a1-b1) < abs(a2-b2):
        lmn.append(min(a1,b1))
        lmx.append(max(a1,b1))
    else:
        lmn.append(min(a2,b2))
        lmx.append(max(a2,b2))

A.reverse()
cums = [0]
for a in A:
    cums.append(cums[-1] + a)
rmn = []
rmx = []
for i in range(2,N-1):
    j = bisect(cums, cums[i]//2)
    a1,b1 = cums[j],cums[i]-cums[j]
    a2,b2 = cums[j-1],cums[i]-cums[j-1]
    if abs(a1-b1) < abs(a2-b2):
        rmn.append(min(a1,b1))
        rmx.append(max(a1,b1))
    else:
        rmn.append(min(a2,b2))
        rmx.append(max(a2,b2))
rmn.reverse()
rmx.reverse()

ans = 10**12
for ln,lx,rn,rx in zip(lmn,lmx,rmn,rmx):
    d = max(lx,rx) - min(ln,rn)
    ans = min(ans, d)
print(ans)

Solution (Python):
from collections import deque
N = int(input())
A = list(map(int, input().split()))

L = [(10**18, 10**18, 10**18)] * (N + 1)
left = 0
right = 0
que = deque([])
for i, a in enumerate(A, start=1):
    right += a
    que.append(a)
    while len(que) > 1 and abs(right - left) > abs((right - que[0]) - (left + que[0])):
        q = que.popleft()
        left += q
        right -= q
    L[i] = (abs(left - right), left, right)

R = [(10**18, 10**18, 10**18)] * (N + 1)
left = 0
right = 0
que = deque([])
for i, a in enumerate(A[::-1], start=1):
    right += a
    que.append(a)
    while len(que) > 1 and abs(right - left) > abs((right - que[0]) - (left + que[0])):
        q = que.popleft()
        left += q
        right -= q
    R[i] = (abs(left - right), left, right)

R = R[::-1]

ans = 10**18
for mid in range(1, N):
    X = [L[mid + 1][1], L[mid + 1][2], R[mid + 1][1], R[mid + 1][2]]
    if min(X) == 0:
        continue
    ans = min(ans, max(X) - min(X))
print(ans)

Solution (Python):
from collections import deque
N = int(input())
A = list(map(int, input().split()))

L = [(10**18, 10**18, 10**18)] * (N + 1)
left = 0
right = 0
que = deque([])
for i, a in enumerate(A, start=1):
    right += a
    que.append(a)
    while len(que) > 1 and abs(right - left) > abs((right - que[0]) - (left + que[0])):
        q = que.popleft()
        left += q
        right -= q
    L[i] = (abs(left - right), left, right)

R = [(10**18, 10**18, 10**18)] * (N + 1)
left = 0
right = 0
que = deque([])
for i, a in enumerate(A[::-1], start=1):
    right += a
    que.append(a)
    while len(que) > 1 and abs(right - left) > abs((right - que[0]) - (left + que[0])):
        q = que.popleft()
        left += q
        right -= q
    R[i] = (abs(left - right), left, right)





R = R[::-1]

ans = 10**18
for mid in range(1, N):
    X = [L[mid + 1][1], L[mid + 1][2], R[mid + 1][1], R[mid + 1][2]]
    if min(X) == 0:
        continue
    ans = min(ans, max(X) - min(X))
print(ans)

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

ans = float('inf')
i = 0; j = 1; k = 2
P = cumsum[i]; Q = cumsum[j]-cumsum[i]
diff1 = abs(P - Q)
R = cumsum[k]-cumsum[j]; S = cumsum[-1] - cumsum[k]
diff2 = abs(R - S)
while j <= N - 3:
  while i < j - 1:
    if abs(P - Q + 2*A[i+1]) < diff1:
      i += 1
      P += A[i]
      Q -= A[i]
      diff1 = abs(P - Q)
    else:
      break
  while k <= N - 3:
    if abs(R - S + 2*A[k+1]) < diff2:
      k += 1
      R += A[k]
      S -= A[k]
      diff2 = abs(R - S)
    else:
      break
  ans = min(ans, max(P, Q, R, S)-min(P, Q, R, S))
  j += 1
  Q += A[j]
  R -= A[j]
  diff1 = abs(P - Q)
  diff2 = abs(R - S)

print(ans)

Solution (Python):
N = int(input())
A = [int(_) for _ in input().split()]
 
ans = []
t = []
c = 0
for i in range(N):
    c += A[i]
    t.append(c)
    
l = 0
r = 0

for _ in range(1, N-1):
    while t[_] > t[l]+t[l+1]:
        l += 1
    while t[-1]+t[_] > t[r]+t[r+1]:
        r += 1
    n = [t[l], t[_]-t[l], t[r]-t[_], t[-1]-t[r]]
    ans.append(max(n)-min(n))
print(min(ans))

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



class BIT:
    """
    a[1]~a[n]の数列を想定
    """

    def __init__(self,n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def add(self,index,x):
        """
        a[index]にxを加算
        """
        while index <= self.size:
            self.tree[index] += x
            index += index & (-index)
 
    def sum(self,index):
        """
        a[1]~a[index]の和
        """
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s
 
    def search(self,value):
        """
        sum(index) >= value を満たす最小のindex
        sum(n) < value のとき n+1 を返す
        """
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i+step <= self.size and s + self.tree[i+step] < value:
                i += step
                s += self.tree[i]
            step >>= 1
        return i + 1

N = I()
A = LI()

sumA = sum(A)

bit = BIT(N)
for i in range(N):
    bit.add(i+1,A[i])

ans = float('inf')



for i in range(1,N-2):
    l_sum = bit.sum(i+1)
    r_sum = sumA-l_sum
    p = bit.search(l_sum+r_sum/2)
    if p == i+2:
        r_max = bit.sum(p)-bit.sum(i+1)
        r_min = r_sum-r_max
    elif p == N:
        r_min = bit.sum(p-1)-bit.sum(i+1)
        r_max = r_sum-r_min
    else:
        max1 = bit.sum(p)-bit.sum(i+1)
        min1 = r_sum-max1
        max2 = min1+A[p-1]
        min2 = max1-A[p-1]
        if max1-min1 < max2-min2:
            r_max = max1
            r_min = min1
        else:
            r_max = max2
            r_min = min2

    p = bit.search(l_sum/2)
    if p == 1:
        l_max = bit.sum(p)
        l_min = l_sum-l_max
    elif p == i+1:
        l_min = bit.sum(p-1)
        l_max = l_sum-l_min
    else:
        max1 = bit.sum(p)
        min1 = l_sum-max1
        max2 = min1+A[p-1]
        min2 = max1-A[p-1]
        if max1-min1 < max2-min2:
            l_max = max1
            l_min = min1
        else:
            l_max = max2
            l_min = min2

    now = max(l_max,r_max) - min(l_min,r_min)
    if now < ans:
        ans = now

print(ans)

Solution (Python):
import sys
from itertools import accumulate
from bisect import bisect
def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    ac = [0] + list(accumulate(A))

    def calc(lst): return abs(max(lst) - min(lst))
    def sm(l,r): return ac[r+1] - ac[l]

    ans = 10**18
    Q_left, S_left = 1, 3
    for R_left in range(2,N-1):
        P, Q = ac[Q_left], sm(Q_left, R_left-1)
        for nql in range(Q_left+1, R_left):
            nP, nQ = ac[nql], sm(nql, R_left-1)
            if calc([nP, nQ]) > calc([P, Q]): break
            Q_left, P, Q = nql, nP, nQ
        R, S = sm(R_left, S_left-1), sm(S_left, N-1)
        for nsl in range(S_left+1, N):
            nR, nS = sm(R_left, nsl-1), sm(nsl, N-1)
            if calc([nR, nS]) > calc([R, S]): break
            S_left, R, S = nsl, nR, nS
        ans = min(ans, calc([P,Q,R,S]))
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate
from bisect import bisect
def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    ac = [0] + list(accumulate(A))

    def calc(lst): return abs(max(lst) - min(lst))
    def sm(l,r): return ac[r+1] - ac[l]
    def get_min_max(l,r):
        if r-l <= 1: return [A[l], A[r]]
        med = ac[l] + sm(l,r) / 2
        i = bisect(ac, med, l+1, r+1)
        r1 = [sm(l,i-1), sm(i,r)]
        if i-1 == l: return r1
        r2 = [sm(l,i-2), sm(i-1,r)]
        return r1 if calc(r1) < calc(r2) else r2

    ans = 10**18
    for R_left in range(2,N-1):
        PQ_mm = get_min_max(0, R_left-1)
        RS_mm = get_min_max(R_left, N-1)
        ans = min(ans, calc(PQ_mm + RS_mm))
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

def bsearch(mn, mx, func):
    
    idx = (mx + mn)//2
    while mx-mn>1:
        if func(idx):
            idx, mx = (idx + mn)//2, idx
            continue
        idx, mn = (idx + mx)//2, idx
    return idx
N, = map(int, input().split())
A = list(map(int, input().split()))
X = [0]*(N+2)
for i in range(N):
    X[i+1] = X[i] + A[i]

R = 10**18
for i in range(2, N-1):
    
    
    idx1 = bsearch(1, i-1, lambda j:X[i]//2 < X[j])
    idx2 = bsearch(i+1, N, lambda j:(X[N]-X[i])//2 < (X[j]-X[i]))

    if idx1+1 <= i-1:
        if abs(2*X[idx1]-X[i]) > abs(2*X[idx1+1]-X[i]):
            idx1+=1

    if idx2+1 <= N-1:
        if abs(2*X[idx2]-X[i]-X[N]) > abs(2*X[idx2+1]-X[i]-X[N]):
            idx2+=1
    mx = max([X[idx1], X[i]-X[idx1], X[idx2]-X[i], X[N]-X[idx2]])
    mn = min([X[idx1], X[i]-X[idx1], X[idx2]-X[i], X[N]-X[idx2]])



    R = min(R, mx-mn)
print(R)

Solution (Python):
import bisect
n=int(input())
a=list(map(int,input().split()))
l=[0]
for i in range(n):
    l.append(l[-1]+a[i])
ans=10**20
for i in range(n-3):
    m=i+2
    f=bisect.bisect_left(l,l[m]//2)
    if f==m:
        f-=1
    f-=1
    if abs(l[m]-2*l[f])>abs(l[m]-2*l[f+1]):
        z=[l[m]-l[f+1],l[f+1]]
    else:
        z=[l[m]-l[f],l[f]]
    b=bisect.bisect_left(l,(l[-1]+l[m])//2)
    if b==n+1:
        b-=1
    if b==n:
        b-=1
    b-=1
    if abs((l[-1]-l[b])-(l[b]-l[m]))>abs((l[-1]-l[b+1])-(l[b+1]-l[m])):
        z.append(l[-1]-l[b+1])
        z.append(l[b+1]-l[m])
    else:
        z.append(l[-1]-l[b])
        z.append(l[b]-l[m])
    ans=min(ans,max(z)-min(z))
    
print(ans)

Solution (Python):
import math
n=int(input())
lists=list(map(int,input().split()))
sums=[0 for i in range(n)]
c=0
for i in range(n):
    c+=lists[i]
    sums[i]=c

ans=10**10
for i in range(1,n-2):
    a=sums[i]
    b=sums[n-1]-sums[i]

    
    a_left=0
    a_right=i-1
    b_left=i
    b_right=n-1
    for j in range(20):
        c=(a_left+a_right)/2
        if 2*sums[math.floor(c)]>a:
            a_left=a_left
            a_right=math.floor(c)
        elif 2*sums[math.floor(c)]<=a:
            a_left=math.floor(c)
            a_right=a_right
    for j in range(20):
        d=(b_left+b_right)/2
        if 2*(sums[math.floor(d)]-sums[i])>b:
            b_left=b_left
            b_right=math.floor(d)
        elif 2*(sums[math.floor(d)]-sums[i])<=b:
            b_left=math.floor(d)
            b_right=b_right

    A1=sums[a_left]
    A2=sums[a_left+1]
    B1=sums[b_left]
    B2=sums[b_left+1]
    J=abs(max(a-A1,A1,a+b-B1,B1-a)-min(a-A1,A1,a+b-B1,B1-a))
    K=abs(max(a-A2,A2,a+b-B2,B2-a)-min(a-A2,A2,a+b-B2,B2-a))
    L=abs(max(a-A2,A2,a+b-B1,B1-a)-min(a-A2,A2,a+b-B1,B1-a))
    M=abs(max(a-A1,A1,a+b-B2,B2-a)-min(a-A1,A1,a+b-B2,B2-a))
    ans=min(J,K,L,M,ans)
print(ans)

Solution (Python):


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


score = [A[0], A[1], A[2], sum(A[3:])]

ans = float("inf")
left, right = 1, 3


""" 尺取り法 """

for mid in range(2, N-1):
    
    while left < mid and abs(score[0] - score[1]) > abs((score[0] + A[left]) - (score[1] - A[left])):
        score[0] += A[left]
        score[1] -= A[left]
        left += 1
    
    while right < N and abs(score[2] - score[3]) > abs((score[2] + A[right]) - (score[3] - A[right])):
        score[2] += A[right]
        score[3] -= A[right]
        right += 1

    ans = min(ans, max(score) - min(score))

    score[1] += A[mid]
    score[2] -= A[mid]

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):
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy




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

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


def main(i,t,last):

    value=(S[last]-S[i])-(S[i]-S[t])
    if value>0:
        return(value)
    else:
        return(-value)

lst=[0,0,0,0]
ide_max=2*(10**9)

returndata=ide_max
for n in range(2,N-1):
    for t in [0,n]:
        passflag=0
        st=1+t
        if t==0:
            end=n-1
            last=n
        else:
            end=N
            last=N

        for z in [st,end]:
            if not main(z,t,last):
                Re=z
                passflag=1
        if not passflag:
            while 1:
                
                if st+3<end:
                    idx1=(st*2+end)//3
                    idx2=(st+end*2)//3
                    idx1v=main(idx1,t,last)
                    idx2v=main(idx2,t,last)
                    if idx1v>idx2v:
                        st=idx1
                    else:
                        end=idx2
                else :
                    value=ide_max
                    for i in range(st,end+1):
                        D=main(i,t,last)
                        if value>D:
                            value=D
                            Re=i
                    break
        if t==0:
            lst[0]=S[Re]-S[t]
            lst[1]=S[n]-S[Re]
        else:
            lst[2]=S[Re]-S[t]
            lst[3]=S[N]-S[Re]
    returndata=min(max(lst)-min(lst),returndata)
print(returndata)

Solution (Python):
import itertools
N=int(input())
A=list(map(int,input().split()))
Asum=list(itertools.accumulate(A))
leftcut=1
rightcut=3
ans=10**9
for i in range(2,N-1):
  Ldiff=abs((Asum[i-1]-Asum[leftcut-1])-Asum[leftcut-1])
  while leftcut+1<i:
    if abs((Asum[i-1]-Asum[leftcut+1-1])-Asum[leftcut+1-1]) < Ldiff:
      Ldiff=abs((Asum[i-1]-Asum[leftcut+1-1])-Asum[leftcut+1-1])
      leftcut+=1
    else:
      break
  Rdiff=abs((Asum[-1]-Asum[rightcut-1])-(Asum[rightcut-1]-Asum[i-1]))
  while rightcut+1<N:
    if abs((Asum[-1]-Asum[rightcut+1-1])-(Asum[rightcut+1-1]-Asum[i-1])) < Rdiff:
      Rdiff=abs((Asum[-1]-Asum[rightcut+1-1])-(Asum[rightcut+1-1]-Asum[i-1]))
      rightcut+=1
    else:
      break
  P=Asum[leftcut-1]
  Q=Asum[i-1]-Asum[leftcut-1]
  R=Asum[rightcut-1]-Asum[i-1]
  S=Asum[-1]-Asum[rightcut-1]
  ans=max(P,Q,R,S)-min(P,Q,R,S) if max(P,Q,R,S)-min(P,Q,R,S)<ans else ans
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

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

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

    ans = 10**15
    for i in range(1, N-2):
        L = AA[i+1]
        ok = i
        ng = -1
        mid = (ok+ng)//2
        while ok-ng > 1:
            if AA[mid+1] >= (L+1)//2:
                ok = mid
            else:
                ng = mid
            mid = (ok+ng)//2
        L_list = []
        if ok != 0:
            L_list.append((AA[ok], L - AA[ok]))
        if ok != i:
            L_list.append((AA[ok+1], L - AA[ok+1]))

        R = AA[-1] - L
        ok = N-1
        ng = i
        mid = (ok + ng) // 2
        while ok - ng > 1:
            if AA[mid+1] - AA[i+1] >= (R + 1) // 2:
                ok = mid
            else:
                ng = mid
            mid = (ok + ng) // 2
        R_list = []
        if ok != i+1:
            R_list.append((AA[ok] - AA[i+1], R - AA[ok] + AA[i+1]))
        if ok != N-1:
            R_list.append((AA[ok+1] - AA[i+1], R - AA[ok+1] + AA[i+1]))

        for p, q in L_list:
            for r, s in R_list:
                ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
                
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect
N = int(input())
A = list(map(int,input().split()))
cums = [0]
for a in A:
    cums.append(cums[-1] + a)

lmx = []
lmn = []
for i in range(2,N-1):
    j = bisect(cums,(cums[i]+1)//2)
    a1,b1 = cums[j], cums[i]-cums[j]
    a2,b2 = cums[j-1], cums[i]-cums[j-1]
    if abs(a1-b1) < abs(a2-b2):
        a,b = (a1,b1) if a1<b1 else (b1,a1)
    else:
        a,b = (a2,b2) if a2<b2 else (b2,a2)
    lmn.append(a)
    lmx.append(b)

rmx = []
rmn = []
MX = cums[-1]
for i in range(2,N-1):
    j = bisect(cums, cums[i] + (MX-cums[i])//2)
    a1,b1 = cums[j]-cums[i], MX-cums[j]
    a2,b2 = cums[j-1]-cums[i], MX-cums[j-1]
    if abs(a1-b1) < abs(a2-b2):
        a,b = (a1,b1) if a1<b1 else (b1,a1)
    else:
        a,b = (a2,b2) if a2<b2 else (b2,a2)
    rmn.append(a)
    rmx.append(b)

ans = MX
for ln,lx,rn,rx in zip(lmn,lmx,rmn,rmx):
    d = max(lx,rx) - min(ln,rn)
    ans = min(ans, d)
print(ans)

Solution (Python):
n = int(input())
a = [0] + list(map(int, input().split()))
for i in range(n):
  a[i+1] += a[i]
an = a[-1]
ans = an
p,r = 1,3
for q in range(2,n-1):
  lef = a[q]
  while abs(a[p]*2-lef) > abs(a[p+1]*2-lef):
    p += 1
  while r < n and abs(an+lef-a[r]*2) > abs(an+lef-a[r+1]*2):
    r += 1
  l = [a[p]-a[0], a[q]-a[p], a[r]-a[q], an-a[r]]
  cur = max(l)-min(l)
  if ans > cur:
    ans = cur
print(ans)

Solution (Python):
def main():
    n = int(input())
    *a, = map(int, input().split())

    
    tot = sum(a)
    ret = tot

    i, k = 1, 3
    p, q, r, s = a[0], a[1], a[2], tot - sum(a[:3])

    for j in range(2, n - 1):
        while (i + 1 < j) and (abs(p - q + a[i] * 2) < abs(p - q)):
            p += a[i]
            q -= a[i]
            i += 1

        while (k + 1 < n) and (abs(r - s + a[k] * 2) < abs(r - s)):
            r += a[k]
            s -= a[k]
            k += 1

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

        q += a[j]
        r -= a[j]

    print(ret)


if __name__ == '__main__':
    main()