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 itertools import accumulate as acc
from bisect import bisect_left as bl

def ans(n):
    tmp=0
    for i in range(N):
        tmp+=abs(a[i]-a[n-1])
    return tmp


N=int(input())
a=list(map(int,input().split()))
a=list(acc(a))

ans=10**18
for j in range(1,N-2):
    x=a[j]/2
    p=bl(a,x)
    if p==j: p-=1
    elif p>0 and x-a[p-1]<a[p]-x: p-=1

    y=(a[j]+a[N-1])/2

    q=bl(a,y)
    if q==N-1: q-=1
    elif q>j+1 and y-a[q-1]<a[q]-y: q-=1

    P,Q,R,S=a[p], a[j]-a[p], a[q]-a[j], a[N-1]-a[q]
    ans=min(ans, max(P,Q,R,S)-min(P,Q,R,S))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools
INF = float("inf")


def solve(N: int, A: "List[int]"):

    wa = list(itertools.accumulate(A))
    # print(wa)
    m = INF
    # しゃくとり法
    atama1, atama2 = 0, 2
    # 真ん中iを固定する
    for i in range(1, N-2):
        # 0からi-1までの分割位置を決める
        # 最も前後の数列の和が近くなるように

        # 前の虫
        s0, s1 = wa[atama1], wa[i]-wa[atama1]
        for j in range(atama1+1, i):
            t0, t1 = wa[j], wa[i]-wa[j]
            # print(s0, s1, t0, t1, atama1)
            if t0 >= t1:
                if abs(s1-s0) >= abs(t1-t0):
                    s0, s1 = t0, t1
                    atama1 += 1
                break
            s0, s1 = t0, t1
            atama1 += 1
        # print(s0, s1, t0, t1)

        # 後ろの虫
        s2, s3 = wa[atama2]-wa[i], wa[N-1]-wa[atama2]
        for j in range(atama2+1, N):
            t2, t3 = wa[j]-wa[i], wa[N-1]-wa[j]
            if t2 >= t3:
                if abs(s3-s2) >= abs(t3-t2):
                    s2, s3 = t2, t3
                    atama2 += 1
                break
            s2, s3 = t2, t3
            atama2 += 1

        s = [s0, s1, s2, s3]
        # print(s)
        s.sort()
        m = min(s[3]-s[0], m)

    print(m)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

S = [0]
for i,a in enumerate(A,1):
    S.append(S[i-1]+a)
Sn = S[-1]
ans = Sn

i0 = 1
k0 = 3
for j in range(2,N-1):
    tmpS = S[j]
    for i in range(i0,j):
        if S[i] > tmpS/2:
            break
    i -= abs(tmpS - S[i] - S[i]) > abs(tmpS - S[i-1] - S[i-1])
    i0 = i
    for k in range(k0,N):
        if S[k]-tmpS > (Sn-tmpS)/2:
            break
    k -= abs(Sn-S[k] - S[k] + tmpS) > abs(Sn - S[k-1] - S[k-1] + tmpS)
    k0 = k
    P = (S[i],S[j]-S[i],S[k]-S[j],S[-1]-S[k])
    ans = min(ans,max(P)-min(P))
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_left
N = int(input())
A = [0] + list(map(int, input().split()))


ans = float('inf')
A = list(accumulate(A))

for m in range(2, N - 1):
    Lx = A[m] // 2
    Li = bisect_left(A, Lx)
    if abs(Lx - A[Li]) > abs(Lx - A[Li - 1]):
        Li -= 1

    Rx = (A[-1] + A[m]) // 2
    Ri = bisect_left(A, Rx)
    if abs(Rx - A[Ri]) > abs(Rx - A[Ri - 1]):
        Ri -= 1

    P, Q, R, S = A[Li], A[m] - A[Li], A[Ri] - A[m], A[-1] - A[Ri]
    tmp_ans = max(P, Q, R, S) - min(P, Q, R, S)
    ans = min(ans, tmp_ans)


