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):
N=int(input())
A=list(map(int, input().split()))
D=[0]
d=0
for i in A:
  d+=i
  D.append(d)
s=D[-1]
D=D[1:-1]
d=s
import bisect
for i in range(1,len(D)-1):
  a=D[i]/2
  b=(D[i]+s)/2
  l=bisect.bisect_left(D,a)
  r=bisect.bisect_left(D,b)
  L,R=[],[]
  if l-1<i:
    L.append(l-1)
  if r-1<len(D):
    R.append(r-1)
  if l<i:
    L.append(l)
  if r<len(D):
    R.append(r)
  for j in L:
    for k in R:
      mi=min(s-D[k],D[k]-D[i],D[i]-D[j],D[j])
      ma=max(s-D[k],D[k]-D[i],D[i]-D[j],D[j])
      d=min(d,ma-mi)
print(d)

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

SUM = sum(A)
left = 0
right = 0
L = 0
M = 0
R = 0

ans = float('inf')

for mid in range(N):
    while abs(M - 2 * L) > abs(M - 2 * L - 2 * A[left]):
        L += A[left]
        left += 1
    
    while right < N and abs(SUM + M - 2 * R) > abs(SUM + M - 2 * R - 2 * A[right]):
        R += A[right]
        right += 1
    
    ans = min(ans, max(L, M - L, R - M, SUM - R) - min(L, M - L, R - M, SUM - R))
    
    M += A[mid]

print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
tmp=0
ca=[tmp]
for x in a:
  tmp+=x
  ca.append(tmp)
ans=float('inf')
bidx=0
cidx=1
didx=2
eidx=3

for didx in range(1,n-1):
  p=ca[cidx]-ca[bidx]
  q=ca[didx]-ca[cidx]
  r=ca[eidx]-ca[didx]
  s=ca[-1]-ca[eidx]
  
  np=ca[cidx+1]-ca[bidx]
  nq=ca[didx]-ca[cidx+1]
  while cidx+1<didx and abs(p-q)>abs(np-nq):
    cidx+=1
    p,q=np,nq
    np=ca[cidx+1]-ca[bidx]
    nq=ca[didx]-ca[cidx+1]

  nr=ca[eidx+1]-ca[didx]
  ns=ca[-1]-ca[eidx+1]
  while eidx+1<n and abs(r-s)>abs(nr-ns):
    eidx+=1
    r,s=nr,ns
    nr=ca[eidx+1]-ca[didx]
    ns=ca[-1]-ca[eidx+1]

  ans=min(ans,max(p,q,r,s)-min(p,q,r,s))
print(ans)

