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

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

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

R = R[::-1]

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

Submission status: Accepted

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

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

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

# for i in range(1, N + 1):
#     L[i] = min(L[i], L[i - 1])
#     R[i] = min(R[i], R[i - 1])

R = R[::-1]

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

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

mod = 10**9 + 7

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

#################

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

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

N = I()
A = LI()

sumA = sum(A)

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

ans = float('inf')

# 2本目の区切りを i/i+1 の境目とする
# 左右2つの区間は，それぞれ差が最小になるように区切ると最適
for i in range(1,N-2):
    l_sum = bit.sum(i+1)
    r_sum = sumA-l_sum
    p = bit.search(l_sum+r_sum/2)
    if p == i+2:
        r_max = bit.sum(p)-bit.sum(i+1)
        r_min = r_sum-r_max
    elif p == N:
        r_min = bit.sum(p-1)-bit.sum(i+1)
        r_max = r_sum-r_min
    else:
        max1 = bit.sum(p)-bit.sum(i+1)
        min1 = r_sum-max1
        max2 = min1+A[p-1]
        min2 = max1-A[p-1]
        if max1-min1 < max2-min2:
            r_max = max1
            r_min = min1
        else:
            r_max = max2
            r_min = min2

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

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

print(ans)

Submission status: Accepted

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

