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:
N=int(input())
alist=list(map(int,input().split()))

def bs_left(mid,mp):
  sum2=abs(2*slist[mid]-slist[mp])
  if mid==0:
    sum1=sum2
  else:
    sum1=abs(2*slist[mid-1]-slist[mp])
  if mid==mp:
    sum3=sum2
  else:
    sum3=abs(2*slist[mid+1]-slist[mp])

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    

def bs_right(mid,mp):
  sum2=abs(2*(slist[mid]-slist[mp])-(slist[-1]-slist[mp]))
  if mid==0:
    sum1=sum2
  else:
    sum1=abs(2*(slist[mid-1]-slist[mp])-(slist[-1]-slist[mp]))
  if mid==mp:
    sum3=sum2
  else:
    sum3=abs(2*(slist[mid+1]-slist[mp])-(slist[-1]-slist[mp]))

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    
  
slist=[]
asum=0
for a in alist:
  asum+=a
  slist.append(asum)
#print(alist)
#print(slist)

dic_lp,dic_rp={},{}
for mp in range(1,N-2):  
  #lp
  l,r=0,mp-1
  while(l<=r):
    mid=(l+r)//2
    ret=bs_left(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_lp[mp]=mid
      #print(mp,mid)
      break
  
  #rp
  l,r=mp+1,N-2
  while(l<=r):
    mid=(l+r)//2
    ret=bs_right(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_rp[mp]=mid
      #print(mp,mid)
      break
    
min_diff=10**9
for mp in range(1,N-2):
  lp=dic_lp[mp]
  rp=dic_rp[mp]
  
  sum1=slist[lp]
  sum2=slist[mp]-slist[lp]
  sum3=slist[rp]-slist[mp]
  sum4=slist[-1]-slist[rp]
  #print(sum1,sum2,sum3,sum4)
  
  sum_list=[sum1,sum2,sum3,sum4]
  sum_list.sort()
  diff=sum_list[-1]-sum_list[0]
  #print(lp,mp,rp,diff)
  if diff<min_diff:
    min_diff=diff    
  
print(min_diff)

Submission status: Accepted

Solution code:
N=int(input())
alist=list(map(int,input().split()))

def bs_left(mid,mp):
  sum2=abs(2*slist[mid]-slist[mp])
  if mid==0:
    sum1=sum2
  else:
    sum1=abs(2*slist[mid-1]-slist[mp])
  if mid==mp:
    sum3=sum2
  else:
    sum3=abs(2*slist[mid+1]-slist[mp])

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    

def bs_right(mid,mp):
  sum2=abs(2*(slist[mid]-slist[mp])-(slist[-1]-slist[mp]))
  if mid==0:
    sum1=sum2
  else:
    sum1=abs(2*(slist[mid-1]-slist[mp])-(slist[-1]-slist[mp]))
  if mid==mp:
    sum3=sum2
  else:
    sum3=abs(2*(slist[mid+1]-slist[mp])-(slist[-1]-slist[mp]))

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    
  
slist=[]
asum=0
for a in alist:
  asum+=a
  slist.append(asum)
#print(alist)
#print(slist)

dic_lp,dic_rp={},{}
for mp in range(1,N-2):  
  #lp
  l,r=0,mp
  while(l<=r):
    mid=(l+r)//2
    ret=bs_left(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_lp[mp]=mid
      #print(mp,mid)
      break
  
  #rp
  l,r=mp+1,N-2
  while(l<=r):
    mid=(l+r)//2
    ret=bs_right(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_rp[mp]=mid
      #print(mp,mid)
      break
    
min_diff=10**9
for mp in range(1,N-2):
  lp=dic_lp[mp]
  rp=dic_rp[mp]
  
  sum1=slist[lp]
  sum2=slist[mp]-slist[lp]
  sum3=slist[rp]-slist[mp]
  sum4=slist[-1]-slist[rp]
  #print(sum1,sum2,sum3,sum4)
  
  sum_list=[sum1,sum2,sum3,sum4]
  sum_list.sort()
  diff=sum_list[-1]-sum_list[0]
  #print(lp,mp,rp,diff)
  if diff<min_diff:
    min_diff=diff    
  
print(min_diff)

Submission status: Accepted

Solution code:
N=int(input())
alist=list(map(int,input().split()))

slist=[]
asum=0
for a in alist:
  asum+=a
  slist.append(asum)
#print(alist)
#print(slist)

dic_lp,dic_rp={},{}
lp,rp=0,2
for mp in range(1,N-2):
  #p1
  mindiff=slist[mp]
  while(lp<mp+1):
    sum1=slist[lp]
    sum2=slist[mp]-slist[lp]
    
    diff=abs(sum1-sum2)
    if mindiff>diff:
      lp+=1
      mindiff=diff
    else:
      lp-=1
      dic_lp[mp]=lp
      #print(mp,lp)
      break
    
  rp=max(rp,mp+1)
  mindiff=slist[-1]-slist[mp]
  while(rp<N):
    sum1=slist[-1]-slist[rp]
    sum2=slist[rp]-slist[mp]
    
    diff=abs(sum1-sum2)
    if mindiff>diff:
      rp+=1
      mindiff=diff
    else:
      rp-=1
      dic_rp[mp]=rp
      #print(mp,rp)
      break
    
min_diff=10**9
for mp in range(1,N-2):
  lp=dic_lp[mp]
  rp=dic_rp[mp]
  
  sum1=slist[lp]
  sum2=slist[mp]-slist[lp]
  sum3=slist[rp]-slist[mp]
  sum4=slist[-1]-slist[rp]
  #print(sum1,sum2,sum3,sum4)
  
  sum_list=[sum1,sum2,sum3,sum4]
  sum_list.sort()
  diff=sum_list[-1]-sum_list[0]
  #print(lp,mp,rp,diff)
  if diff<min_diff:
    min_diff=diff
    #print(min_diff)
  
print(min_diff)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

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

    k1=start
    k2=end

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

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

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


print(main())

Submission status: Accepted

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

Submission status: Accepted

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

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]

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
#102_D
N = int(input())
A = [int(i) for i in input().split()]
s = 0
AS = []
for i in range(N):
    s += A[i]
    AS.append(s)
#尺取り法
Ans = AS[N-1]+1
L = 0
R = 2
for Mid in range(1, N-2):
    Sum_L = AS[Mid]
    Sum_R = AS[N-1]-Sum_L
    while abs((Sum_L - AS[L]) - AS[L]) > abs((Sum_L - AS[L+1]) - AS[L+1]):
        L += 1

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

Submission status: Accepted

Solution code:
# import math
# N = int(input())
# A_list = [int(i) for i in input().split()]


# def divide_list(num_list):
#   left = 0
#   right = len(num_list)
#   minimum = 10**9

#   while True:
#     c = (left+right)//2
#     left_sum = sum(num_list[:c])
#     right_sum = sum(num_list[c:])
#     diff = abs(left_sum - right_sum)

#     if minimum > diff:
#       minimum = diff
#       minimum_left = left
#       minimum_right = right
    
#     if left_sum > right_sum:
#       right = c
#     elif left_sum < right_sum:
#       left = c
#     else:
#       return num_list[:c], num_list[c:]

#     if c==left or c==right:
#       c = (minimum_left+minimum_right)//2
#       return num_list[:c], num_list[c:]

# tmp1_list, tmp2_list = divide_list(A_list)
# print(tmp1_list, tmp2_list)
# tmp11_list, tmp12_list = divide_list(tmp1_list)
# tmp21_list, tmp22_list = divide_list(tmp2_list)
# print(tmp11_list, tmp12_list, tmp21_list, tmp22_list)

# ans_list = [sum(tmp11_list), sum(tmp12_list), sum(tmp21_list), sum(tmp22_list)]
# ans_list.sort()

# print(ans_list[-1] - ans_list[0])


#102_D
N = int(input())
A = list(map(int, input().split()))
s = 0
AS = []
for i in range(N):
    s += A[i]
    AS.append(s)
#尺取り法
Ans = AS[N-1]+1
L = 0
R = 2
for Mid in range(1, N-2):
    Sum_L = AS[Mid]
    Sum_R = AS[N-1]-Sum_L
    while abs(Sum_L-2*AS[L]) > abs(Sum_L-2*AS[L+1]):
        L += 1

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

Submission status: Accepted

Solution code:
#102_D
N=int(input())
A=list(map(int,input().split()))
s=0
AS=[]
for i in range(N):
    s+=A[i]
    AS.append(s)
#尺取り法
Ans=AS[N-1]+1
L=0
R=2
for Mid in range(1,N-2):
    Sum_L=AS[Mid]
    Sum_R=AS[N-1]-Sum_L
    while abs(Sum_L-2*AS[L])>abs(Sum_L-2*AS[L+1]):
        L+=1
    
    while R<=N-3 and abs(AS[N-1]-2*AS[R]+AS[Mid])>abs(AS[N-1]-2*AS[R+1]+AS[Mid]):
        R+=1
    P=AS[L]
    Q=AS[Mid]-AS[L]
    S=AS[R]-AS[Mid]
    T=AS[N-1]-AS[R]
    #print(Mid,L,R,abs(max(P,Q,S,T)-min(P,Q,S,T)))
    Ans=min(Ans,abs(max(P,Q,S,T)-min(P,Q,S,T)))
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]
    
ans=10**20

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

th_pq=1
th_rs=3

for i in range(2,N-1):#全体をi番目で二分割
    sq+=A[i-1]
    sr-=A[i-1]
    while th_pq!=i-1:#pqの境界を移動させる
        diff_pq=abs(sp-sq)
        sp2=sp+A[th_pq]
        sq2=sq-A[th_pq]
        diff_pq2=abs(sp2-sq2)
        if diff_pq2 <= diff_pq:
            sp=sp2
            sq=sq2
            th_pq+=1
        else:
            break
        
    while th_rs!=N-1:
        diff_rs=abs(sr-ss)
        sr2=sr+A[th_rs]
        ss2=ss-A[th_rs]
        diff_rs2=abs(sr2-ss2)
        if diff_rs2 <= diff_rs:
            sr=sr2
            ss=ss2
            th_rs+=1
        else:
            break
    temp=max(sp,sr,sq,ss) - min(sp,sq,sr,ss)
    ans=min(ans,temp)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from itertools import accumulate
from bisect import bisect_left

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

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from itertools import accumulate
from bisect import bisect_left

INF = 10 ** 18

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

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

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

Submission status: Accepted

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

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

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

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


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

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

    def get_cumsum(a, b):
        # get cumsum from [a, b] element
        return cumsum[b+1] - cumsum[a]

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

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

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

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

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

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

    def _separate_opt_sum(l, r):
        # find arr1, arr2 s.t. |arr1 - arr2| = min
        # arr1 = get_cumsum(l, k), arr2 = get_cumsum(k+1, r)
        tot_sum = get_cumsum(l, r)
        m = (l + r) // 2
        m_min = l - 1
        m_max = r + 1
        cur_min_diff = abs(2 * get_cumsum(l, m) - tot_sum)
        cur_min_m = m
        while m_min < m and m < m_max:
            left_sum = get_cumsum(l, m)
            right_sum = tot_sum - left_sum
            cur_diff = abs(left_sum - right_sum)
            if cur_diff < cur_min_diff:
                cur_min_diff = cur_diff
                cur_min_m = m
            if left_sum < right_sum:
                m_min = m
                m = (m + r) // 2
            elif left_sum > right_sum:
                m_max = m
                m = (l + m) // 2
            else:
                break
        l_ans = get_cumsum(l, cur_min_m)
        r_ans = get_cumsum(cur_min_m + 1, r)
        return l_ans, r_ans

    ans = inf
    for sep in range(1, N-2):
        left_S = get_cumsum(0, sep)
        right_S = get_cumsum(sep+1, N-1)
        # import pdb
        # pdb.set_trace()
        p, q = separate_opt_sum(0, sep, 0)
        r, s = separate_opt_sum(sep+1, N-1, left_S)
        
        # print('sep:', sep, ' ', p, q, r, s)
        # print('\tleft_S:', left_S, ' right_S:', right_S)
        ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
    print(ans)
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 解説の方法

from itertools import accumulate

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

acc = list(accumulate(a))

l = 0
r = 2

ans = float('inf')

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
import bisect


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

arev = list(reversed(a))

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

Submission status: Accepted

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

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

# 真ん中の区切りを全通り試す
for iC in range(2, N - 1):
    while P < Q and As[iB] <= Q - P:
        P += As[iB]
        Q -= As[iB]
        iB += 1

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

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

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

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

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

left_i = [None] * N
right_i = [None] * N
l = 1
r = 3
ans = INF
# 真ん中の切る位置を決めたとき、左右それぞれの切る位置も決まる
for i in range(2, N - 1):
    while l + 1 < i and abs(cum[l - 1] * 2 - cum[i - 1]) > abs(cum[l] * 2 - cum[i - 1]):
        l += 1
    while r + 1 < N and abs(cum[r - 1] * 2 - cum[i - 1] - cum[N - 1]) > abs(cum[r] * 2 - cum[i - 1] - cum[N - 1]):
        r += 1

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

Submission status: Accepted

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

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

Submission status: Accepted

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

l = 1
r = 3
cut = []
for i in range(2,N-1):
    Lm = float("inf")
    Rm = float("inf")
    c = [0,i,0]
    for j in range(l,i):
        tmp = abs(B[i]-2*B[j])
        if tmp > Lm:
            c[0] = j-1
            l = j-1
            break
        Lm = tmp
    else:
        c[0] = i-1
        l = i-1
    for k in range(r,N):
        tmp = abs((B[N]-B[k])-(B[k]-B[i]))
        if tmp > Rm:
            c[2] = k-1
            r = k-1
            break
        Rm = tmp
    else:
        c[2] = N-1
        r = N
    cut.append(c)
#print(cut)
ans = float("inf")
for p,q,r in cut:
    P = B[p]
    Q = B[q]-B[p]
    R = B[r]-B[q]
    S = B[N]-B[r]
    ans = min(ans,max(P,Q,R,S)-min(P,Q,R,S))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import *

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

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

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

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

    return ans

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

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
from bisect import bisect_left as bi_l

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

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

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

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

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

    return ans

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