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()))
c = list(accumulate(a))
ans = float("inf")
x, y = 0, 2
for i in range(1, n - 2):
    while c[x] < c[i] - c[x + 1]:
        x += 1
    y = max(y, i + 1)
    while c[y] - c[i] < c[-1] - c[y + 1]:
        y += 1
    ma = max(c[x], c[i] - c[x], c[y] - c[i], c[-1] - c[y])
    mi = min(c[x], c[i] - c[x], c[y] - c[i], c[-1] - c[y])
    ans = min(ans, ma - mi)
print(ans)

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

A_sum = []
tmp = 0
for a in A:
  tmp += a
  A_sum.append(tmp)

ans = 10**10
for part_mid in range(1,N-2):
  sum_l = A_sum[part_mid]
  part_lft = bisect.bisect_right(A_sum, (A_sum[part_mid]+0)//2)-1
  if part_lft == -1 or abs(2*A_sum[part_lft+1] - A_sum[part_mid]) < abs(2*A_sum[part_lft] - A_sum[part_mid]):
    part_lft += 1
  
  part_rgt = bisect.bisect_right(A_sum, (A_sum[N-1]+A_sum[part_mid])//2)-1
  if part_rgt < part_mid or abs(2*A_sum[part_rgt+1] - (A_sum[N-1]+A_sum[part_mid])) < abs(2*A_sum[part_rgt] - (A_sum[N-1]+A_sum[part_mid])):
    part_rgt += 1
  s = [A_sum[part_lft], A_sum[part_mid] - A_sum[part_lft], A_sum[part_rgt]-A_sum[part_mid], A_sum[N-1] - A_sum[part_rgt]]
  ans = min(ans, max(s) - min(s))
  
  
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline









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



b_end = 1
c_end = 2
d_end = 3
e_end = len(A) - 1
bc_best = 10 ** 10
de_best = 10 ** 10
ans = 10 ** 10
def get_ans(b_end,c_end,d_end):
  B = A[b_end]
  C = A[c_end] - A[b_end]
  D = A[d_end] - A[c_end]
  E = A[-1] - A[d_end]


  return max(B,C,D,E) - min(B,C,D,E)

for c_end in range(2, N - 1):
  
  
  B = A[b_end]
  C = A[c_end] - A[b_end]
  best_b_end = b_end
  if B != C:
    while b_end + 1 < c_end and B < C:
      b_end += 1
      tempB = B
      tempC = C
      B = A[b_end]
      C = A[c_end] - A[b_end]
      if B == C:
        best_b_end = b_end
        break
      if B > C:
        
        if abs(tempB - tempC) > abs(B - C):
          best_b_end = b_end
        break
      else:
        best_b_end = b_end
  b_end = best_b_end
  
  D = A[d_end] - A[c_end]
  E = A[e_end] - A[d_end]
  best_d_end = d_end
  if D != E:
    while d_end + 1 < e_end and D < E:
      d_end += 1
      tempD = D
      tempE = E
      D = A[d_end] - A[c_end]
      E = A[e_end] - A[d_end]
      if D == E:
        best_d_end = d_end
        break
      if D > E:
        if abs(tempD - tempE) > abs(D - E):
          best_d_end = d_end
        break
      else:
        best_d_end = d_end
  d_end = best_d_end
    
  val = get_ans(b_end,c_end,d_end)
  if val < ans:
    ans = val
    
print(ans)

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

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

X = [0]*N
Y = [0]*N

p = 0

for i in range(1,N-2):
    
    while S[p] * 2 < S[i] and p < i-1:
        p += 1
    
    if p == 0:
        X[i] = p
    elif abs(S[i]-2*S[p]) < abs(S[i]-2*S[p-1]):
        X[i] = p
    else:
        X[i] = p-1
    
    

q = 2

for i in range(1,N-2):
    if q <= i:
        q = i+1
    
    while (S[q]-S[i])*2 < S[N-1]-S[i] and q < N-2:
        q += 1
    
    if q == i+1:
        Y[i] = q
    elif abs((S[N-1]-S[q])-(S[q]-S[i])) < abs((S[N-1]-S[q-1])-(S[q-1]-S[i])):
        Y[i] = q
    else:
        Y[i] = q-1
    
    





ans = 10**15
for i in range(1,N-2):
    cut = (S[X[i]],S[i]-S[X[i]],S[Y[i]]-S[i],S[N-1]-S[Y[i]])
    ans = min(ans,max(cut)-min(cut))
    

print(ans)

Solution (Python):
from itertools import *
N = int(input())
A = list(accumulate(map(int,input().split())))
l = 0
r = 2
t = A[-1]
a = t

for m in A[1:-2]:
  while abs(t-2*A[r]+m)>abs(t-2*A[r+1]+m):
    r+=1
  while abs(m-2*A[l])>abs(m-2*A[l+1]):
    l+=1
  x = sorted([A[l],m-A[l],A[r]-m,t-A[r]])
  a = min(a,x[3]-x[0])

print(a)

Solution (Python):
def main():
    from bisect import bisect_left

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

    
    
    cs = [0] * n
    for i in range(n):
        cs[i] = cs[i-1] + a[i]

    
    ans = 10**15
    for middle in range(2, n-1):
        
        first = bisect_left(cs, cs[middle-1]//2, lo=1, hi=middle)
        if abs((cs[middle-1] - cs[first-1]) - cs[first-1]) < abs((cs[middle-1] - cs[first]) - cs[first]):
            p = cs[first-1]
            q = cs[middle-1] - cs[first-1]
        else:
            p = cs[first]
            q = cs[middle-1] - cs[first]

        
        last = bisect_left(cs, (cs[-1] + cs[middle-1])//2, lo=middle+1, hi=n)
        if abs((cs[-1] - cs[last-1]) - (cs[last-1] - cs[middle-1])) < abs((cs[-1] - cs[last]) - (cs[last] - cs[middle-1])):
            r = cs[last-1] - cs[middle-1]
            s = cs[-1] - cs[last-1]
        else:
            r = cs[last] - cs[middle-1]
            s = cs[-1] - cs[last]
        
        diff = max(p, q, r, s) - min(p, q, r, s)
        if diff < ans:
            ans = diff
    
    print(ans)

main()

Solution (Python):
def main():
    from bisect import bisect_left

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

    
    
    cs = [0] * n
    for i in range(n):
        cs[i] = cs[i-1] + a[i]

    
    ans = 10**15
    for middle in range(2, n-1):
        
        first = bisect_left(cs, cs[middle-1]//2, lo=1, hi=middle)
        if abs((cs[middle-1] - cs[first-1]) - cs[first-1]) < abs((cs[middle-1] - cs[first]) - cs[first]):
            p = cs[first-1]
            q = cs[middle-1] - cs[first-1]
        else:
            p = cs[first]
            q = cs[middle-1] - cs[first]

        
        last = bisect_left(cs, (cs[-1] + cs[middle-1])//2, lo=middle+1, hi=n)
        if abs((cs[-1] - cs[last-1]) - (cs[last-1] - cs[middle-1])) < abs((cs[-1] - cs[last]) - (cs[last] - cs[middle-1])):
            r = cs[last-1] - cs[middle-1]
            s = cs[-1] - cs[last-1]
        else:
            r = cs[last] - cs[middle-1]
            s = cs[-1] - cs[last]
        
        diff = max(p, q, r, s) - min(p, q, r, s)
        if diff < ans:
            ans = diff
    
    print(ans)

main()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N = I()
A = IL()

def ACC1(l):
  N = len(l)
  ret = [0]*(N+1)
  for i in range(N):
    ret[i+1] = ret[i]+l[i]
  return ret
def calc_half(l,r):
  start = ACC[l]
  end = ACC[r+1]
  p = bisect.bisect(ACC,-((-(start+end))//2))
  P1,Q1 = ACC[p]-ACC[l],ACC[r+1]-ACC[p]
  P2,Q2 = ACC[p-1]-ACC[l],ACC[r+1]-ACC[p-1]
  
  if abs(P1-Q1)<abs(P2-Q2):
    return P1,Q1
  else:
    return P2,Q2
ans = INF
ACC = ACC1(A)

for i in range(1,N-2):
  P,Q = calc_half(0,i)
  R,S = calc_half(i+1,N-1)
  
  ans = min(ans,max(P,Q,R,S)-min(P,Q,R,S))
print(ans)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


N = I()
A = [0] + LI()

from itertools import accumulate

S = list(accumulate(A))

ans = 10**18
for i in range(2,N-1):  
    left = S[i]
    right = S[N]-S[i]
    
    low1,high1 = 0,i
    while low1 + 1 < high1:
        mid1 = (low1+high1)//2
        if S[mid1] >= (left+1)//2:
            high1 = mid1
        else:
            low1 = mid1
    low2,high2 = i,N
    while low2 + 1 < high2:
        mid2 = (low2+high2)//2
        if S[mid2]-S[i] >= (right+1)//2:
            high2 = mid2
        else:
            low2 = mid2
    x1 = max(S[high1],S[high2]-left) - min(left-S[high1],right-S[high2]+left)
    x2 = max(S[high1],right-S[high2-1]+left) - min(left-S[high1],S[high2-1]-left)
    x3 = max(left-S[high1-1],S[high2]-left) - min(S[high1-1],right-S[high2]+left)
    x4 = max(left-S[high1-1],right-S[high2-1]+left) - min(S[high1-1],S[high2-1]-left)
    ans = min(ans,x1,x2,x3,x4)

print(ans)

Solution (Python):
from bisect import *
from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
S = [0] + list(accumulate(A))
res = float("inf")
for i in range(2,N-1):
    j = bisect_left(S,S[i]//2)
    if abs(S[i]-2*S[j]) >= abs(S[i]-2*S[j-1]):
        P =[S[j-1], S[i]-S[j-1]]
    else: P = [S[j], S[i]-S[j]]
    T = S[-1] - S[i]
    j = bisect_left(S,S[-1]-T//2)
    U1, U2 = S[j]-S[i],S[j-1]-S[i]
    if abs(T-2*U1) >= abs(T-2*U2):
        P += [U2, T-U2]
    else: P += [U1, T-U1]
    tmp = max(P)-min(P)
    res = min(res, tmp)
print(res)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
acc=[0]*N
acc[0]=A[0]
for i in range(1,N):
  acc[i]=acc[i-1]+A[i]
def f(x,y):
  if x==0:
    return acc[y]
  else:
    return acc[y]-acc[x-1]
left=0
right=2

import math
ans=math.inf
for mid in range(1,N-2):

  while abs(f(0,left)-f(left+1,mid))>=abs(f(0,left+1)-f(left+2,mid)):
    left+=1
    if left==mid-1:
      break
  while abs(f(mid+1,right)-f(right+1,N-1))>=abs(f(mid+1,right+1)-f(right+2,N-1)):
    right+=1
    if right==N-2:
      break
  list=[f(0,left),f(left+1,mid),f(mid+1,right),f(right+1,N-1)]
  tans=max(list)-min(list)
  ans=min(tans,ans)
print(ans)

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

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

ans=float("inf")
l=0
r=1
for i in range(1, n-2):
    while abs(ac[i]-2*ac[l+1]) < abs(ac[i]-2*ac[l]) and l < i+1:
        l+=1
    while abs(ac[-1]-2*ac[r+1]+ac[i]) < abs(ac[-1]-2*ac[r]+ac[i]) and r < n-2:
        r+=1
    t=[ac[l], ac[i]-ac[l], ac[r]-ac[i], ac[-1]-ac[r]]
    ans=min(ans, max(t)-min(t))
print(ans)

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

ans = float('inf')

f=1
g=3
for i in range(2, N - 1):

    while abs(lr[i] - lr[f] - lr[f]) > abs(lr[i] - lr[f + 1] - lr[f + 1]):
        f += 1
    while abs((lr[-1] - lr[g]) - (lr[g] - lr[i])) > abs((lr[-1] - lr[g + 1]) - (lr[g + 1] - lr[i])):
        g += 1
    l = (lr[f], lr[i] - lr[f], lr[-1] - lr[g], lr[g] - lr[i])
    ans = min(ans, max(l) - min(l))

print(ans)

Solution (Python):


from itertools import accumulate, islice
from bisect import bisect_left

n = int(input())
xs = list(map(int, 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):
n = int(input())
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = b[i] + a[i]
x = [[0, 0] for _ in range(n - 3)]
j = 1
for i in range(2, n - 1):
    while True:
        if i == j + 1:
            x[i - 2][0] = b[j]
            break
        if abs(b[i] - 2 * b[j]) > abs(b[i] - 2 * b[j + 1]):
            j += 1
        else:
            x[i - 2][0] = b[j]
            break
j = n - 1
for i in range(n - 2, 1, -1):
    while True:
        if i == j - 1:
            x[i - 2][1] = b[j]
            break
        if abs(b[n] + b[i] - 2 * b[j]) > abs(b[n] + b[i] - 2 * b[j - 1]):
            j -= 1
        else:
            x[i - 2][1] = b[j]
            break
ans = 1145141919810
for i in range(n - 3):
    s = [x[i][0], b[i + 2] - x[i][0], x[i][1] - b[i + 2], b[n] - x[i][1]]
    ans = min(ans, max(s) - min(s))
print(ans)

Solution (Python):
from bisect import bisect_left
n=int(input())
a=list(map(int,input().split()))
bl=[0]
for i in a:bl.append(bl[-1]+i)
br=[0]
for i in a[::-1]:br.append(br[-1]+i)
def fl(r):
  suma=bl[r+1]
  ir=bisect_left(bl,suma//2)
  ans11,ans12=bl[ir],suma-bl[ir]
  ans21,ans22=bl[ir-1],suma-bl[ir-1]
  if abs(ans11-ans12)<abs(ans21-ans22):return[ans11,ans12]
  else:return[ans21,ans22]
def fr(l):
  r=(n-1)-l
  suma=br[r+1]
  ir=bisect_left(br,suma//2)
  ans11,ans12=br[ir],suma-br[ir]
  ans21,ans22=br[ir-1],suma-br[ir-1]
  if abs(ans11-ans12)<abs(ans21-ans22):return[ans11,ans12]
  else:return[ans21,ans22]
ans=10**20
for i in range(1,n-1):
  l=i
  r=i+1
  ll,lr=fl(i)
  rl,rr=fr(i+1)
  ans=min(ans,max(ll,lr,rl,rr)-min(ll,lr,rl,rr))
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
R = [0] * (N + 1)
for i in range(N):
  R[i + 1] += R[i] + A[i]


ans = 10 ** 15
l, r = 2, 4
for i in range(3, N):
  
  
  
  while abs(R[i - 1] - 2 * R[l]) <= abs(R[i - 1] - 2 * R[l - 1]):
    l += 1
    
  
  while abs(R[N] - 2 * R[r] + R[i - 1]) <= abs(R[N] - 2 * R[r - 1] + R[i - 1]):
    r += 1  
  
  now_max = max(max(R[l - 1], R[i - 1] - R[l - 1]), max(R[r - 1] - R[i - 1], R[N] - R[r - 1]))
  now_min = min(min(R[l - 1], R[i - 1] - R[l - 1]), min(R[r - 1] - R[i - 1], R[N] - R[r - 1]))
  ans = min(ans, now_max - now_min)
  
print(ans)

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

ans = 10 ** 18


A = tuple(accumulate(A, initial=0))
i = 1
j = 3


for mid in range(2, N - 1):
    
    b = A[i] - A[0]
    c = A[mid] - A[i]
    while i + 1 < mid and abs(b - c) > abs(A[mid] + A[0] - 2 * A[i+1]):
        i += 1
        b = A[i] - A[0]
        c = A[mid] - A[i]
    
    j = max(j, mid + 1)
    d = A[j] - A[mid]
    e = A[N] - A[j]
    while j + 1 < N and abs(d - e) > abs(A[N] + A[mid] - 2 * A[j+1]):
        j += 1
        d = A[j] - A[mid]
        e = A[N] - A[j]

    res = max(b, c, d, e) - min(b, c, d, e)
    ans = min(ans, res)

print(ans)

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

ans=float('inf')

f,g=1,3
for i in range(2,N-1):
  while abs(lr[i]-lr[f]-lr[f])>abs(lr[i]-lr[f+1]-lr[f+1]):
    f+=1
  while abs((lr[-1]-lr[g])-(lr[g]-lr[i]))>abs((lr[-1]-lr[g+1])-(lr[g+1]-lr[i])):
    g+=1
  l=(lr[f],lr[i]-lr[f],lr[-1]-lr[g],lr[g]-lr[i])
  ans=min(ans,max(l)-min(l))

print(ans)

Solution (Python):
import bisect
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

class Accumulation:
    def __init__(self,X,accumfunc,init_val=0):
        self.X = X
        self.accumfunc = accumfunc

        N = len(X)
        v1 = [0] * (N+1)
        v1[0] = init_val

        for i in range(N):
            v1[i+1] = accumfunc(v1[i],X[i])

        self.v1 = v1
    
    
    def query(self,l,r):
        return self.v1[r+1] - self.v1[l]
    
    def get_array(self):
        return self.v1

INF=10**20
def main():
    N=ii()
    A=list(mi())
    B = []
    for a in A:
        B.append(a*2)

    def add(x,y): return x+y

    acc = Accumulation(A,add)
    accB = Accumulation(B,add)

    vA = acc.get_array()
    vB = accB.get_array()

    ans = INF
    for j in range(N):
        i1 = bisect.bisect_left(vB,vA[j+1]) - 1 

        Q,P=0,INF
        for di in [-1,0,1]:
            if not 0<= i1+di < N: continue
            q,p = acc.query(i1+di+1,j), acc.query(0,i1+di)
            if abs(p-q) < abs(P-Q):
                Q,P = q,p

        S,R = 0,INF
        i2 = bisect.bisect_left(vB,vA[N]+vA[j+1]) - 1
        for di in [-1,0,1]:
            if not 0<= i2+di < N: continue
            s,r = acc.query(i2+di+1,N-1), acc.query(j+1,i2+di)
            if abs(s-r) < abs(S-R):
                S,R=s,r



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


    print(ans)





if __name__ == "__main__":
    main()

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

for i in range(N):
    S.append(S[-1] + A[i])

res = 10**18

for i in range(2, N - 1):
    hi = i
    lo = 0
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if S[mid] - S[0] >= S[i] - S[mid]:
            hi = mid
        else:
            lo = mid
    p = S[hi] - S[0]
    q = S[i] - S[hi]
    if p - q > (q + A[hi - 1]) - (p - A[hi - 1]):
        p -= A[hi - 1]
        q += A[hi - 1]

    hi = N
    lo = i
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if S[mid] - S[i] >= S[N] - S[mid]:
            hi = mid
        else:
            lo = mid
    s = S[hi] - S[i]
    t = S[N] - S[hi]
    if s - t > (t + A[hi - 1]) - (s - A[hi - 1]):
        s -= A[hi - 1]
        t += A[hi - 1]

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

print(res)

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

for i in range(N):
    S.append(S[-1] + A[i])

res = 10**18

for i in range(2, N - 1):
    hi = i
    lo = 0
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if S[mid] - S[0] >= S[i] - S[mid]:
            hi = mid
        else:
            lo = mid
    p = S[hi] - S[0]
    q = S[i] - S[hi]
    if p - q > abs((p - A[hi - 1]) - (q + A[hi - 1])):
        p -= A[hi - 1]
        q += A[hi - 1]

    hi = N
    lo = i
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if S[mid] - S[i] >= S[N] - S[mid]:
            hi = mid
        else:
            lo = mid
    s = S[hi] - S[i]
    t = S[N] - S[hi]
    if s - t > abs((s - A[hi - 1]) - (t + A[hi - 1])):
        s -= A[hi - 1]
        t += A[hi - 1]

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

print(res)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N = getN()
A = getList()
fore = copy.deepcopy(A)
back = copy.deepcopy(A)

for i in range(N - 1):
    fore[i + 1] += fore[i]
    back[N - i - 2] += back[N - i - 1]

left = 0
total = A[0]

fore_list = []
for right in range(1, N - 2):
    while abs((fore[right] / 2) - (total + A[left + 1])) < abs((fore[right] / 2) - total):
        left += 1
        total += A[left]
    fore_list.append([right, total, fore[right] - total])

right = N - 1
total = A[-1]

back_list = []
for left in range(N - 2, 1, -1):
    while abs((back[left] / 2) - (total + A[right - 1])) < abs((back[left] / 2) - total):
        right -= 1
        total += A[right]
    back_list.append([left, total, back[left] - total])
back_list.sort()

ans = float('inf')
for i in range(len(back_list)):
    ind1, a, b = fore_list[i]
    ind2, c, d = back_list[i]
    opt = max(a, b, c, d) - min(a, b, c, d)
    ans = min(ans, opt)
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
def solve(n, a):
    b, c, d, e = a[0], a[1], a[2], sum(a[3:])
    bc = b + c
    de = d + e
    bci = 1
    dei = 3
    ans = max(b, c, d, e) - min(b, c, d, e)
    for i in range(2, n - 1):
        while i - bci > 1 and (min(b, c) < min(b + a[bci], c - a[bci])):
            b += a[bci]
            c -= a[bci]
            bci += 1
        while dei < n - 1 and (max(d, e) > max(d + a[dei], e - a[dei])):
            d += a[dei]
            e -= a[dei]
            dei += 1
        ans = min(ans, max(b, c, d, e) - min(b, c, d, e))
        bc += a[i]
        de -= a[i]
        c += a[i]
        d -= a[i]
        if i + 1 >= dei:
            d += a[dei]
            e -= a[dei]
            dei += 1
    return ans

print(min(solve(n, a), solve(n, list(a))))

Solution (Python):

import bisect

N = int(input())
A = list(int(a) for a in input().split())

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

ans = 10**18
for i in range(2, N-1):
    B = bisect.bisect_left(Acum, Acum[i]//2) - 1
    if abs(Acum[B] * 2 - Acum[i]) > abs(Acum[B+1] * 2 - Acum[i]):
        B += 1
    if B == i:
        B -= 1
    elif B == 0:
        B += 1
    P = Acum[B]
    Q = Acum[i] - Acum[B]
    D = bisect.bisect_left(Acum, Acum[i] + (Acum[-1]-Acum[i])//2) - 1
    if abs(Acum[D] * 2 - Acum[i] - Acum[-1]) > abs(Acum[D+1] * 2 - Acum[i] - Acum[-1]):
        D += 1
    if D == N:
        D -= 1
    elif D == i:
        D += 1
    R = Acum[D] - Acum[i]
    S = Acum[-1] - Acum[D]
    mi = min(P, Q, R, S)
    ma = max(P, Q, R, S)
    ans = min(ans, abs(ma - mi))
print(ans)

Solution (Python):
def calc(cum, p1, p2, p3):
    arr = [0]*4
    arr[0] = cum[p1]
    arr[1] = cum[p2] - cum[p1]
    arr[2] = cum[p3] - cum[p2]
    arr[3] = cum[-1] - cum[p3]
    return max(arr) - min(arr)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(n-1):
        a[i+1] += a[i]
    ans = float("inf")
    for i in range(1, n-2):
        p2 = i
        v = a[i]
        L, R = 0, p2
        while L+1 < R:
            P = (L+R)//2
            if a[P] <= v//2:
                L = P
            else:
                R = P
        p1 = L
        L, R = -1, p2-1
        while L+1 < R:
            P = (L+R+1)//2
            if a[P] <= v//2:
                L = P
            else:
                R = P
        p1_ = R
        L, R = p2+1, n-1
        while L+1 < R:
            P = (L+R)//2
            if a[P]-v <= (a[-1]-v)//2:
                L = P
            else:
                R = P
        p3 = L
        L, R = p2, n-2
        while L+1 < R:
            P = (L+R+1)//2
            if a[P]-v <= (a[-1]-v)//2:
                L = P
            else:
                R = P
        p3_ = R
        arr = [0]*4
        arr[0] = calc(a, p1, p2, p3)
        arr[1] = calc(a, p1_, p2, p3)
        arr[2] = calc(a, p1, p2, p3_)
        arr[3] = calc(a, p1_, p2, p3_)
        x = min(arr)
        if x < ans:
            ans = x
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from bisect import bisect_right
n = int(input())
a = [int(x) for x in input().split()]

cum = [0]
for x in a:
  cum.append(cum[-1]+x)

ans = 10**30
for z in range(4):
  for i in range(2,n-1):
    b = cum[bisect_right(cum, cum[i]//2)-1+(z&1)]
    c = cum[i]-b
    d = cum[bisect_right(cum, (cum[n]-cum[i])//2+cum[i])-1+(z>>1&1)] - cum[i]
    e = cum[n] - (b+c+d)
    ans = min(ans, max(b,c,d,e) - min(b,c,d,e))
  
print(ans)

Solution (Python):
from bisect import bisect_right
n = int(input())
a = [int(x) for x in input().split()]

cum = [0]
for x in a:
  cum.append(cum[-1]+x)

ans = 10**30
for i in range(2,n-1):
  for z in range(4):
    b = cum[bisect_right(cum, cum[i]//2)-1+(z&1)]
    c = cum[i]-b
    d = cum[bisect_right(cum, (cum[n]-cum[i])//2+cum[i])-1+(z>>1&1)] - cum[i]
    e = cum[n] - (b+c+d)
    ans = min(ans, max(b,c,d,e) - min(b,c,d,e))
  
print(ans)

Solution (Python):
import bisect

n=int(input())
arr=list(map(int,input().split()))
acum=[0]
for i in range(n):
  acum.append(acum[-1]+arr[i])
ans=10**18
for i in range(2,n-1):
  suma=acum[i]
  sumb=acum[n]-suma
  posa=bisect.bisect_right(acum,suma//2)
  diffa=10**18
  if posa>=2:
    mina=min(acum[posa-1],acum[i]-acum[posa-1])
    maxa=max(acum[posa-1],acum[i]-acum[posa-1])
    diffa=maxa-mina
  if posa!=i:
    tmina=min(acum[posa],acum[i]-acum[posa])
    tmaxa=max(acum[posa],acum[i]-acum[posa])
    tdiffa=tmaxa-tmina
    if tdiffa<diffa:
      diffa=tdiffa
      mina=tmina
      maxa=tmaxa
  posb=bisect.bisect_right(acum,suma+sumb//2)
  diffb=10**18
  if posb>=i+2:
    minb=min(acum[posb-1]-acum[i],acum[n]-acum[posb-1])
    maxb=max(acum[posb-1]-acum[i],acum[n]-acum[posb-1])
    diffb=maxb-minb
  if posa!=n+1:
    tminb=min(acum[posb]-acum[i],acum[n]-acum[posb])
    tmaxb=max(acum[posb]-acum[i],acum[n]-acum[posb])
    tdiffb=tmaxb-tminb
    if tdiffb<diffb:
      diffb=tdiffb
      minb=tminb
      maxb=tmaxb
  ans=min(ans,max(maxa,maxb)-min(mina,minb))
print(ans)

Solution (Python):
import bisect

n=int(input())
arr=list(map(int,input().split()))
acum=[0]
for i in range(n):
  acum.append(acum[-1]+arr[i])
ans=10**18
for i in range(2,n-1):
  suma=acum[i]
  sumb=acum[n]-suma
  posa=bisect.bisect_right(acum,suma//2)
  diffa=10**18
  if posa>=2:
    mina=min(acum[posa-1],acum[i]-acum[posa-1])
    maxa=max(acum[posa-1],acum[i]-acum[posa-1])
    diffa=maxa-mina
  if posa!=i:
    tmina=min(acum[posa],acum[i]-acum[posa])
    tmaxa=max(acum[posa],acum[i]-acum[posa])
    tdiffa=tmaxa-tmina
    if tdiffa<diffa:
      diffa=tdiffa
      mina=tmina
      maxa=tmaxa
  posb=bisect.bisect_right(acum,suma+sumb//2)
  diffb=10**18
  if posb>=i+2:
    minb=min(acum[posb-1]-acum[i],acum[n]-acum[posb-1])
    maxb=max(acum[posb-1]-acum[i],acum[n]-acum[posb-1])
    diffb=maxb-minb
  if posa!=n+1:
    tminb=min(acum[posb]-acum[i],acum[n]-acum[posb])
    tmaxb=max(acum[posb]-acum[i],acum[n]-acum[posb])
    tdiffb=tmaxb-tminb
    if tdiffb<diffb:
      diffb=tdiffb
      minb=tminb
      maxb=tmaxb
  ans=min(ans,max(maxa,maxb)-min(mina,minb))
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
tmp=0
ca=[0]
for ai in a:
  tmp+=ai
  ca.append(tmp)
from bisect import bisect_right,bisect_left
ans=float('inf')


f,g=1,3
for i in range(2,n-1):
  while abs(ca[i]-ca[f]-ca[f])>abs(ca[i]-ca[f+1]-ca[f+1]):
    f+=1
  while abs((ca[-1]-ca[g])-(ca[g]-ca[i]))>abs((ca[-1]-ca[g+1])-(ca[g+1]-ca[i])):
    g+=1
  l=(ca[f],ca[i]-ca[f],ca[-1]-ca[g],ca[g]-ca[i])
  ans=min(ans,max(l)-min(l))
  
print(ans)

Solution (Python):
import sys
from itertools import combinations
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    """
    まず２分して左右をさらにそれぞれ２分するときこれらはなるべく差が小さい方がよさそう
    """
    
    s = sum(A[2:])
    partial_s = 0
    init_r = N - 2
    for r in range(2, N - 1):
        partial_s += A[r]
        if partial_s * 2 > s:
            init_r = r
            break
    l = 0
    r = init_r
    sums = [A[0], A[1], partial_s, s - partial_s]
    ans = max(sums) - min(sums)
    temp = [sums[0], sums[1], sums[2] - A[r], sums[3] + A[r]]
    ans = min(ans, max(temp) - min(temp))
    


    
    for m in range(2, N - 2):
        
        sums[1] += A[m]
        while sums[0] <= sums[1] and l < m - 1:
            l += 1
            sums[0] += A[l]
            sums[1] -= A[l]
        
        sums[2] -= A[m]
        while sums[2] <= sums[3] and r < N - 2:
            r += 1
            sums[2] += A[r]
            sums[3] -= A[r]
        
        ans = min(ans, max(sums) - min(sums))
        temp = [sums[0] - A[l], sums[1] + A[l], sums[2], sums[3]]
        ans = min(ans, max(temp) - min(temp))
        temp = [sums[0], sums[1], sums[2] - A[r], sums[3] + A[r]]
        ans = min(ans, max(temp) - min(temp))
        temp = [sums[0] - A[l], sums[1] + A[l], sums[2] - A[r], sums[3] + A[r]]
        ans = min(ans, max(temp) - min(temp))
        
    print(ans)


if __name__ == "__main__":
    main()