print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    _accum = 0
    accum = []
    for a in A:
        _accum += a
        accum.append(_accum)
    
    upper = 0
    bottom = 2
    result = 10 ** 18
    for middle in range(1, N-2):
        while True:
            if upper == middle -1:
                break
            up = accum[upper]
            btm = accum[middle] - accum[upper]
            if abs(up - btm) > abs((up+A[upper+1])-(btm-A[upper+1])):
                upper += 1
            else:
                break
        while True:
            if bottom == N - 2:
                break
            up = accum[bottom] - accum[middle]
            btm = accum[N-1] - accum[bottom]
            if abs(up - btm) > abs((up + A[bottom+1]) - (btm-A[bottom+1])):
                bottom += 1
            else:
                break
        li = [accum[middle] - accum[upper], accum[bottom] - accum[middle], accum[upper], accum[N-1] - accum[bottom]]
        li = [abs(_) for _ in li]
        result = min(result, max(li)-min(li))
    print(result)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    n = I()
    a = LI()
    for i in range(n-1):
        a[i+1] += a[i]
    a.insert(0,0)
    ans = float("inf")
    for m in range(3,n):
        lu = a[m-1]
        ru = a[n]-a[m-1]
        lm = bisect.bisect_left(a,lu//2)
        rm = bisect.bisect_left(a,ru//2+a[m-1])
        k = [a[lm],a[m-1]-a[lm],a[rm]-a[m-1],a[n]-a[rm]]
        if min(k):
            ans = min(ans,max(k)-min(k))
        lm -= 1
        k = [a[lm],a[m-1]-a[lm],a[rm]-a[m-1],a[n]-a[rm]]
        if min(k):
            ans = min(ans,max(k)-min(k))
        rm -= 1
        k = [a[lm],a[m-1]-a[lm],a[rm]-a[m-1],a[n]-a[rm]]
        if min(k):
            ans = min(ans,max(k)-min(k))
        lm += 1
        k = [a[lm],a[m-1]-a[lm],a[rm]-a[m-1],a[n]-a[rm]]
        if min(k):
            ans = min(ans,max(k)-min(k))
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
for i in range(n-1):a[i+1]+=a[i]
j,k,m=0,2,1e18
for i in range(1,n-1):
 while abs(a[j]*2-a[i])>abs(a[j+1]*2-a[i]):j+=1
 while abs(a[k]*2-a[i]-a[n-1])>abs(a[k+1]*2-a[i]-a[n-1]):k+=1
 t=a[j],a[i]-a[j],a[k]-a[i],a[n-1]-a[k];m=min(m,max(t)-min(t))
print(m)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
for i in range(n-1):
    a[i+1]+=a[i]
j,k=0,2
m=1e18
for i in range(1,n-1):
    while abs(a[j]*2-a[i])>abs(a[j+1]*2-a[i]):
        j+=1
    while abs(a[k]*2-a[i]-a[n-1])>abs(a[k+1]*2-a[i]-a[n-1]):
        k+=1
    t=a[j],a[i]-a[j],a[k]-a[i],a[n-1]-a[k]
    m=min(m,max(t)-min(t))
print(m)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
P,Q,R,S=A[0],0,A[1]+A[2],sum(A[3:])
l,r=1,3
ans=float("inf")
for i in range(2,N-1):
  Q+=A[i-1]
  while l<i-1:
    if abs(P-Q)>abs(P+A[l]-(Q-A[l])):
      P+=A[l]
      Q-=A[l]
      l+=1
    else:
      break
  R-=A[i-1]
  if i==r:
    R+=A[r]
    S-=A[r]
    r+=1
  while r<N-1:
    if abs(R-S)>abs(R+A[r]-(S-A[r])):
      R+=A[r]
      S-=A[r]
      r+=1
    else:
      break
  ans=min(ans,(max(P,Q,R,S)-min(P,Q,R,S)))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(item) for item in input().split()]

cumsum = [0] * n
for i in range(n):
  if i == 0:
    cumsum[0] = a[0]
  else:
    cumsum[i] = cumsum[i-1] + a[i]
    
l = 0
r = 2
ans = sum(a)
for i in range(1, n-1):
  while cumsum[i] - cumsum[l+1] > cumsum[l]:
    l += 1
  while cumsum[-1] - cumsum[r+1] > cumsum[r] - cumsum[i]:
    r += 1
  a = cumsum[l]
  b = cumsum[i] - cumsum[l]
  c = cumsum[r] - cumsum[i]
  d = cumsum[-1] - cumsum[r]
  
  ans = min(ans, max(a,b,c,d) - min(a,b,c,d))
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate as ac
n=int(input())
s=list(ac(list(map(int,input().split()))))
c=0
d=2
f=s[-1]
k=f
for i in range(1,n-1):
    while s[i]>s[c]+s[c+1]:
        c+=1
    while s[i]+f>s[d]+s[d+1]:
        d+=1
    j=[s[c],s[i]-s[c],s[d]-s[i],f-s[d]]
    k=min(max(j)-min(j),k)
print(k)

Submission status: Accepted

Solution code:
import math

n = int(input())

a = [int(i) for i in input().split(" ")]
ar = a[::-1]
a = [0] + a
ar = [0] + ar
s = [0] * (n + 1)
sr = [0] * (n + 1)
li = 0
ri = n

for i in range(1, n + 1):
    s[i] = a[i] + s[i - 1]
    sr[i] = ar[i] + sr[i - 1]
    
def f(a):
    return max(a) - min(a)

def fs(rr):
    global li
    while abs(s[rr] - 2 * s[li]) > abs(s[rr] - 2 * s[li + 1]):
        li += 1
        
def fsr(rr):
    global ri
    while abs(sr[rr] - 2 * sr[ri]) > abs(sr[rr] - 2 * sr[ri - 1]):
        ri -= 1

m_min = 2 * 10**14
for i in range(2, n - 1):
    fs(i)
    fsr(n - i)
    m = f([s[li], s[i] - s[li], sr[ri], sr[n - i] - sr[ri]])
    if m < m_min:
        m_min = m
        
print(m_min)

Submission status: Accepted

Solution code:
import itertools

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

lst_accum = list(itertools.accumulate(lst))

min_diff = 10**100
first_cut = 0
third_cut = 2
all_sum = lst_accum[-1]
for k in range(1, len(lst_accum)-2):
    second_last = lst_accum[k]
    P = lst_accum[first_cut]
    Q = second_last - P
    diff = abs(P-Q)
    while k - first_cut > 1 and diff > abs(second_last - lst_accum[first_cut+1]*2):
        first_cut += 1
        P = lst_accum[first_cut]
        Q = second_last - P
        diff = abs(P-Q)    
    
    if third_cut == k:
        third_cut += 1
    third_last = lst_accum[third_cut]
    S = all_sum - third_last
    R = third_last - second_last
    diff = abs(S-R)
    while (n-1) - third_cut > 1 and diff > abs(all_sum - lst_accum[third_cut+1]*2 + second_last):
        third_cut += 1
        third_last = lst_accum[third_cut]
        S = all_sum - third_last
        R = third_last - second_last
        diff = abs(S-R)
    
    #print(first_cut, k, third_cut)
    min_diff = min(min_diff, max(P,Q,R,S) - min(P,Q,R,S))
    #print(min_diff)
    

print(min_diff)

Submission status: Accepted

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

l, c, r = 0, 1, 2
P = sum(A[:l])
Q = sum(A[l:c])
R = sum(A[c:r])
S = sum(A[r:])
err = 10**10

while c <= N-2:
	while True:
		# leftを動かして考える
		# lを動かして差が広がったらいったん中断
		if abs(P-Q) < abs((P+A[l])-(Q-A[l])):
			break
		# もちろんcはlよりも大きい
		if l == c-1:
			break

		P += A[l]
		Q -= A[l]
		l += 1

	while True:
		# rightについても同様に動かして考える
		# rを動かして差が広がったらいったん中断
		if abs(R-S) < abs((R+A[r])-(S-A[r])):
			break
		# もちろんrはN-1以下
		if r == N-1:
			break

		R += A[r]
		S -= A[r]
		r += 1

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

	# centerについて調整
	Q += A[c]
	R -= A[c]
	c += 1

print(err)

Submission status: Accepted

Solution code:
n = int(input())

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

acc = []

s = 0
for c in l:
    s += c
    acc.append(s)

#find the left part best bars

left = [-1]*(n-1)
# left[i] is the best bar when middle bar is between i and i+1

L = 0
M = 1

for M in range(1,n-2):
    if M == 1:
        left[M] = 0
    else:
        #judge left bar go forward or not?!
        pre_bar = left[M-1]
        pre_gap = abs(acc[pre_bar] - (acc[M]-acc[pre_bar]))
        next_bar = M-1
        for nxt_bar in range(pre_bar+1,M):
            nxt_gap = abs(acc[nxt_bar]-(acc[M]-acc[nxt_bar]))
            if nxt_gap > pre_gap:
                next_bar = nxt_bar - 1
                break
            else:
                pre_gap = nxt_gap
        left[M] = next_bar
#print(left)



#find the right part best bars
right = [-1]*(n-1)
# right[i] is the best bar when middle bar is between i and i+1

for M in range(1,n-2)[::-1]:
    if M == n-3:
        right[M] = n - 2
    else:
        #judge right bar go backward or not?!
        pre_bar = right[M+1]
        pre_gap = abs(acc[n-1]-acc[pre_bar] - (acc[pre_bar] - acc[M]))
        next_bar = M+1
        for nxt_bar in range(M+1,pre_bar)[::-1]:
            nxt_gap = abs(acc[n-1]-acc[nxt_bar] - (acc[nxt_bar]-acc[M]))
            if nxt_gap > pre_gap:
                next_bar = nxt_bar + 1
                break
            else:
                pre_gap = nxt_gap
        right[M] = next_bar
#print(right)

res = acc[n-1] + 1
for M in range(1,n-2):
    L = left[M]
    R = right[M]
    a,b,c,d = acc[L],acc[M]-acc[L],acc[R]-acc[M],acc[n-1]-acc[R]
    gap = max(a,b,c,d)-min(a,b,c,d)
    res = min(res,gap)

print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import *
n = int(input())
s = list(accumulate(map(int,input().split())))
l,r,t = 0,2,s[-1]
a = t
for m in s[1:-2]:
    while abs(t-2*s[r]+m)>abs(t-2*s[r+1]+m):
        r += 1
    while abs(m-2*s[l])>abs(m-2*s[l+1]):
        l += 1
    x = sorted([s[l],m-s[l],s[r]-m,t-s[r]])
    a = min(a , x[3] - x[0])
print(a)

Submission status: Accepted

Solution code:
def equal_cut(N: int, A: list) -> int:
    Sa = [0] * (N + 1)  # A の累積和
    for i, a in enumerate(A):
        Sa[i + 1] = Sa[i] + a

    li, ri = 1, 3
    ans = float('inf')
    for mi in range(2, N - 1):
        # 中心の区切り mi を固定して左右の区間内で最適な
        # 区切り位置 li, ri を決めていく
        # B, C, D, E = A[:li], A[li:mi], A[mi:ri], A[ri:]
        if ri <= mi:
            ri = mi + 1

        # 適切な li を決める
        for temp_li in range(li + 1, mi):
            P, Q = Sa[temp_li - 1], Sa[mi] - Sa[temp_li - 1]
            nP, nQ = Sa[temp_li], Sa[mi] - Sa[temp_li]

            if abs(nP - nQ) <= abs(P - Q):
                # nP と nQ が近くなら li を更新する
                li = temp_li
            else:
                # nP と nQ が遠ざかり始めたらこれ以上 li を
                # 右に移動しても差は広がる一方で探索する意味
                # がないので打ち切り
                break

        # 適切な ri を決める
        for temp_ri in range(ri + 1, N):
            R, S = Sa[temp_ri - 1] - Sa[mi], Sa[N] - Sa[temp_ri - 1]
            nR, nS = Sa[temp_ri] - Sa[mi], Sa[N] - Sa[temp_ri]

            if abs(nR - nS) <= abs(R - S):
                ri = temp_ri
            else:
                break

        P = Sa[li]
        Q = Sa[mi] - Sa[li]
        R = Sa[ri] - Sa[mi]
        S = Sa[N] - Sa[ri]
        temp = max(P, Q, R, S) - min(P, Q, R, S)

        if temp < ans:
            ans = temp

    return ans


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = equal_cut(N, A)
    print(ans)

Submission status: Accepted

Solution code:
# /user/bin/python
# -*- coding: utf-8 -*-
import sys 
from itertools import accumulate


def diff(p,q,r,s):
  return abs(max(p,q,r,s) - min(p,q,r,s))


## input
N = int(sys.stdin.readline().rstrip())
An = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
sum = list(accumulate(An))


ans = sys.maxsize
li,ri = 1, 3
for i in range(2, N-1):
  while sum[li] < sum[i]-sum[li]:
    li += 1
  while sum[ri]-sum[i] < sum[N]-sum[ri]:
    ri += 1

  P1,Q1 = sum[li], sum[i]-sum[li]
  P2,Q2 = sum[li-1], sum[i]-sum[li-1]
  R1,S1 = sum[ri]-sum[i], sum[N]-sum[ri]
  R2,S2 = sum[ri-1]-sum[i], sum[N]-sum[ri-1]

  ans = min(ans, diff(P1,Q1,R1,S1), diff(P1,Q1,R2,S2), diff(P2,Q2,R1,S1), diff(P2,Q2,R2,S2))

print(ans)

Submission status: Accepted

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

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

B = [0 for i in range(N)]
B[1] = 0
left = 0
for i in range(2, N - 1):
  t = abs(cs[i] - cs[left] * 2) 
  for j in range(left + 1, i):
    if abs(cs[i] - cs[j] * 2) > t:
      left = j - 1
      break
    t = abs(cs[i] - cs[j] * 2)
  else:
    left = i - 1
  B[i] = left
E = [0 for i in range(N)]
E[N - 2] = N - 2
right = N - 2
for i in range(N - 3, 0, -1):
  t = abs(cs[N - 1] - cs[right] * 2 + cs[i]) 
  for j in range(right - 1, i, -1):
    if abs(cs[N - 1] - cs[j] * 2 + cs[i]) > t:
      right = j + 1
      break
    t = abs(cs[N - 1] - cs[j] * 2 + cs[i])
  else:
    right = i + 1
  E[i] = right

Ans = 10**15
for i in range(1, N - 2):
  b = cs[B[i]]
  c = cs[i] - cs[B[i]]
  d = cs[E[i]] - cs[i]
  e = cs[-1] - cs[E[i]]
  t = max(b, c, d, e) - min(b, c, d, e)
  if Ans > t:
    Ans = t
print(Ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)
def spl_l(i,b):
    while abs(h[i]-2*h[b])>abs(h[i]-2*h[b+1]):
        b+=1
    return b
def spl_r(i,b):
    while abs(h[-1]-2*h[b]+h[i])>abs(h[-1]-2*h[b+1]+h[i]):
        b+=1
    return b
def calc(j,i,k):
    pqrs=[h[j],h[i]-h[j],h[k]-h[i],h[-1]-h[k]]
    ans=max(pqrs)-min(pqrs)
    return ans

j=0
k=2
ans=18**20
for i in range(1,N-2):
    j=spl_l(i,j)
    k=spl_r(i,k)
    ans=min(ans,calc(j,i,k))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + a[i]
llsum = a[0]
lrsum = a[1]
l = [0] * n
l[2] = 1
for mid in range(3, n-1):
    new = a[mid-1]
    lrsum += new
    l[mid] = l[mid-1]
    unk = a[l[mid]]
    while(abs(lrsum - llsum) > abs(lrsum - llsum - 2 * unk)):
        llsum += unk
        lrsum -= unk
        l[mid] += 1
        unk = a[l[mid]]
rrsum = a[n-1]
rlsum = a[n-2]
r = [0] * n
r[n-2] = n-1
for mid in reversed(range(2, n-2)):
    new = a[mid]
    rlsum += new
    r[mid] = r[mid+1]
    unk = a[r[mid] - 1]
    while(abs(rlsum - rrsum) > abs(rlsum - rrsum - 2 * unk)):
        rrsum += unk
        rlsum -= unk
        r[mid] -= 1
        unk = a[r[mid] - 1]
minabs = 10 ** 20
for mid in range(2, n-1):
    c0 = cum[l[mid]]
    c1 = cum[mid]
    c2 = cum[r[mid]]
    sums = (c0, c1 - c0, c2 - c1, cum[n] - c2)
    minabs = min(minabs, max(sums) - min(sums))
print(minabs)

Submission status: Accepted

Solution code:
from itertools import accumulate
n=int(input())
A=list(map(int,input().split()))
S=list(accumulate(A))
left=0
right=2
ans=float('inf')
for i in range(1,n-2):
    while abs(S[left]-(S[i]-S[left]))>abs(S[left+1]-(S[i]-S[left+1])):
        left+=1
    while abs(S[right]-S[i]-(S[n-1]-S[right]))>abs(S[right+1]-S[i]-(S[n-1]-S[right+1])):
        right+=1
    minL,maxL=min(S[left],S[i]-S[left]),max(S[left],S[i]-S[left])
    minR,maxR=min(S[right]-S[i],S[n-1]-S[right]),max(S[right]-S[i],S[n-1]-S[right])
    ans=min(ans,max(maxL,maxR)-min(minL,minR))
print(ans)

Submission status: Accepted

Solution code:
# 解説みて実装
import numpy as np


N = int(input())
A = list(map(int, input().split()))
C = np.cumsum(A).tolist()

LL = [np.inf] * N
LR = [np.inf] * N

l = 0

for m in range(N-1):
    if l < m:
        LL[m] = C[l]
        LR[m] = C[m] - C[l]
        while l < m:
            LL_tmp = C[l+1]
            LR_tmp = C[m] - C[l+1]
            if abs(LL[m] - LR[m]) >= abs(LL_tmp - LR_tmp):
                l    += 1
                LL[m] = C[l]
                LR[m] = C[m] - C[l]
            else:
                break

B = A[::-1]
D = np.cumsum(B).tolist()

RL = [np.inf] * N
RR = [np.inf] * N

r = 0

for m in range(N-1):
    if r < m:
        RR[m] = D[r]
        RL[m] = D[m] - D[r]
        while r < m:
            RR_tmp = D[r+1]
            RL_tmp = D[m] - D[r+1]
            if abs(RR[m] - RL[m]) >= abs(RR_tmp - RL_tmp):
                r    += 1
                RR[m] = D[r]
                RL[m] = D[m] - D[r]
            else:
                break

RR = RR[::-1]
RL = RL[::-1]

X = np.array([LL[:-1], LR[:-1], RL[1:], RR[1:]])[:, 1:-1]

print(int(np.min(np.abs(np.max(X, axis=0) - np.min(X, axis=0)))))

Submission status: Accepted

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

N = int(input())
P = list(accumulate(list(map(int, input().split()))))
l, r = 0, 2
ans = P[N - 1]
for i in range(1, N - 2):
    while l < i and abs(P[i] - 2 * P[l]) > abs(P[i] - 2 * P[l + 1]):
        l += 1
    while r < N - 1 and abs(P[N - 1] - 2 * P[r] + P[i]) > abs(P[N - 1] - 2 * P[r + 1] + P[i]):
        r += 1
    minn = min(abs(P[i] - P[l]), P[l], abs(P[N - 1] - P[r]), abs(P[r] - P[i]))
    maxn = max(abs(P[i] - P[l]), P[l], abs(P[N - 1] - P[r]), abs(P[r] - P[i]))
    ans = min(ans, maxn - minn)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect

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

    B = []
    t = 0
    for a in A:
        t += a
        B.append(t)

    T = B[N - 1]

    i2 = bisect.bisect_left(B, T / 2, lo = 1, hi = N - 2)
    i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
    i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)

    P = B[i1]
    Q = B[i2] - B[i1]
    R = B[i3] - B[i2]
    S = T - B[i3]

    min_d = max(P, Q, R, S) - min(P, Q, R, S)
    min_half = T / 2 - min_d
    max_half = T / 2 + min_d

    i2_lo = bisect.bisect_left(B, min_half, lo = 1, hi = N - 2)
    i2_hi = bisect.bisect_left(B, max_half, lo = i2_lo, hi = N - 2) + 1

    for i2 in range(i2_lo, i2_hi):
        if min_d * 2 < abs(T - 2 * B[i2]):
            continue

        i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
        i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)
        i1_lo, i1_hi = i1, i1 + 1
        i3_lo, i3_hi = i3, i3 + 1
        if B[i1] * 2 != B[i2] and 0 < i1:
            i1_lo -= 1
        if B[i3] * 2 != T + B[i2] and i2 + 1 < i3:
            i3_lo -= 1

        for i1 in range(i1_lo, i1_hi):
            P = B[i1]
            Q = B[i2] - B[i1]
            for i3 in range(i3_lo, i3_hi):
                R = B[i3] - B[i2]
                S = T - B[i3]
                d = max(P, Q, R, S) - min(P, Q, R, S)
                if d < min_d:
                    min_d = d


    print(min_d)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate
