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



Sample input:
5
3 2 4 1 2


Sample output:
2

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
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 # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

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

# # # # AVL class # # # #

# NOTE multi_mode not well tested 2020-08-02

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)

        # balace >1 -> 左の方が重い
        # data < node.left_child.data 左の子より左側にデータが挿入されたので、左の子の左の子の方が重い
        # つまり、left-left heavy　右回転を行う
        if balance > 1 and data < node.left_child.data:
            return self.rotate_right(node)

        # balace > -1 -> 右の方が重い
        # data > node.right_child.data 右の子より右側にデータが挿入されたので、右の子の右の子の方が重い
        # つまり、right-right heavy　左回転を行う
        if balance < -1 and data > node.right_child.data:
            return self.rotate_left(node)

        # balace >1 -> 左の方が重い
        # data > node.left_child.data 左の子より右側にデータが挿入されたので、左の子の右の子の方が重い
        # つまり、left-right heavy　左回転を行い右回転を行う
        if balance > 1 and data > node.left_child.data:
            node.left_child = self.rotate_left(node.left_child)
            return self.rotate_right(node)

        # balace > -1 -> 右の方が重い
        # data < node.right_child.data 右の子より左側にデータが挿入されたので、右の子の左の子の方が重い
        # つまり、right-left heavy　右回転を行い左回転を行う
        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
                # None を返すことで、親ノードの削除子ノードへのポインタを None に変更
                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
            # 削除ノードが左右の子を持つ場合、ここでは、左側のsubtreeの最大のノードを代わりのノードにすることにする。
            #  subtreeの最大のノードを取得するヘルパー関数
            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
            # 左側のsubtreeから削除ノードと入れ替えたノードを削除
            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))

#if __name__ == '__main__':
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)
    # 2 4 8 16 32 64 128 256 512
    avl.traverse_inorder()
    avl.remove(2)
    # right-right heavy
    avl.remove(4)
    print(avl.find_bounds(3))
    avl.remove(512)
    avl.remove(256)
    # left-left heavy
    avl.remove(64)
    print(avl.find_bounds(37))
    print(avl.find_bounds(128))
    avl.remove(128)
    # 8 16 32
    avl.traverse_inorder()
    # height 1
    print('height', avl.get_height(avl.root))

if DBG_TEST_AVL:
    test_avl_alone()

# # # # AVL class end # # # #


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)
    #if min([abs(r1[0]),abs(r1[1]),abs(r2[0]),abs(r2[1])])>10**10:
    #    3/0
    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)]))

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
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 # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

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)

Submission status: Accepted

Solution code:
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が左側の分割、bが右側の分割
    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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# arc 100 D

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])
    #print(ll,rr)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
    # 左側 [0,i)
    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

    # 右側 [i,N)
    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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ARC100D

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 #ca[i] = a0~aiの和
s = 0
for i,num in enumerate(a):
    s += a[i]
    ca[i] = s

diff = [None] * n

s = 0
t = 1
v1 = 0 # a[:s]
v2 = a[0] # sum(a[s:t])
diff[t-1] = (v1,v2)
while t<n:
#     print(t, v1-v2)
    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 # sum(a[s:])
v2 = a[-1] # sum(a[t:s])
diff2[t] = (v1,v2)
while t>=1:
    # print(t, v1, v2)
    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)))

Submission status: Accepted

Solution code:
# ARC100D

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


# import numpy as np
import bisect
n = int(input())
a = list(map(int, input().split()))
# a = np.array(list(map(int, input().split())))
ca = [None] * n #ca[i] = a0~aiの和
s = 0
for i,num in enumerate(a):
    s += a[i]
    ca[i] = s
# ca = a.cumsum()

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])
#     print(p1,p2,nn)
    best = min(best, nn)
print(best)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
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  # 左のリストで2つに切り分けるindex
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)
# 27r

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

Submission status: Accepted

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