Solution (Python):
import bisect
import itertools
N = int(input())
A = [int(_) for _ in input().split()]
cum = list(itertools.accumulate(A))
ans = 10**10
for i2 in range(1, N - 2):
    i1 = i = bisect.bisect_left(cum, cum[i2] // 2)
    c = abs(cum[i2] - 2 * cum[i1])
    for j in range(i - 1, i + 2):
        if 0 <= j < i2 and abs(cum[i2] - 2 * cum[j]) < c:
            i1 = j
            c = abs(cum[i2] - 2 * cum[j])
    i3 = i = bisect.bisect_left(cum, (cum[i2] + cum[N - 1]) // 2)
    c = abs(cum[N - 1] + cum[i2] - 2 * cum[i3])
    for j in range(i - 1, i + 2):
        if i2 < j < N - 1 and abs(cum[N - 1] + cum[i2] - 2 * cum[j]) < c:
            i3 = j
            c = abs(cum[N - 1] + cum[i2] - 2 * cum[j])
    B = [cum[i1], cum[i2] - cum[i1], cum[i3] - cum[i2], cum[N - 1] - cum[i3]]
    ans = min(ans, max(B) - min(B))
print(ans)

Solution (Python):
import bisect
import itertools
N = int(input())
A = [int(_) for _ in input().split()]
cum = list(itertools.accumulate(A))
ans = 10**10
for i2 in range(1, N - 2):
    i1 = i = bisect.bisect_left(cum, cum[i2] // 2)
    c = abs(cum[i2] - 2 * cum[i1])
    for j in range(i - 1, i + 2):
        if 0 <= j < i2 and abs(cum[i2] - 2 * cum[j]) < c:
            i1 = j
            c = abs(cum[i2] - 2 * cum[j])
    i3 = i = bisect.bisect_left(cum, (cum[i2] + cum[N - 1]) // 2)
    c = abs(cum[N - 1] + cum[i2] - 2 * cum[i3])
    for j in range(i - 1, i + 2):
        if i2 < j < N - 1 and abs(cum[N - 1] + cum[i2] - 2 * cum[j]) < c:
            i3 = j
            c = abs(cum[N - 1] + cum[i2] - 2 * cum[j])
    B = [cum[i1], cum[i2] - cum[i1], cum[i3] - cum[i2], cum[N - 1] - cum[i3]]
    ans = min(ans, max(B) - min(B))
print(ans)

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

def main():
    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 = int(1e15)
    for i in range(n):
        sub = []
        for l, r, ll, rr in zip([0, i], [i, n], [0, i], [i, n]):
            while r-l > 1:
                k = (r+l) // 2
                if s[k] - s[ll] < s[rr] - s[k]:
                    l = k
                else:
                    r = k

            if abs(s[ll] + s[rr] - s[l]*2) > abs(s[ll] + s[rr] - s[r]*2):
                k = r
            else:
                k = l
            sub.append(s[k] - s[ll])
            sub.append(s[rr] - s[k])
        judge = max(sub) - min(sub)
        ans = min(ans, judge)
    
    print(ans)


    
if __name__ == "__main__":
    main()

Solution (Python):
from itertools import accumulate

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

csum = list(accumulate(As, initial=0))

P_end = 1
R_end = 3
ans = 10 ** 18
for Q_end in range(2, N - 1):
    former_half = csum[Q_end] / 2
    latter_half = (csum[-1] - csum[Q_end]) / 2
    while P_end + 1 <= Q_end and csum[P_end + 1] < former_half:
        P_end += 1
    while R_end + 1 < N and csum[R_end + 1] - csum[Q_end] < latter_half:
        R_end += 1
    
    if abs(csum[P_end] - former_half) > abs(csum[P_end + 1] - former_half):
        P = csum[P_end + 1]
    else:
        P = csum[P_end]
    Q = csum[Q_end] - P

    if abs(csum[R_end] - csum[Q_end] - latter_half) > abs(csum[R_end + 1] - csum[Q_end] - latter_half):
        R = csum[R_end + 1] - csum[Q_end]
        S = csum[-1] - csum[R_end + 1]
    else:
        R = csum[R_end] - csum[Q_end]
        S = csum[-1] - csum[R_end]

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

print(ans)

Solution (Python):
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    ans = 10**15
    from itertools import accumulate
    S = list(accumulate([0] + A))
    idx = [1, 2, 3]
    for center in range(2, N-1):
        idx[1] = center
        P_sum = S[idx[0]] - S[0]
        Q_sum = S[idx[1]] - S[idx[0]]
        mae_diff = abs(P_sum - Q_sum)
        while idx[0] < center - 1 and \
                abs((P_sum + A[idx[0]]) - (Q_sum - A[idx[0]])) < mae_diff:
            idx[0] += 1
            P_sum = S[idx[0]] - S[0]
            Q_sum = S[idx[1]] - S[idx[0]]
            mae_diff = abs(P_sum - Q_sum)

        R_sum = S[idx[2]] - S[idx[1]]
        S_sum = S[N] - S[idx[2]]
        usi_diff = abs(R_sum - S_sum)
        while idx[2] < N and \
                abs((R_sum + A[idx[2]]) - (S_sum - A[idx[2]])) < usi_diff:
            idx[2] += 1
            R_sum = S[idx[2]] - S[idx[1]]
            S_sum = S[N] - S[idx[2]]
            usi_diff = abs(R_sum - S_sum)

        ans = min(ans, abs(max(P_sum, Q_sum, R_sum, S_sum) -
                           min(P_sum, Q_sum, R_sum, S_sum)))
        if idx[1] + 1 == idx[2]:
            idx[2] += 1
    print(ans)


if __name__ == '__main__':
    main()

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

P = A[0]
Q = A[1]
Lsum = P+Q
Ldiff = abs(P-Q)
Li = 1
Rsum = sum(A) - Lsum
R = A[2]
S = Rsum - R
Rdiff = abs(R-S)
Ri = 3
while abs(R-S+2*A[Ri]) < Rdiff:
    R += A[Ri]
    S -= A[Ri]
    Ri += 1
    Rdiff = abs(R-S)
 
def diff(x):
    x.sort()
    return x[-1] - x[0]

ans = diff([P,Q,R,S])
for i in range(3, N-1):
    Q += A[i-1]
    R -= A[i-1]
    Ldiff = abs(P-Q)
    Rdiff = abs(R-S)
    while abs(P-Q+2*A[Li]) < Ldiff:
        P += A[Li]
        Q -= A[Li]
        Li += 1
        Ldiff = abs(P-Q)
    while abs(R-S+2*A[Ri]) < Rdiff:
        R += A[Ri]
        S -= A[Ri]
        Ri += 1
        Rdiff = abs(R-S)
    ans = min(ans, diff([P,Q,R,S]))

print(ans)

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
ren=[0]*n
ren[0]= A[0]
for i in range(n-1):
    ren[i+1]= ren[i]+ A[i+1]
import bisect as bi
ans=float("inf")
for cen in range(1, n-2):
    maru= ren[cen]
    a=ren[bi.bisect(ren, maru//2)-1]
    if a==ren[-1]: a=float("inf")
    b=maru-a
    c=ren[bi.bisect(ren, maru//2)]
    if c==maru: c=float("inf")
    d=maru-c
    
    e=ren[bi.bisect(ren,(maru+ren[-1])//2)-1]-maru 
    if e==0: e= float("inf")
    f=ren[-1]-e-maru
    g=ren[bi.bisect(ren,(maru+ren[-1])//2)]-maru
    if g==ren[-1]-maru: g=float("INF")
    h=ren[-1]-g-maru

    q=[max(a,b,e,f)-min(a,b,e,f), max(a,b,g,h)-min(a,b,g,h), max(c,d,e,f)-min(c,d,e,f), max(c,d,g,h)-min(c,d,g,h)]
    ans= min(ans, min(q))
    
    
    
    
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())
from itertools import accumulate
from bisect import bisect_right
cum = list(accumulate(As))

ans = 10**18
for i in range(1, N-2):
    c = cum[i]
    l_target = c/2
    r_target = (cum[-1]+c)/2
    l_idx = bisect_right(cum, l_target)
    r_idx = bisect_right(cum, r_target)
    if abs(l_target-cum[l_idx])<=abs(l_target-cum[l_idx-1]):
        first = cum[l_idx]
    else:
        first = cum[l_idx-1]
    second = c-first
    if abs(r_target-cum[r_idx])<=abs(r_target-cum[r_idx-1]):
        third = cum[r_idx]-c
        forth = cum[-1]-cum[r_idx]
    else:
        third = cum[r_idx-1]-c
        forth = cum[-1]-cum[r_idx-1]
    lis = [first, second, third, forth]
    ans = min(ans, max(lis)-min(lis))
print(ans)

Solution (Python):
def left(i):
    s=cum[i]
    l,r=-1,i
    while(r-l>1):
        mid=(l+r)//2
        if cum[mid]>s/2:
            r=mid
        else:
            l=mid
    a,b=cum[r],cum[i]-cum[r]
    c,d=cum[l],cum[i]-cum[l]

    if (abs(b-a)<abs(c-d)):
        return a,b
    else:
        return c,d
def right(i):
    s=cum[N]-cum[i]
    l,r=i-1,N+1
    while(r-l>1):
        mid=(l+r)//2
        if cum[mid]-cum[i]>s/2:
            r=mid
        else:
            l=mid
    a,b=cum[r]-cum[i],cum[N]-cum[r]
    c,d=cum[l]-cum[i],cum[N]-cum[l]

    if (abs(b-a)<abs(c-d)):
        return a,b
    else:
        return c,d
        
N=int(input())
A=list(map(int,input().split()))
cum=[0]*(N+1)
for i in range(N):
    cum[i+1]=cum[i]+A[i]
ans=10**30
for i in range(2,N-1):
    a,b=left(i)
    c,d=right(i)
    ans=min(ans,max([a,b,c,d])-min([a,b,c,d]))
print(ans)

Solution (Python):
from itertools import groupby, accumulate, product, permutations, combinations
from bisect import *
def calc(p,q):
  ind = bisect_right(cum,(cum[q]+cum[p])/2)
  M = cum[ind]-cum[p]
  if ind>0:
    M = min(M,cum[q]-cum[ind-1])
  m = cum[q]-cum[p] - M
  return M, m
ans = float('inf')
N = int(input())
A = list(map(int, input().split()))
cum = [0]+list(accumulate(A))
for i in range(2,N-1):
  lis = [*calc(0,i),*calc(i,N)]
  ans = min(ans,max(lis)-min(lis))
print(ans)

Solution (Python):
from itertools import groupby, accumulate, product, permutations, combinations
from bisect import *
def solve():
  ans = float('inf')
  N = int(input())
  A = list(map(int, input().split()))
  cum = list(accumulate(A))
  for i in range(1,N-2):
    mae = cum[i]
    usiro = cum[-1]-cum[i]
    ind = bisect_right(cum,mae/2)
    mae_max = min(cum[ind],mae-cum[ind-1])
    if ind==0:
      mae_max = cum[ind]
    mae_min = mae - mae_max
    ind2 = bisect_right(cum,usiro/2+cum[i])
    usiro_max = min(cum[ind2]-cum[i],cum[-1]-cum[ind2-1])
    if ind2==i+1:
      usiro_max = cum[ind2]-cum[i]
    usiro_min = usiro - usiro_max
    lis = [mae_max,mae_min,usiro_max,usiro_min]
    ans = min(ans,max(lis)-min(lis))
  return ans
print(solve())

Solution (Python):
def solution(a,b,c,d):
  return(max(a,max(b,max(c,d)))-min(a,min(b,min(c,d))))
n=int(input())
a=list(map(int,input().split()))
tot=sum(a)
pointer1=1
p=a[0]
q=a[1]
pointer2=0
s=tot-p-q
r=0
pointer2=2
while r+a[pointer2]<s-a[pointer2]:
  r+=a[pointer2]
  s-=a[pointer2]
  pointer2+=1
ans=solution(p,q,r,s)
ans=min(ans,solution(p,q,r+a[pointer2],s-a[pointer2]))
for i in range(2,n-1):
  q+=a[i]
  r-=a[i]
  while p+a[pointer1]<q-a[pointer1]:
    p+=a[pointer1]
    q-=a[pointer1]
    pointer1+=1
  while r+a[pointer2]<s-a[pointer2]:
    r+=a[pointer2]
    s-=a[pointer2]
    pointer2+=1
  ans=min(ans,solution(p,q,r,s))
  ans=min(ans,solution(p+a[pointer1],q-a[pointer1],r,s))
  ans=min(ans,solution(p+a[pointer1],q-a[pointer1],r+a[pointer2],s-a[pointer2]))
  ans=min(ans,solution(p,q,r+a[pointer2],s-a[pointer2]))
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 + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]

res = sum(a)
for m in range(1, N - 1):
  lsm = cs[m]
  rsm = cs[-1] - cs[m]
  l = bl(cs, lsm / 2)
  l -= l == m
  for i in range(l - 1, l + 2):
    if i == 0: continue
    if i == m: break
    if abs(cs[l] - (cs[m] - cs[l])) > abs(cs[i] - (cs[m] - cs[i])): l = i
  r = bl(cs, rsm // 2 + lsm)
  r -= r == N
  for i in range(r - 1, r + 2):
    if i == m: continue
    if i == N: break
    if abs(cs[-1] - cs[r] - (cs[r] - cs[m])) > abs(cs[-1] - cs[i] - (cs[i] - cs[m])): r = i
  mx = max(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r])
  mn = min(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r])
  res = min(res, mx - mn)
  
print(res)

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)





DBG_TEST_AVL = False
AVL_INF = 10**16

class Node(object):

    def __init__(self, data):
        self.data = data
        self.left_child = None
        self.right_child = None
        self.height = 0


class AVL(object):

    def __init__(self,multi=False):
        self.root = None
        self.multi_mode = multi

    def get_height(self, node):
        if not node:
            return -1
        return node.height

    def get_balance(self, node):
        '''
        返り値が1より大きい場合、左の部分木が重い　→　右回転
        返り値が-1より小さい場合、右の部分木が重い　→　左回転
        '''
        if not node:
            return 0
        return self.get_height(node.left_child) - self.get_height(node.right_child)

    def rotate_right(self, node):
        temp_left_child = node.left_child
        temp_left_right_child = temp_left_child.right_child

        temp_left_child.right_child = node
        node.left_child = temp_left_right_child

        node.height = max(self.get_height(node.left_child), self.get_height(node.right_child)) + 1
        temp_left_child.height = max(self.get_height(temp_left_child.left_child), self.get_height(temp_left_child.right_child)) + 1

        return temp_left_child

    def rotate_left(self, node):
        temp_right_child = node.right_child
        temp_right_left_child = temp_right_child.left_child

        temp_right_child.left_child = node
        node.right_child = temp_right_left_child

        node.height = max(self.get_height(node.left_child), self.get_height(node.right_child)) + 1
        temp_right_child.height = max(self.get_height(temp_right_child.left_child), self.get_height(temp_right_child.right_child)) + 1

        return temp_right_child

    def insert(self, data):
        self.root = self._insert(data, self.root)

    def _insert(self, data, node):
        if not node:
            return Node(data)

        if data < node.data:
            node.left_child = self._insert(data, node.left_child)
        else:
            if not self.multi_mode and data==node.data:
                return node
            node.right_child = self._insert(data, node.right_child)

        node.height = max(self.get_height(node.left_child), self.get_height(node.right_child)) + 1
        return self.settle_unbalance(data, node)

    def settle_unbalance(self, data, node):

        balance = self.get_balance(node)

        
        
        
        if balance > 1 and data < node.left_child.data:
            return self.rotate_right(node)

        
        
        
        if balance < -1 and data > node.right_child.data:
            return self.rotate_left(node)

        
        
        
        if balance > 1 and data > node.left_child.data:
            node.left_child = self.rotate_left(node.left_child)
            return self.rotate_right(node)

        
        
        
        if balance < -1 and data < node.right_child.data:
            node.right_child = self.rotate_right(node.right_child)
            return self.rotate_left(node)

        return node

    def traverse_inorder(self):
        if self.root:
            self._traverse_inorder(self.root)
            
            print()
        else:
            print('木は空です。')

    def _traverse_inorder(self, node):
        if node.left_child:
            self._traverse_inorder(node.left_child)

        print(node.data, end=' ')

        if node.right_child:
            self._traverse_inorder(node.right_child)

    def remove(self, data):
        if self.root:
            self.root = self._remove(data, self.root)

    def _remove(self, data, node):
        
        if not node:
            return node

        if data < node.data:
            node.left_child = self._remove(data, node.left_child)
        elif data > node.data:
            node.right_child = self._remove(data, node.right_child)
        else:
            
            if not node.right_child and not node.left_child:
                del node
                
                return None

            
            if not node.right_child:
                temp = node.left_child
                del node
                
                return temp

            
            if not node.left_child:
                temp = node.right_child
                del node
                return temp
            
            
            def _get_max_node(node):
                if node.right_child:
                    return _get_max_node(node.right_child)
                return node
            temp = _get_max_node(node.left_child)
            node.data = temp.data
            
            node.left_child = self._remove(temp.data, node.left_child)

        node.height = max(self.get_height(node.left_child), self.get_height(node.right_child)) + 1
        balance = self.get_balance(node)

        if balance > 1 and self.get_balance(node.left_child) >= 0:
            print('left-left heavy')
            return self.rotate_right(node)

        if balance < -1 and self.get_balance(node.left_child) <= 0:
            print('right-right heavy')
            return self.rotate_left(node)

        if balance > 1 and self.get_balance(node.left_child) < 0:
            print('left-right heavy')
            node.left_child = self.rotate_left(node.left_child)
            return self.rotate_right(node)

        if balance < -1 and self.get_balance(node.left_child) > 0:
            node.right_child = self.rotate_right(node.right_child)
            print('right-left heavy')
            return self.rotate_left(node)

        return node

    def find_bounds(self,d):
        return self._find(self.root,d,-AVL_INF,AVL_INF)

    def _find(self,nd,d,l,r):
        if not nd:
            return (l,r)
        elif nd.data==d:
            return (d,d)
        elif nd.data<d:
            return self._find(nd.right_child,d,max(l,nd.data),r)
        else:
            return self._find(nd.left_child,d,l,min(r,nd.data))


def test_avl_alone():
    avl = AVL()

    avl.insert(2)
    avl.insert(4)
    avl.insert(8)
    avl.insert(16)
    avl.insert(16)
    avl.insert(32)
    avl.insert(64)
    avl.insert(128)
    avl.insert(256)
    avl.insert(512)
    
    avl.traverse_inorder()
    avl.remove(2)
    
    avl.remove(4)
    print(avl.find_bounds(3))
    avl.remove(512)
    avl.remove(256)
    
    avl.remove(64)
    print(avl.find_bounds(37))
    print(avl.find_bounds(128))
    avl.remove(128)
    
    avl.traverse_inorder()
    
    print('height', avl.get_height(avl.root))

if DBG_TEST_AVL:
    test_avl_alone()




n = inn()
a = inl()
mnl = [0]*n
mnr = [0]*n
mxl = [0]*n
mxr = [0]*n

lacc = a[0]
av = AVL()
av.insert(lacc)
for i in range(1,n-2):
    lacc += a[i]
    r1 = av.find_bounds(lacc//2)
    r2 = av.find_bounds(lacc//2+1)
    
    
    mnl[i+1] = max([ \
     min(r1[0],lacc-r1[0]),
     min(r1[1],lacc-r1[1]),
     min(r2[0],lacc-r2[0]),
     min(r2[1],lacc-r2[1]) ])
    mxl[i+1] = min([ \
     max(r1[0],lacc-r1[0]),
     max(r1[1],lacc-r1[1]),
     max(r2[0],lacc-r2[0]),
     max(r2[1],lacc-r2[1]) ])
    av.insert(lacc)

racc = a[n-1]
av = AVL()
av.insert(racc)
for i in range(n-2,1,-1):
    racc += a[i]
    r1 = av.find_bounds(racc//2)
    r2 = av.find_bounds(racc//2+1)
    mnr[i] = max([ \
     min(r1[0],racc-r1[0]),
     min(r1[1],racc-r1[1]),
     min(r2[0],racc-r2[0]),
     min(r2[1],racc-r2[1]) ])
    mxr[i] = min([ \
     max(r1[0],racc-r1[0]),
     max(r1[1],racc-r1[1]),
     max(r2[0],racc-r2[0]),
     max(r2[1],racc-r2[1]) ])
    av.insert(racc)

print(min( \
 [max(mxr[i],mxl[i])-min(mnr[i],mnl[i]) for i in range(2,n-1)]))

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)

import bisect
n = inn()
a = inl()
lacc = [0]*(n+1)
for i in range(n):
    lacc[i+1] = lacc[i]+a[i]
ans = BIG
for i in range(2,n-1):
    j = bisect.bisect_left(lacc,lacc[i]//2+1)
    j = min(j,i-1)
    k = bisect.bisect_left(lacc,(lacc[n]+lacc[i])//2+1)
    k = min(k,n-1)
    for dj in range(2):
        jj = j-dj
        if jj<=0:
            continue
        for dk in range(2):
            kk = k-dk
            if kk<=i:
                continue
            v = []
            v.append(lacc[jj])
            v.append(lacc[i]-lacc[jj])
            v.append(lacc[kk]-lacc[i])
            v.append(lacc[n]-lacc[kk])
            ans = min(ans,max(v)-min(v))
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 = list(map(int, input().split()))

s1 = s2 = 0
b = 0
left = []
for i in range(n):
    s2 += a[i]
    while s1 + a[b] < s2 - a[b]:
        s1 += a[b]
        s2 -= a[b]
        b += 1
    left.append(((s1, s2), (s1 + a[b], s2 - a[b])))
s1 = s2 = 0
b = n
right = []
for i in range(n-1, -1, -1):
    s1 += a[i]
    while s2 + a[b-1] < s1 - a[b-1]:
        s2 += a[b-1]
        s1 -= a[b-1]
        b -= 1
    right.append(((s1, s2), (s1 - a[b-1], s2 + a[b-1])))
right.reverse()
ans = 1001001001001001001
for p1, p2 in zip(left, right[1:]):
    for s1, s2 in p1:
        for t1, t2 in p2:
            ans = min(ans, max(s1, s2, t1, t2) - min(s1, s2, t1, t2))
print(ans)

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    sa = [0,a[0]]
    for i in a[1::]:
        sa.append(sa[-1]+i)

    mi = 10**18
    ll = 1
    rr = 3
    for ci in range(2,n-1):
        ls = sa[ci]
        rs = sa[-1]
        nms = []
        pld = 10**18
        for l in range(ll,ci):
            al = sa[l]
            d = abs(ls-2*al)
            if pld > d:
                pld = d
                sl = (al,ls-al)
                if l == ci:
                    ll = ci-1
            else:
                ll = l-1
                break
        nms.append(sl[0])
        nms.append(sl[1])
        pld = 10**18
        for r in range(rr,n):
            ar = sa[r]
            d = abs(rs+ls-2*ar)
            if pld > d:
                pld = d
                sl = (rs-ar,ar-ls)
                if r == n-1:
                    rr = n-1
            else:
                rr = r-1
                break
        nms.append(sl[0])
        nms.append(sl[1])
        d = max(nms)-min(nms)
        if mi > d:
            mi = d

    print(mi)


    return None

if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left

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

def f(pos1, pos2):
    v1 = ac[pos1]
    v2 = ac[i]-ac[pos1]
    v3 = ac[pos2]-ac[i]
    v4 = ac[N]-ac[pos2]
    return max(v1,v2,v3,v4)-min(v1,v2,v3,v4)

ans = 10**20
for i in range(2, N):
    pos1 = bisect_left(ac, ac[i]//2, 1, i-1)
    pos2 = bisect_left(ac, (ac[i]+ac[N])//2, i+1, N)
    ans = min(ans, f(pos1, pos2), f(pos1-1, pos2), f(pos1, pos2-1), f(pos1-1, pos2-1))

print(ans)

Solution (Python):


def ruiseki(n,array):
    res = [0]*(n)
    for i in range(n):
        res[i] = res[i-1] + array[i]
    return res

n = int(input())
A = list(map(int,input().split()))
sa = ruiseki(n,A)

ans = 10**15
left_c = 0
right_c = 2
for center in range(1,n-1):
    while left_c+1 < center:
        if abs(sa[center]-2*sa[left_c]) > abs(sa[center]-2*sa[left_c+1]):
            left_c+=1
        else:
            break

    right_c = max(right_c, center+1)
    while right_c+1 < n-1:
        if abs(sa[-1] + sa[center] - 2*sa[right_c]) > abs(sa[-1] + sa[center] - 2*sa[right_c+1]):
            right_c+=1
        else:
            break
    
    x = max(sa[left_c], sa[center]-sa[left_c], sa[right_c]-sa[center], sa[-1]-sa[right_c])
    y = min(sa[left_c], sa[center]-sa[left_c], sa[right_c]-sa[center], sa[-1]-sa[right_c])
    ans = min(ans, x-y)

print(ans)

Solution (Python):
from itertools import accumulate
n=int(input())
l=[0]+list(accumulate(list(map(int,input().split()))))
ans=float("INf")
lnow=1
rnow=3
for center in range(2,n-1):

    laim=l[center]//2
    while lnow+1<center and l[lnow+1]<laim:lnow+=1
    if rnow<=center:rnow=center+1
    raim=(l[-1]-l[center])//2
    while rnow+1<n and l[rnow+1]-l[center]<raim:rnow+=1
    for i,j in ((0,0),(1,0),(1,1),(0,1)):
        if lnow+i<center and rnow+j<n:
            a=(l[lnow+i],l[center]-l[lnow+i],l[rnow+j]-l[center],l[-1]-l[rnow+j])
            ans=min(ans,max(a)-min(a))
print(ans)

Solution (Python):
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]
dij=[(1,0),(0,1),(-1,0),(0,-1)]

def main():
    n=II()
    aa=LI()

    pre=[0]*(n+1)
    for i in range(n):pre[i+1]+=pre[i]+aa[i]

    ll=[[0]*2 for _ in range(n)]
    rr=[[0]*2 for _ in range(n)]
    j=1
    for i in range(2,n-1):
        while j<i-1 and pre[i]-pre[j]*2>0:j+=1
        if pre[i]-pre[j-1]*2<-pre[i]+pre[j]*2:j-=1
        ll[i][0]=min(pre[i]-pre[j],pre[j])
        ll[i][1]=max(pre[i]-pre[j],pre[j])
    j=n-1
    for i in range(n-2,1,-1):
        while j>i+1 and pre[n]+pre[i]-pre[j]*2<0:j-=1
        if -pre[n]-pre[i]+pre[j+1]*2<pre[n]+pre[i]-pre[j]*2:j+=1
        rr[i][0]=min(pre[n]-pre[j],pre[j]-pre[i])
        rr[i][1]=max(pre[n]-pre[j],pre[j]-pre[i])
    

    ans=10**16
    for i in range(2,n-1):
        mn=min(ll[i][0],rr[i][0])
        mx=max(ll[i][1],rr[i][1])
        cur=mx-mn
        if cur<ans:ans=cur
    print(ans)

main()

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
from itertools import accumulate
C=[0]+list(accumulate(A))
l,r=1,3
x=10**16
for m in range(2,N-1):
    a,b,c,d=C[l],C[m]-C[l],C[r]-C[m],C[N]-C[r]
    while l<m-1 and abs(C[m]-C[l+1]*2)<abs(a-b):
        l+=1
        a,b=C[l],C[m]-C[l]
    while r<N-1 and abs(C[N]-C[r+1]*2+C[m])<abs(c-d):
        r+=1
        c,d=C[r]-C[m],C[N]-C[r]
    x=min(x,max(a,b,c,d)-min(a,b,c,d))
print(x)

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

Solution (Python):
import bisect

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

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

ans = 1e18
for i in range(2, N-1):
    
    left_sum = S[i-1]
    m = bisect.bisect(S, left_sum/2)

    L = [S[m], left_sum-S[m]]

    if m != 0:
        L2 = [S[m-1], left_sum - S[m-1]]
        if(abs(L[0]-L[1]) > abs(L2[0]-L2[1])): L = L2

    
    m = bisect.bisect(S, (S[-1]+left_sum)/2)
    R = [S[m]-left_sum, S[-1]-S[m]]

    if m != i:
        R2 = [S[m-1]-left_sum, S[-1]-S[m-1]]
        if(abs(R[0]-R[1]) > abs(R2[0]-R2[1])): R = R2


    ans = min(ans, max(L[0],L[1],R[0],R[1]) - min(L[0],L[1],R[0],R[1]))

print(ans)

Solution (Python):
N,*A = map(int, open(0).read().split())
a = A[0]
b = A[1]
c = A[2]
d = sum(A[3:])
x = 0
m = c
n = d
df2 = max(m,n)-min(m,n)
y = 2
for i in range(3,N-1):
  m += A[i]
  n -= A[i]
  if df2>max(m,n)-min(m,n):
    df2 = max(m,n)-min(m,n)
    c,d = m,n
    y = i
ans = max(a,b,c,d)-min(a,b,c,d)
for i in range(2,N-2):
  b += A[i]
  c -= A[i]
  df1 = max(a,b)-min(a,b)
  df2 = max(c,d)-min(c,d)
  while True:
    na = a+A[x+1]
    nb = b-A[x+1]
    if df1<max(na,nb)-min(na,nb):
      break
    df1 = max(na,nb)-min(na,nb)
    a,b = na,nb
    x += 1
  while True:
    nc = c+A[y+1]
    nd = d-A[y+1]
    if df2<max(nc,nd)-min(nc,nd):
      break
    df2 = max(nc,nd)-min(nc,nd)
    c,d = nc,nd
    y += 1
  ans = min(ans,max(a,b,c,d)-min(a,b,c,d))
print(ans)