input = stdin.readline
N = int(input())
A = [0] + list(map(int, input().split()))
acc = list(accumulate(A))
# print(acc)

lefti = 0
righti = 0
ans = 10**15
for i in range(2, N-1):
    while abs(acc[lefti]-(acc[i]-acc[lefti])) > abs(acc[lefti+1]-(acc[i]-acc[lefti+1])):
        lefti += 1
    while abs(acc[righti]-acc[i]-(acc[-1]-acc[righti])) > abs(acc[righti+1]-acc[i]-(acc[-1]-acc[righti+1])):
        righti += 1
    minbc, maxbc = min(acc[lefti], acc[i]-acc[lefti]
                       ), max(acc[lefti], acc[i]-acc[lefti])
    minde, maxde = min(acc[righti]-acc[i], acc[-1]-acc[righti]
                       ), max(acc[righti]-acc[i], acc[-1]-acc[righti])
    #print(i, minbc, maxbc, minde, maxde)
    ans = min(ans, max(maxbc, maxde)-min(minbc, minde))
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n = int(input())
a = list(map(int, input().split()))

s = list(accumulate(a))
ans = float("inf")

j = 0
k = 2

for i in range(1, n-2):
    while abs(s[i]-2*s[j]) > abs(s[i]-2*s[j+1]):
        j += 1
    while abs(s[n-1] - 2*s[k] + s[i]) > abs(s[n-1] - 2*s[k+1] + s[i]):
        k += 1
    t = max(s[j], s[i]-s[j], s[k]-s[i], s[n-1]-s[k]) - min(s[j], s[i]-s[j], s[k]-s[i], s[n-1]-s[k])
    ans = min(ans, t)