R = 10**18
for i in range(2, N-1):
    # X0, X1, X2 .. Xi
    # Xj Xj+1 (1<= j <= i-1)
    idx1 = bsearch(1, i-1, lambda j:X[i]//2 < X[j])
    idx2 = bsearch(i+1, N, lambda j:(X[N]-X[i])//2 < (X[j]-X[i]))
#    print(X[idx1], X[i]-X[idx1], X[idx2]-X[i], X[N]-X[idx2])
    if idx1+1 <= i-1:
        if abs(2*X[idx1]-X[i]) > abs(2*X[idx1+1]-X[i]):
            idx1+=1
#    print(1,i,idx2)
    if idx2+1 <= N-1:
        if abs(2*X[idx2]-X[i]-X[N]) > abs(2*X[idx2+1]-X[i]-X[N]):
            idx2+=1
    mx = max([X[idx1], X[i]-X[idx1], X[idx2]-X[i], X[N]-X[idx2]])
    mn = min([X[idx1], X[i]-X[idx1], X[idx2]-X[i], X[N]-X[idx2]])
#    print(X[i]-X[idx1], X[idx1], X[idx2]-X[i])
#    print(idx1, i, idx2)
#    print(mx-mn)
    R = min(R, mx-mn)
print(R)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
a=list(map(int,input().split()))
l=[0]
for i in range(n):
    l.append(l[-1]+a[i])
ans=10**20
for i in range(n-3):
    m=i+2
    f=bisect.bisect_left(l,l[m]//2)
    if f==m:
        f-=1
    f-=1
    if abs(l[m]-2*l[f])>abs(l[m]-2*l[f+1]):
        z=[l[m]-l[f+1],l[f+1]]
    else:
        z=[l[m]-l[f],l[f]]
    b=bisect.bisect_left(l,(l[-1]+l[m])//2)
    if b==n+1:
        b-=1
    if b==n:
        b-=1
    b-=1
    if abs((l[-1]-l[b])-(l[b]-l[m]))>abs((l[-1]-l[b+1])-(l[b+1]-l[m])):
        z.append(l[-1]-l[b+1])
        z.append(l[b+1]-l[m])
    else:
        z.append(l[-1]-l[b])
        z.append(l[b]-l[m])
    ans=min(ans,max(z)-min(z))
    #print(z)
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:
# 写経AC

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

# P,Q,R,S に対応
score = [A[0], A[1], A[2], sum(A[3:])]

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


""" 尺取り法 """
# 真ん中
for mid in range(2, N-1):
    # 左側
    while left < mid and abs(score[0] - score[1]) > abs((score[0] + A[left]) - (score[1] - A[left])):
        score[0] += A[left]
        score[1] -= A[left]
        left += 1
    # 右側
    while right < N and abs(score[2] - score[3]) > abs((score[2] + A[right]) - (score[3] - A[right])):
        score[2] += A[right]
        score[3] -= A[right]
        right += 1

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

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

print(ans)

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




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

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


def main(i,t,last):

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

    # [0,i), [i,j), [j,k), [k, n)
    tot = sum(a)
    ret = tot

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

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

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

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

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

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

N = int(input())
n = N

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

s = [0]
ans = float("inf")

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

for i in range(N-3):

    i += 1

    l = 0
    r = i+1

    while r-l != 1:

        m = (l+r) // 2
        if s[m] <= s[i+1] / 2:
            l = m
        else:
            r = m

    if l == 0:
        b = s[1]
        c = s[i+1] - b
    elif r == i+1:
        b = s[i]
        c = s[i+1]-s[i]
    elif abs(s[l] - s[i+1]/2) < abs(s[r] - s[i+1]/2):
        b = s[l]
        c = s[i+1]-s[l]
    else:
        b = s[r]
        c = s[i+1]-s[r]

    l = i+1
    r = n

    while r-l != 1:

        m = (l+r) // 2
        if s[m]-s[i+1] <= (s[n]-s[i+1])/2:
            l = m
        else:
            r = m

    if l == i+1:
        d = s[i+2]-s[i+1]
        e = s[n] - s[i+2]
    elif r == n:
        d = s[n-1]-s[i+1]
        e = s[n]-s[n-1]
    elif abs((s[l]-s[i+1]) - (s[n]-s[i+1])/2) < abs((s[r]-s[i+1]) - (s[n]-s[i+1])/2):
        d = s[l]-s[i+1]
        e = s[n]-s[l]
    else:
        d = s[r]-s[i+1]
        e = s[n]-s[r]

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

print (ans)

Submission status: Accepted

Solution code:
def examC():
    N = I()
    A = LI()
    Ad = [0]*N
    for i in range(N):
        Ad[i] = A[i]-(i+1)
    Ad.sort()
#    print(Ad)
    b = Ad[N//2]
    ans = 0
    for a in Ad:
        ans +=abs(a-b)
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    cumA = [0]*N
    cumA[0] = A[0]
    for i in range(N-1):
        cumA[i+1] = cumA[i]+A[i+1]
    ans = inf
#    print(cumA)
    for i in range(1,N-1):
        curcd = (cumA[i]+1)//2
        cd = bisect.bisect_right(cumA,curcd)
#        print(curcd,cd)
        C = cumA[cd]; D = cumA[i]-C
        if cd>0 and abs(C-D)>abs(cumA[cd-1]-(cumA[i]-cumA[cd-1])):
            C = cumA[cd-1]; D = cumA[i] - C
        curef = (cumA[-1]-cumA[i]+1)//2
        ef = bisect.bisect_right(cumA,curef+cumA[i])
#        print(curef,ef)
        E = cumA[ef]-cumA[i]; F = cumA[-1]-E-cumA[i]
        if abs(E-F)>abs(cumA[ef-1]-cumA[i]-(cumA[-1]-cumA[ef-1])):
            E = cumA[ef-1]-cumA[i]; F = cumA[-1]-E-cumA[i]
 #           print(E,F)
        ansC = max(C,D,E,F)-min(C,D,E,F)
        ans = min(ans,ansC)
 #       print(C,D,E,F)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examD()

Submission status: Accepted

Solution code:
import numpy as np
import math

global csA
MAXINT = 2 ** 63 - 1

def getsumanddiff(i, j, k):
    tmp = csA[j+1]
    p = tmp - csA[i]
    q = csA[k+1] - tmp
    return p, q, abs(p - q)

N = int(input())
# A = np.array(list(map(int, input().split())))
# csA = np.cumsum(A)

csA = [0] * (N+1)
for i, v in enumerate(input().split()):
    csA[i+1] = csA[i] + int(v)

# init
mid0 = 0
mid2 = 2

p, q, r, s = [0]*4
diff = MAXINT

csAN = csA[N]
for mid1 in range(1, N - 2):
    diff0 = MAXINT
    diff2 = MAXINT
    csAmid1 = csA[mid1+1]

    # mid0 search
    for i in range(mid0, mid1):
        # tmpp, tmpq, tmpdiff0 = getsumanddiff(0, i, mid1)
        tmpp = csA[i+1]
        tmpq = csAmid1 - tmpp
        tmpdiff0 = abs(tmpp - tmpq)
        if diff0 > tmpdiff0:
            mid0 = i
            diff0 = tmpdiff0
            p = tmpp
            q = tmpq
        else:
            break

    # mid2 search
    start = mid1 if mid2 < mid1 else mid2
    for i in range(start, N - 1):
        # tmpr, tmps, tmpdiff2 = getsumanddiff(mid1+1, i, N - 1)
        csAi = csA[i+1]
        tmpr = csAi - csAmid1
        tmps = csAN - csAi
        tmpdiff2 = abs(tmpr - tmps)
        if diff2 > tmpdiff2:
            mid2 = i
            diff2 = tmpdiff2
            r = tmpr
            s = tmps
        else:
            break

    tmpdiff = max(p, q, r, s) - min(p, q, r, s)
    if diff > tmpdiff:
        diff = tmpdiff

print(diff)

Submission status: Accepted

Solution code:
import sys
import itertools
import bisect

readInt = lambda : [int(i) for i in input().split()];
n = readInt()[0]
A = readInt()

B = list(itertools.accumulate(A))

cand = 2 * pow(10, 14)
for i in range(2, len(A)-1):
  z = B[i-1]
  s = z // 2
  j = bisect.bisect_right(B, s)
  if (j == 0):
    j0 = j
  else:
    c0 = abs(2 * B[j-1] - z)
    c1 = abs(2 * B[j] - z)
    j0 = j-1 if c0 < c1 else j

  z = B[-1]
  s = B[i-1] + (B[-1] - B[i-1]) // 2
  j = bisect.bisect_right(B, s)
  if (j == i):
    j1 = j
  else:
    c0 = abs(B[j-1] - B[i-1] - (B[-1] - B[j-1]))
    c1 = abs(B[j]   - B[i-1] - (B[-1] - B[j]  ))
    j1 = j-1 if c0 < c1 else j

  c = [B[j0], B[i-1] - B[j0], B[j1] - B[i-1], B[-1] - B[j1]]
  cand = min(cand, max(c) - min(c))

ans = cand
print(ans)

Submission status: Accepted

Solution code:
def main():
    from itertools import accumulate as ac
    from bisect import bisect_right as br
    n=int(input())
    a=list(map(int,input().split()))
    b=list(ac([0]+a))
    ans=[]
    for i in range(2,n-1):
        l=b[i]
        r=b[n]
        lc=br(b,l/2)
        rc=br(b,l+(r-l)/2)
        temp_l=[]
        temp_r=[]
        if lc>1:
            temp_l.append([b[lc-1],l-b[lc-1]])
        if lc<i:
            temp_l.append([b[lc],l-b[lc]])
        if rc>i+1:
            temp_r.append([b[rc-1]-l,r-b[rc-1]])
        if rc<n:
            temp_r.append([b[rc]-l,r-b[rc]])
        temp_l.sort(key=lambda x:abs(x[0]-x[1]))
        temp_r.sort(key=lambda x:abs(x[0]-x[1]))
        temp=temp_l[0]+temp_r[0]
        temp.sort()
        ans.append(temp[-1]-temp[0])
    print(min(ans))
main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

S = [A[0], A[1], A[2], sum(A[3:])]
l = 0
r = 2
while r < N-1:
    if S[2] + A[r+1] <= S[3] - A[r+1]:
        S[2] += A[r+1]
        S[3] -= A[r+1]
        r += 1
    else:
        break

S2 = [S[0], S[1], S[2]+A[r+1], S[3]-A[r+1]]
ans = min(max(S)-min(S), max(S2)-min(S2))
for m in range(2, N-2):
    S[1] += A[m]
    S[2] -= A[m]
    while r < N-1:
        if S[2] + A[r+1] <= S[3] - A[r+1]:
            S[2] += A[r+1]
            S[3] -= A[r+1]
            r += 1
        else:
            break
    
    while l < m:
        if S[0] + A[l+1] <= S[1] - A[l+1]:
            S[0] += A[l+1]
            S[1] -= A[l+1]
            l += 1
        else:
            break
    
    S1 = [S[0]+A[l+1], S[1]-A[l+1], S[2], S[3]]
    S2 = [S[0], S[1], S[2]+A[r+1], S[3]-A[r+1]]
    S3 = [S[0]+A[l+1], S[1]-A[l+1], S[2]+A[r+1], S[3]-A[r+1]]
    ans = min([ans, max(S)-min(S), max(S1)-min(S1), max(S2)-min(S2), max(S3)-min(S3)])

print(ans)

Submission status: Accepted

Solution code:
import bisect

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	B = [0]
	for i in range(N):
		B.append(B[-1] + A[i])
	#print(B)
	ans = float("inf")
	for i in range(2, N - 1):
		Q = B[i]
		x = bisect.bisect_left(B, Q // 2)
		P = max(B[x], B[1])
		P = min(P, B[i - 1])
		if x >= 1:
			P2 = max(B[x - 1], B[1])
			Q2 = Q - P2
		Q3 = max(B[i] - B[i - 1], B[i] - B[x + 1])
		P3 = Q - Q3
		Q -= P

		S = B[N] - B[i]
		y = bisect.bisect_left(B, (B[i] + B[N]) // 2)
		R = max(B[y] - B[i] , B[i + 1] - B[i])
		R = min(R, B[N - 1] - B[i])
		R2 = max(B[y - 1] - B[i] , B[i + 1] - B[i])
		S2 = S - R2
		if y < N:
			S3 = max(B[N] - B[N - 1], B[N] - B[y + 1])
			R3 = S - S3
		S -= R
		ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
		ans = min(ans, max(P3, Q3, R, S) - min(P3, Q3, R, S))
		ans = min(ans, max(P, Q, R2, S2) - min(P, Q, R2, S2))
		ans = min(ans, max(P3, Q3, R2, S2) - min(P3, Q3, R2, S2))
		if x >= 1:
			ans = min(ans, max(P2, Q2, R, S) - min(P2, Q2, R, S))
			ans = min(ans, max(P2, Q2, R2, S2) - min(P2, Q2, R2, S2))
		if y < N:
			ans = min(ans, max(P, Q, R3, S3) - min(P, Q, R3, S3))
			ans = min(ans, max(P3, Q3, R3, S3) - min(P3, Q3, R3, S3))
		if x >= 1 and y < N:
			ans = min(ans, max(P2, Q2, R3, S3) - min(P2, Q2, R3, S3))
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
Ll, Lr, Rl, Rr = 0, A[0], A[1], sum(A[2:])
idx_l = 0  # 次に足すもの
idx_r = 2  # 次に足すもの
ans = float("inf")
for i, a in enumerate(A[1:-2], 1):
    Lr += a
    Rl -= a
    while True:
        a_ = A[idx_l]
        if abs((Ll+a_)-(Lr-a_)) < abs(Ll-Lr):
            Ll += a_
            Lr -= a_
            idx_l += 1
        else:
            break
    while True:
        a_ = A[idx_r]
        if abs((Rl+a_)-(Rr-a_)) < abs(Rl-Rr):
            Rl += a_
            Rr -= a_
            idx_r += 1
        else:
            break
    ans = min(ans, max(Ll, Lr, Rl, Rr)-min(Ll, Lr, Rl, Rr))
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from itertools import accumulate

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

cumsum = (0,) + tuple(accumulate(a))
# print(cumsum)

# PQ := [0, cut)
# RS = [cut, n)

ans = cumsum[-1]
for cut in range(2, n - 1):
    # cumsum[cut] : PQ区間和
    # cumsum[lc], cumsum[lc_1] : P区間和の候補
    # cumsum[n] - cumsum[cut] : RS区間和
    # cumsum[rc], cumsum[rc_1] : R区間和 + sPQの候補

    sPQ = cumsum[cut]
    sRS = cumsum[n] - cumsum[cut]

    lc = bisect_left(cumsum, sPQ // 2)
    # x以上で最小, 累積和のindexは、aの1-indexedに対応
    lc_1 = lc - 1
    # x未満で最大

    if abs((sPQ - cumsum[lc]) - cumsum[lc]) < abs((sPQ - cumsum[lc_1]) - cumsum[lc_1]):
        sP = cumsum[lc]
        # print('sP', sP, lc, cumsum)
    else:
        sP = cumsum[lc_1]
        # print('sP', sP, lc_1, cumsum)
    sQ = sPQ - sP
    # print('sQ', sQ)

    rc = bisect_left(cumsum, sPQ + (sRS // 2))
    # x以上で最小, 累積和のindexは、aの1-indexedに対応
    rc_1 = rc - 1
    # x未満で最大

    if abs((sRS - (cumsum[rc] - sPQ)) - (cumsum[rc] - sPQ)) < abs((sRS - (cumsum[rc_1] - sPQ)) - (cumsum[rc_1] - sPQ)):
        sR = cumsum[rc] - sPQ
        # print('sR', sR, rc, cumsum)
    else:
        sR = cumsum[rc_1] - sPQ
        # print('sR', sR, rc_1, cumsum)
    sS = sRS - sR
    # print('sS', sS)

    t = (sP, sQ, sR, sS)

    ans = min(ans, max(t) - min(t))
    # print(t)
print(ans)

Submission status: Accepted

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

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

def bisect(l,r,Su,il):
    while r-l>1:
        if S[(l+r)//2]-S[il] > Su//2:
            r = (l+r)//2
        else:
            l = (l+r)//2
    return l

min_score = 10**27

for i in range(2,N-1):
    l1 = bisect(0,i,S[i],0)
    l2 = bisect(i,N,S[N]-S[i],i)
    P = S[l1]
    Q = S[i]-P
    R = S[l2]-S[i]
    S1 = S[N]-S[l2]
    val1 = max(P,Q,R,S1)-min(P,Q,R,S1)
    P = S[l1+1]
    Q = S[i]-P
    R = S[l2]-S[i]
    S1 = S[N]-S[l2]
    val2 = max(P,Q,R,S1)-min(P,Q,R,S1)
    P = S[l1]
    Q = S[i]-P
    R = S[l2+1]-S[i]
    S1 = S[N]-S[l2+1]
    val3 = max(P,Q,R,S1)-min(P,Q,R,S1)
    P = S[l1+1]
    Q = S[i]-P
    R = S[l2+1]-S[i]
    S1 = S[N]-S[l2+1]
    val4 = max(P,Q,R,S1)-min(P,Q,R,S1)
    min_score = min(val1,val2,val3,val4,min_score)

print(min_score)

Submission status: Accepted

Solution code:
from bisect import bisect_right, bisect_left
from itertools import accumulate

N = int(input())
A = list(map(int, input().split()))
A = [0] + A
a = list(accumulate(A))
answer = a[-1]

# 切り口はN-1個, 真ん中の選び方はN-3
for i in range(N - 3):
    left = a[i + 2]
    right = a[-1] - left
    p = bisect_left(a, left // 2)
    P1 = a[p]
    Q1 = left - P1
    P2 = a[p - 1]
    Q2 = left - P2
    if abs(P1 - Q1) <= abs(P2 - Q2):
        P = P1
        Q = Q1
    else:
        P = P2
        Q = Q2

    s = bisect_right(a, a[-1] - right // 2)
    S1 = a[-1] - a[s - 1]
    R1 = right - S1
    S2 = a[-1] - a[s]
    R2 = right - S2
    if abs(S1 - R1) <= abs(S2 - R2):
        S = S1
        R = R1
    else:
        S = S2
        R = R2

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

print(answer)