print(ans)

Submission status: Accepted

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

ans = float('inf')
# 切る位置を全探索
for mid in range(1, N):
    L_target, R_target = A[mid] // 2, (A[mid] + A[-1]) // 2
    L_index, R_index = bisect_left(A, L_target), bisect_left(A, R_target)
    if abs(A[L_index - 1] - L_target) < abs(A[L_index] - L_target):
        L_index -= 1
    if abs(A[R_index - 1] - R_target) < abs(A[R_index] - R_target):
        R_index -= 1

    P, Q, R, S = A[L_index], A[mid]-A[L_index], A[R_index]-A[mid], A[-1]-A[R_index]
    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()))

b,c,d,e = 0,a[0],a[1],sum(a[2:n])
p,q,r = -1,1,1
m = sum(a)

while q <= n-3:
  c += a[q]
  d -= a[q]
  while p+1 <= q-1 and abs(b-c+2*a[p+1]) <= abs(b-c):
    p += 1
    b += a[p]
    c -= a[p]
  while r+1 <= n-2 and abs(d-e+2*a[r+1]) <= abs(d-e):
    r += 1
    d += a[r]
    e -= a[r]
  m = min(m,max(b,c,d,e) - min(b,c,d,e))
  q += 1
print(m)

Submission status: Accepted

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

b = a[0]
c = a[1]
d = a[2]
e = sum(a[3:n])
p = 0
q = 1
r = 2
while r+1 <= n-2 and abs((d+a[r+1])-(e-a[r+1])) < abs(d-e):
    r += 1
    d += a[r]
    e -= a[r]
m = max(b,c,d,e) - min(b,c,d,e)

while q <= n-4:
  q += 1
  c += a[q]
  d -= a[q]
  while p+1 <= q-1 and abs((b+a[p+1])-(c-a[p+1])) <= abs(b-c):
    b += a[p+1]
    c -= a[p+1]
    p += 1
  while r+1 <= n-2 and abs((d+a[r+1])-(e-a[r+1])) <= abs(d-e):
    d += a[r+1]
    e -= a[r+1]
    r += 1
  m = min(m,max(b,c,d,e) - min(b,c,d,e))
print(m)

Submission status: Accepted

Solution code:
n = int(input())
a = input().split()
a = [int(m) for m in a]
asum = []
t = 0
for i in range(n):
    t += a[i]
    asum.append(t)
x1 = 0
x2 = 0
x3 = 0
x4 = 0
s1 = 1
s2 = 3
ansli = []
for i in range(n - 3):
    ansli.append([])
ac = 2
bc = 2
for i in range(2, n - 1):
    for j in range(s1, i):
        if j == 1:
            s1l = asum[0]
            s1r = asum[i - 1] - asum[0]
            cr = abs(s1l - s1r)
            ac = 2
        else:
            if ac == 1:
                s1r += a[i - 1]
                cr = abs(s1l - s1r)

            s1l2 = asum[j - 1]
            s1r2 = asum[i - 1] - asum[j - 1]
            cr2 = abs(s1l2 - s1r2)
            if cr2 <= cr:
                s1l = s1l2
                s1r = s1r2
                cr = cr2
                s1 = j
                ac = 2
            else:
                break
    ansli[i - 2].append(s1l)
    ansli[i - 2].append(s1r)
    ac = 1
    for k in range(s2, n):
        if k == 3:
            s2l = asum[i] - asum[i - 1]
            s2r = asum[n - 1] - asum[i]
            crw = abs(s2l - s2r)
            bc = 2
        else:
            if bc == 1:
                s2l -= a[i - 1]
                crw = abs(s2l - s2r)

            s2l2 = asum[k - 1] - asum[i - 1]
            s2r2 = asum[n - 1] - asum[k - 1]
            cr2w = abs(s2l2 - s2r2)
            if cr2w <= crw:
                s2l = s2l2
                s2r = s2r2
                crw = cr2w
                s2 = k
                bc = 2
            else:
                break
    ansli[i - 2].append(s2l)
    ansli[i - 2].append(s2r)
    bc = 1
ransli = []
for i in range(n - 3):
    p = max(ansli[i])
    q = min(ansli[i])
    ransli.append(p - q)

print(min(ransli))

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
T=[]
for i in range(N):
  if i==0:
    T.append(A[i])
  else:
    T.append(T[i-1]+A[i])
ans=float("inf")
x=1
y=1
for i in range(2,N):
  while abs(T[i-1]-2*T[x-1])>abs(T[i-1]-2*T[x]):
    x+=1
  while abs(T[i-1]+T[N-1]-2*T[y-1])>abs(T[i-1]+T[N-1]-2*T[y]):
    y+=1
  P=T[x-1]
  Q=T[i-1]-T[x-1]
  R=T[y-1]-T[i-1]
  S=T[N-1]-T[y-1]
  A=max(P,Q,R,S)
  B=min(P,Q,R,S)
  ans=min(ans,A-B)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    d1 = 1
    d2 = 2
    d3 = 3
    P = A[0]
    Q = A[1]
    R = A[2]
    S = sum(A[3:])
    ans = max(P, Q, R, S) - min(P, Q, R, S)
    while d2 <= N-2:
        while d1 < d2-1:
            x = A[d1]
            if abs((Q-x) - (P+x)) < abs(Q - P):
                P += x
                Q -= x
                d1 += 1
            else:
                break
        while d3 < N-1:
            x = A[d3]
            if d2 >= d3 or abs((S-x) - (R+x)) < abs(S - R):
                R += x
                S -= x
                d3 += 1
            else:
                break
        current = max(P, Q, R, S) - min(P, Q, R, S)
        ans = min(current, ans)
        Q += A[d2]
        R -= A[d2]
        d2 += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

cumsum = [a[0]]
for i in range(1, n):
    cumsum.append(cumsum[i-1]+a[i])

i, k = 0, 2
ans = 10**18
for j in range(1, n-2):
    while True:
        p = cumsum[i]
        q = cumsum[j] - cumsum[i]
        p_new = cumsum[i+1]
        q_new = cumsum[j] - cumsum[i+1]
        if abs(p_new-q_new) < abs(p-q):
            i += 1
        else:
            break

    while True:
        r = cumsum[k] - cumsum[j]
        s = cumsum[-1] - cumsum[k]
        r_new = cumsum[k+1] - cumsum[j]
        s_new = cumsum[-1] - cumsum[k+1]
        if abs(r_new-s_new) < abs(r-s):
            k += 1
        else:
            break

    ans = min(ans, max([p, q, r, s]) - min([p, q, r, s]))
    # print(ans, ':', i, j, k, ':', p, q, r, s)
print(ans)

Submission status: Accepted

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

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

left = 1
right = 3

ans = float('inf')

for mid in range(2, n-1):
    p = a[left - 1]
    q = a[mid - 1] - a[left - 1]
    p_next = a[left]
    q_next = a[mid - 1] - a[left]

    while abs(p_next - q_next) <= abs(p - q):
        left += 1
        p = a[left - 1]
        q = a[mid - 1] - a[left - 1]
        p_next = a[left]
        q_next = a[mid - 1] - a[left]

    r = a[right - 1] - a[mid - 1]
    s = a[n - 1] - a[right - 1]
    r_next = a[right] - a[mid - 1]
    s_next = a[n - 1] - a[right]

    while abs(r_next - s_next) <= abs(r - s):
        right += 1
        r = a[right - 1] - a[mid - 1]
        s = a[n - 1] - a[right - 1]
        r_next = a[right] - a[mid - 1]
        s_next = a[n - 1] - a[right]

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

print(ans)