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:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    def nibutan1(ok,ng,index):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve1(mid,index):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve1(mid,index):
        P=S[mid]
        Q=S[index]-S[mid]
        return P<Q

    def nibutan2(ok,ng,index):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve2(mid,index):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve2(mid,index):
        P=S[mid]-S[index]
        Q=S[N-1]-S[mid]
        return P<Q
    
    N=int(input())
    A=list(map(int,input().split()))
    S=[A[0]]
    for i in range(N-1):
        S.append(S[i]+A[i+1])
    ans=INF
    for i in range(1,N-1):
        c1=nibutan1(0,i-1,i)
        c2=nibutan2(i,N-2,i)
        if abs(S[c1]-(S[i]-S[c1]))<abs(S[c1+1]-(S[i]-S[c1+1])):
            p,q=S[c1],S[i]-S[c1]
        else:
            p,q=S[c1+1],S[i]-S[c1+1]
        if abs(S[c2]-S[i]-(S[N-1]-S[c2]))<abs(S[c2+1]-S[i]-(S[N-1]-S[c2+1])):
            r,s=S[c2]-S[i],S[N-1]-S[c2]
        else:
            r,s=S[c2+1]-S[i],S[N-1]-S[c2+1]
        ans=min(ans,max(p,q,r,s)-min(p,q,r,s))
    print(ans)
        
        
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

l = 1
m = 2
r = 3
a = sum(A[:l])
b = sum(A[l:m])
c = sum(A[m:r])
d = sum(A[r:])
ans = max(a, b, c, d) - min(a, b, c, d)
# 尺取法(3点動かす)
while m < N-1:
    # a,bの差が最小になるまで左を動かす
    while l < m-1 and abs(a - b) > abs(a+A[l] - (b-A[l])):
        a += A[l]
        b -= A[l]
        l += 1
    # c,dの差が最小になるまで右を動かす
    while r < N-1 and abs(c - d) > abs(c+A[r] - (d-A[r])):
        c += A[r]
        d -= A[r]
        r += 1
    ans = min(ans, max(a, b, c, d) - min(a, b, c, d))
    # 真ん中を動かす
    b += A[m]
    c -= A[m]
    m += 1
    # 真ん中が右に追いついたら、右も合わせて+1する
    if m == r:
        c += A[r]
        d -= A[r]
        r += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a_cs = [0] * (n + 1)
for i in range(n):
    a_cs[i + 1] = a_cs[i] + a[i]

i1 = 1
i3 = 3
ans = 10**14
for i2 in range(2, n - 1):
    while i1 + 1 < i2 and abs(a_cs[i1] * 2 - a_cs[i2]) > abs(a_cs[i1 + 1] * 2 -
                                                             a_cs[i2]):
        i1 += 1

    while i3 + 1 < n and abs(a_cs[-1] + a_cs[i2] - a_cs[i3] *
                             2) > abs(a_cs[-1] + a_cs[i2] - a_cs[i3 + 1] * 2):
        i3 += 1

    p = a_cs[i1]  # [0,i1)
    q = a_cs[i2] - a_cs[i1]  # [i1, i2)
    r = a_cs[i3] - a_cs[i2]  # [i2, i3)
    s = a_cs[n] - a_cs[i3]  # [i3, n)
    cand = max(p, q, r, s) - min(p, q, r, s)
    ans = min(ans, cand)

print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
cs = [0] * N
cs[0] = a[0]
for i in range(N - 1): cs[i + 1] = cs[i] + a[i + 1]
res = float("inf")
for m in range(1, N - 1):
  l = bl(cs, cs[m] // 2, hi = m)
  r = bl(cs, cs[m] + (cs[-1] - cs[m]) // 2, lo = m)
  l -= l == m
  r += r == m
  nl = l + 0
  nr = r + 0
  for i in range(3):
    if i == 1: continue
    if 0 <= l + i - 1 < m:
      if abs(cs[m] - 2 * cs[l + i - 1]) < abs(cs[m] - 2 * cs[l]):
        nl = l + i - 1
    if m < r + i - 1 < N:
      if abs(cs[-1] - 2 * cs[r + i - 1] + cs[m]) < abs(cs[-1] - 2 * cs[r] + cs[m]):
        nr = r + i - 1
  l = nl
  r = nr
  res = min(res, max(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]) - min(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]))
print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 10**19
sum_a = [0]
for x in a:
    sum_a.append(sum_a[-1]+x)

for q_r in range(2,n-1):
    pq = sum_a[q_r]
    rs = sum_a[n]-sum_a[q_r]
    #print(pq,rs)
    ok1 = 1
    ng1 = q_r
    while ng1-ok1 > 1:
        mid1 = (ng1+ok1)//2
        if pq > 2*sum_a[mid1]:
            ok1 = mid1
        else:
            ng1 = mid1
    p1 = sum_a[ok1]
    q1 = pq-p1
    p2 = sum_a[ok1+1]
    q2 = pq-p2
    if abs(p1-q1) > abs(p2-q2):
        p = p2
        q = q2
    else:
        p = p1
        q = q1
    ok2 = q_r+1
    ng2 = n
    while ng2-ok2>1:
        mid2 = (ng2+ok2)//2
        if rs > 2*(sum_a[mid2]-pq):
            ok2 = mid2
        else:
            ng2 = mid2
    r1 = sum_a[ok2]-pq
    s1 = rs-r1
    r2= sum_a[ok2+1]-pq
    s2 = rs-r2
    if abs(r1-s1) > abs(r2-s2):
        r = r2
        s = s2
    else:
        r = r1
        s = s1
    #print(p,q,r,s)
    ans = min(ans,max(p,q,r,s)-min(p,q,r,s))

print(ans)

Submission status: Accepted

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

def calc(B):
    P, Q = B[0], B[1]
    ret = [None] * N
    ret[1] = (P, Q)
    mid = 1

    for right in range(2, N - 2):
        Q += B[right]
        while mid < right:
            newP = P + B[mid]
            newQ = Q - B[mid]

            if abs(newP - newQ) >= abs(P - Q):
                break
            mid += 1
            P = newP
            Q = newQ

        ret[right] = (P, Q)

    return ret

left = calc(A)[1: -2]
right = calc(A[:: -1])[1: -2][:: -1]

ans = 10**10
for (P, Q), (R, S) in zip(left, right):
    ans = min(ans, abs(max(P, Q, R, S) - min(P, Q, R, S)))

print(ans)

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
S = [0]
for a in A:
    S += [S[-1] + a]

ans = float("inf")
l = 0
r = 2
for i in range(1, N - 1):
    while S[l] < S[i] - S[l + 1]:
        l += 1
    while S[r] - S[i] < S[N] - S[r + 1]:
        r += 1

    a = S[l]
    b = S[i] - S[l]
    c = S[r] - S[i]
    d = S[N] - S[r]

    ans = min(ans, max(a, b, c, d) - min(a, b, c, d))
print(ans)

Submission status: Accepted

Solution code:
import bisect

def cumsum(inlist):
    s = 0
    outlist = [0]
    for i in inlist:
        s += i
        outlist.append(s)
    return outlist

def bis(inlist, l, r):
    ok = r
    ng = l
    while ok - ng > 1:
        mid = (ok+ng)//2
        if inlist[r] - 2*inlist[mid] + inlist[l] > 0:
            ng = mid
        else:
            ok = mid
    upper = inlist[r] - 2*inlist[ok] + inlist[l]
    lower = inlist[r] - 2*inlist[ng] + inlist[l]
    if abs(upper) > abs(lower):
        return inlist[r] - inlist[ng], inlist[ng] - inlist[l]
    else:
        return inlist[r] - inlist[ok], inlist[ok] - inlist[l]



n = int(input())
num = [ int(v) for v in input().split() ]
accum_num = cumsum(num)
ans_list = []

for i in range(2,n+1-2):
    a, b = bis(accum_num, 0, i)
    c, d = bis(accum_num, i, n)
    ans_list2 = sorted([a, b, c, d])
    ans_list.append(ans_list2[-1] - ans_list2[0])
print(min(ans_list))

Submission status: Accepted

Solution code:
n=int(input())
a=[0]+list(map(int,input().split()))
inf=float("inf")

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

left=1
right=0
ans=inf
for mid in range(2,n-1):
    right=max(right,mid+1)
    while a[left]<a[mid]-a[left]:
        left+=1
    data_1=[[a[left-1],a[mid]-a[left-1]],[a[mid]-a[left],a[left]]]
    while a[right]-a[mid]<a[n]-a[right]:
        right+=1
    data_2=[[a[right-1]-a[mid],a[n]-a[right-1]],[a[n]-a[right],a[right]-a[mid]]]

    for x,y in data_1:
        for z,w in data_2:
            ans=min(ans,max(y,w)-min(x,z))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
l=0
r=2
ans=10**18
for i in range(1,n-2):
    while b[i]-b[l]>b[l+1]:
        l+=1
    while b[-1]-b[r]>b[1+r]-b[i]:
        r+=1
    p=b[l]
    q=b[i]-b[l]
    rr=b[r]-b[i]
    s=b[n-1]-b[r]
    ans=min(ans,abs(max(p,q,rr,s)-min(p,q,rr,s)))
    
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
from itertools import accumulate
b=[0]+list(accumulate(a))
l=0
r=2
ans=10**18
for i in range(1,n-1):
    while b[i]-b[l]>b[l+1]:
        l+=1
    while b[-1]-b[r]>b[1+r]-b[i]:
        r+=1
    p=b[l]
    q=b[i]-b[l]
    rr=b[r]-b[i]
    s=b[n]-b[r]
    ans=min(ans,abs(max(p,q,rr,s)-min(p,q,rr,s)))
    
print(ans)

Submission status: Accepted

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

S = [0]*N
S[0] = A[0]
for i in range(1, N):
    S[i] = A[i]+S[i-1]
    
ans = 2*10**14
l = 0
temp = 2*10**14
r = 2
#for i in range(2, N):
#    if abs(S[-1]-2*S[i]+S[1]) < temp:
#        temp = abs(S[-1]-2*S[r]+S[1])
#        r = i
        
for i in range(2, N-1):
    r = max(r, i)
    while l+1 < i-1 and abs(S[i-1]-2*S[l]) > abs(S[i-1]-2*S[l+1]):
        l += 1
    while r+1 < N-1 and abs(S[N-1]-2*S[r]+S[i-1])  > abs(S[N-1]-2*S[r+1]+S[i-1]):
        r += 1
    t = max(S[N-1]-S[r], S[r]-S[i-1], S[i-1]-S[l], S[l]) - min(S[N-1]-S[r], S[r]-S[i-1], S[i-1]-S[l], S[l])
    ans = min(ans, t)
    
print(ans)

Submission status: Accepted

Solution code:
import bisect
INF = 10**16
n=int(input())
a=list(map(int,input().split()))
la=[0]
for i in range(n):
    la.append(la[i]+a[i])
la.pop(0)
sa = la[-1]
l=0
r=2
res = INF
for i in range(1,n-2):
    while abs(la[l+1]-(la[i]-la[l+1])) < abs(la[l]-(la[i]-la[l])):
        l += 1

    if r == i:
        r += 1
    while abs((la[r+1] - la[i])-(sa - la[r+1])) < abs((la[r] - la[i])-(sa - la[r])):
        r += 1
    r1 = la[l]
    r2 = la[i] - la[l]
    r3 = la[r] - la[i]
    r4 = sa    - la[r]
    res=min(res,max(r1,r2,r3,r4)-min(r1,r2,r3,r4))
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from bisect import bisect_left as bisect
    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=INF
    for j in range(1,n):
        i=bisect(S,S[j]/2)
        k=bisect(S,(S[j]+S[-1])/2)
        ans=min(ans,max(S[i],S[j]-S[i],S[k]-S[j],S[-1]-S[k])-min(S[i],S[j]-S[i],S[k]-S[j],S[-1]-S[k]))
        ans=min(ans,max(S[i],S[j]-S[i],S[k-1]-S[j],S[-1]-S[k-1])-min(S[i],S[j]-S[i],S[k-1]-S[j],S[-1]-S[k-1]))
        ans=min(ans,max(S[i-1],S[j]-S[i-1],S[k]-S[j],S[-1]-S[k])-min(S[i-1],S[j]-S[i-1],S[k]-S[j],S[-1]-S[k]))
        ans=min(ans,max(S[i-1],S[j]-S[i-1],S[k-1]-S[j],S[-1]-S[k-1])-min(S[i-1],S[j]-S[i-1],S[k-1]-S[j],S[-1]-S[k-1]))
    print(ans)
resolve()

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_left

def main():
    N, *A = map(int, open(0).read().split())

    A = [0] + list(accumulate(A))

    ans = float("inf")
    for i in range(2, N - 1):
        lm = A[i] // 2
        l = bisect_left(A, lm)
        if abs(A[l - 1] - lm) < abs(A[l] - lm):
            l -= 1

        rm = (A[i] + A[N]) // 2
        r = bisect_left(A, rm)
        if abs(A[r - 1] - rm) < abs(A[r] - rm):
            r -= 1

        P = A[l]
        Q = A[i] - A[l]
        R = A[r] - A[i]
        S = A[N] - A[r]

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

    print(ans)

main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_left

N, *A = map(int, open(0).read().split())

A = [0] + list(accumulate(A))

ans = float("inf")
for i in range(2, N - 1):
    lm = A[i] // 2
    l = bisect_left(A, lm)
    if abs(A[l - 1] - lm) < abs(A[l] - lm):
        l -= 1

    rm = (A[i] + A[N]) // 2
    r = bisect_left(A, rm)
    if abs(A[r - 1] - rm) < abs(A[r] - rm):
        r -= 1

    P = A[l]
    Q = A[i] - A[l]
    R = A[r] - A[i]
    S = A[N] - A[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
from bisect import bisect_left

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

ans = float("inf")

for j in range(2,n-1):
    i_list = []
    i_left = bisect_left(s, s[j-1]//2)-1
    if i_left != -1:
        i_list.append([s[i_left], s[j-1]-s[i_left]])
    if i_left != j-2:
        i_list.append([s[i_left+1], s[j-1]-s[i_left+1]])

    k_list = []
    k_left = bisect_left(s, s[j-1]+(s[-1]-s[j-1])//2)-1
    if k_left != j-1:
        k_list.append([s[k_left] - s[j-1], s[-1]-s[k_left]])
    if k_left != n-2:
        k_list.append([s[k_left+1] - s[j-1], s[-1]-s[k_left+1]])
    for i in i_list:
        for k in k_list:
            tmp = max(i+k)-min(i+k)
            ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right as br
N = int(input())
A = [int(a) for a in input().split()]
s = sum(A)
S = [0] * (N+1)
for i in range(N):
    S[i+1] = S[i] + A[i]

mi = 1<<100
for i in range(1, N-1):
    sl = S[i]
    sr = s - sl
    a = br(S, sl//2)
    b = br(S, sl + sr//2)
    L = [S[a], S[i]-S[a], S[b]-S[i], s-S[b]]
    mi = min(mi, max(L) - min(L))
    L = [S[a], S[i]-S[a], S[b-1]-S[i], s-S[b-1]]
    mi = min(mi, max(L) - min(L))
    if a-1 >= 0:
        L = [S[a-1], S[i]-S[a-1], S[b]-S[i], s-S[b]]
        mi = min(mi, max(L) - min(L))
        L = [S[a-1], S[i]-S[a-1], S[b-1]-S[i], s-S[b-1]]
        mi = min(mi, max(L) - min(L))

print(mi)

Submission status: Accepted

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
AA=[A[0]]
for i in range(1,n):
  AA.append(AA[-1]+A[i])
tot=AA[-1]
import bisect
ans=float("inf")
for i in range(1,n-2):
  cur=AA[i]
  l=bisect.bisect_left(AA,cur//2)
  if l==0:
    L1=[0,float("inf")]
  else:
    L1=[AA[l-1],cur-AA[l-1]]
  L2=[AA[l],cur-AA[l]]
  
  r=bisect.bisect_left(AA,cur+(tot-cur)//2)
  if r-1==i:
    R1=[0,float("inf")]
  else:
    R1=[AA[r-1]-cur,tot-AA[r-1]]
  R2=[AA[r]-cur,tot-AA[r]]
  A11=L1+R1
  A12=L1+R2
  A21=L2+R1
  A22=L2+R2
  a11=max(A11)-min(A11)
  a12=max(A12)-min(A12)
  a21=max(A21)-min(A21)
  a22=max(A22)-min(A22)

  ans=min(ans,a11,a12,a21,a22)
print(ans)

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)

Submission status: Accepted

Solution code:
#editorial
#累積和と尺取り
n = int(input())
a = list(map(int, input().split( )))
asum = 0
a_sum = []
for i in range(n):
    asum += a[i]
    a_sum.append(asum)


j = 1
k = 3

b = a[0]
c = a[1]
d = a[2]
e = asum-b-c-d

ans = asum

for i in range(2,n):
    while abs(b+a[j] -(c-a[j]))<=abs(b-c) and j<i:
        #a>0なのでjがiを超えることはない
        b+=a[j]
        c-=a[j]
        j+=1
    while abs(d+a[k] -(e-a[k]))<=abs(d-e) and k<n-1:
        d += a[k]
        e -= a[k]
        k+=1
    #print(b,c,d,e,max(b,c,d,e),min(b,c,d,e),ans)
    ans = min(ans, max(b,c,d,e)-min(b,c,d,e))
    c += a[i]
    d -= a[i]
    
print(ans)

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def f(x,y,i):
        p = [a[x],a[i-1]-a[x],b[y],b[-i-1]-b[y]]
        if 0 in p:
            return float("inf")
        return max(p)-min(p)

    n = I()
    a = LI()
    b = [a[i] for i in range(n)]
    for i in range(n-1):
        a[i+1] += a[i]
    for i in range(n-1)[::-1]:
        b[i] += b[i+1]
    b.sort()
    ans = float("inf")
    for i in range(2,n-1):
        l = a[i-1]
        r = b[-1-i]
        li = bisect.bisect_left(a,l/2)
        ri = bisect.bisect_left(b,r/2)
        for x in range(max(li-1,0),min(li+2,i-1)):
            for y in range(max(ri-1,0),min(ri+2,n-i-1)):
                ans = min(f(x,y,i),ans)
    print(ans)
    return

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
A = np.array(read().split(),np.int64)

Acum = A.cumsum(); S = Acum[-1]
Acum2 = Acum+Acum
I1 = np.searchsorted(Acum2,Acum)
P1 = Acum[I1]; Q1 = Acum-P1
P2 = P1 - A[I1]; Q2 = P1+Q1-P2
P = np.where(np.abs(P1-Q1) > np.abs(P2-Q2),P2,P1); Q = P1+Q1-P

A = A[::-1]
Acum = A.cumsum(); S = Acum[-1]
Acum2 = Acum+Acum
I1 = np.searchsorted(Acum2,Acum)
P1 = Acum[I1]; Q1 = Acum-P1
P2 = P1 - A[I1]; Q2 = P1+Q1-P2
R = np.where(np.abs(P1-Q1) > np.abs(P2-Q2),P2,P1); S = P1+Q1-R

R = R[::-1]; S = S[::-1]

P,Q,R,S = P[:-1],Q[:-1],R[1:],S[1:]

PQRS = np.vstack([P,Q,R,S])

PQRS

score = np.max(PQRS,axis=0) - np.min(PQRS,axis=0)
answer = score.min()
print(answer)

Submission status: Accepted

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

S = [0]

for a in A:
    S += [ S[-1] + a ]

l = 0
r = 2
ans = float('inf') 

for i in range(1, N-1):
    while S[i] - S[l+1] > S[l]:
        l += 1

    while S[N] - S[r+1] > S[r] - S[i]:
        r += 1

    a = S[l]
    b = S[i] - S[l]
    c = S[r] - S[i]
    d = S[N] - S[r]
  
    ans = min(ans, max(a,b,c,d) - min(a,b,c,d))
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

N = int(input())
A = [int(i) for i in input().split()]

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

ret = float('inf')
for b in range(1, N - 1) :
    a = bisect_left(A, A[b] / 2)
    c = bisect_left(A, A[b] + (s - A[b]) / 2)
    for i in [a - 1, a] :
        for j in [c - 1, c] :
            if not 0 <= i < b < j < N - 1 :
                continue
            cut = [A[i], A[b] - A[i], A[j] - A[b], s - A[j]]
            ret = min(ret, max(cut) - min(cut))
            
print(ret)

Submission status: Accepted

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

cumsum_A = []
cumsum = 0
for a in A:
    cumsum += a
    cumsum_A.append(cumsum)

ans = float('INF')
left = 0
right = 2

for center in range(1, n-2):
    ll_value = cumsum_A[left]
    lc_value = cumsum_A[center] - ll_value
    cr_value = cumsum_A[right] - cumsum_A[center]
    rr_value = cumsum_A[-1] - cumsum_A[right]

    while abs(ll_value - lc_value) > abs(ll_value - lc_value + 2*A[left+1]):
        if left == center - 1:
            break
        left += 1
        ll_value += A[left]
        lc_value -= A[left]

    while abs(cr_value - rr_value) > abs(cr_value - rr_value + 2 * A[right + 1]):
        if right == n - 2:
            break
        right += 1
        cr_value += A[right]
        rr_value -= A[right]

    candidate = max(ll_value, lc_value, cr_value, rr_value) - min(ll_value, lc_value, cr_value, rr_value)
    ans = min(ans, candidate)

print(ans)

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
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    if n % 2:
        print(2 * n)
    else:
        print(n)
    return

#B
def B():
    n = II()
    a = LI()
    a.sort()
    print(a[n-1]-a[0])
    return

#C
def C():
    return

# D
# 解説AC
# BCDEのC,Dの仕切り位置を右に移動させていくと
# B,CとD,Eの仕切り位置について右にしか移動しないこと
# がわかれば終わりだった。
# わかりたい
def D():
    n = II()
    a = LI()
    for i in range(n - 1):
        a[i + 1] += a[i]
    l, r = 0, 0
    ans = inf
    for center in range(1, n - 2):
        r = max(r, center + 1)
        while center - l > 1:
            if abs(a[center] - 2 * a[l]) > abs(a[center] - 2 * a[l + 1]):
                l += 1
            else:
                break
        while n - 1 - r > 1:
            if abs(a[n - 1] - a[r] - (a[r] - a[center])) > abs(a[n - 1] - a[r + 1] - (a[r + 1] - a[center])):
                r += 1
            else:
                break
        b = a[l]
        c = a[center] - a[l]
        d = a[r] - a[center]
        e = a[n - 1] - a[r]
        ans = min(ans, max(b, c, d, e) - min(b, c, d, e))
    print(ans)

        
    return

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

Submission status: Accepted

Solution code:
#解説解法
#15:49
n = int(input())
a = list(map(int,input().split()))
b = [a[0]]
for i in range(1,n):
  b.append(b[-1] + a[i])
c = []
for i in range(n):
  c.append([abs(b[i] - b[-1]/2),i])
h = -1
j = min(c,key= lambda x:x[0])[1]
p = 0
q = 0
r = b[j]
s = b[-1] - r
#print(p,q,r,s)
can = []
for i in range(n-2):
  q += a[i]
  while True:
    pnew = p + a[h+1]
    qnew = q - a[h+1]
    if abs(pnew-qnew) < abs(p-q):
      h += 1
      p = pnew
      q = qnew
    else:
      break
  r -= a[i]
  while True:
    rnew = r + a[j+1]
    snew = s - a[j+1]
    if abs(rnew-snew) < abs(r-s):
      j += 1
      r = rnew
      s = snew
    else:
      break
  if 1 <= i < n-2:
    can.append(max(p,q,r,s) - min(p,q,r,s))
    #print(p,q,r,s)
#print(can)
print(min(can))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = list(accumulate(LI() + [0]))
ret = INF
for second_point in range(2, n-1):
    left_sum = L[second_point - 1]
    right_sum = L[-1] - left_sum
    if L[bisect_left(L, left_sum/2)] - left_sum/2 < left_sum/2 - L[bisect_left(L, left_sum/2) - 1] or not bisect_left(L, left_sum/2):
        p = L[bisect_left(L, left_sum/2)]
    else:
        p = L[bisect_left(L, left_sum/2) - 1]
    q = left_sum - p
    if L[bisect_left(L, left_sum + right_sum/2)] - right_sum/2 - left_sum < left_sum + right_sum/2 - L[bisect_left(L, left_sum + right_sum/2) - 1]:
        s = L[-1] - L[bisect_left(L, left_sum + right_sum/2)]
    else:
        s = L[-1] - L[bisect_left(L, left_sum + right_sum/2) - 1]
    r = right_sum - s
    ret = min(ret, max(p, q, r, s) - min(p, q, r, s))


print(ret)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import accumulate
from bisect import bisect
n = int(input())
a = list(map(int, input().split()))
ans = 10**9
cs = [0] + list(accumulate(a))
for i in range(2, n - 1):
    left = cs[i]
    right = cs[-1] - cs[i]
    lm = bisect(cs, left // 2)
    l1, l2 = cs[lm], left - cs[lm]
    l3, l4 = cs[lm - 1], left - cs[lm - 1]
    if abs(l1 - l2) > abs(l3 - l4):
        l1 = l3
        l2 = l4
    rm = bisect(cs, left + right // 2)
    r1, r2 = cs[rm] - cs[i], right - (cs[rm] - cs[i])
    r3, r4 = cs[rm - 1] - cs[i], right - (cs[rm - 1] - cs[i])
    if abs(r1 - r2) > abs(r3 - r4):
        r1 = r3
        r2 = r4
    ans = min(ans, max(l1, l2, r1, r2) - min(l1, l2, r1, r2))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int,input().split()))
sum_a = [0]
for i in range(N):
  sum_a.append(As[i]+sum_a[i])
ans = float('inf')
p,q = 0,2
for cut in range(2,N-1):
  while p < cut-1:
    if abs(sum_a[cut]-sum_a[p]*2) >= abs(sum_a[cut]-sum_a[p+1]*2):
      p += 1
    else:
      break
      
  while q < N-1:
    if abs(sum_a[N]-sum_a[q]-(sum_a[q]-sum_a[cut])) >= abs(sum_a[N]-sum_a[q+1]-(sum_a[q+1]-sum_a[cut])):
      q += 1
    else:
      break
      
  ls = [sum_a[N]-sum_a[q],sum_a[q]-sum_a[cut],sum_a[cut]-sum_a[p],sum_a[p]]
  ans = min(ans,max(ls)-min(ls))
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]
j = 0
k = 2
ans = 10**9

# j, i, k(の右側)で区切る
# iを一旦固定して、j, kをそれぞれ右へ移動させる
# iの取り得る値は1〜N-3(N-2の手前)
for i in range(1, N-2):
    while abs(a[j]*2-a[i]) > abs(a[j+1]*2-a[i]):
    # a[j]-(a[i]-a[j]) A:B:C:DのA-B
    # a[j+1]-(a[i]-a[j-1]) A:B:C:DのA-B
    # A-Bが最小となるjを探す
        j += 1
    
    while abs(a[k]*2-a[i]-a[N-1]) > abs(a[k+1]*2-a[i]-a[N-1]):
    # (a[k]-a[i])-(a[N-1]-a[k]) A:B:C:DのC-D
    # (a[k+1]-a[i])-(a[N-1]-a[k+1]) A:B:C:DのC-D
    # C-Dが最小となるkを探す
        k += 1
    
    # 順にA, B, C, Dを出す
    t=[a[j], a[i]-a[j], a[k]-a[i], a[N-1]-a[k]]
    ans = min(ans, max(t)-min(t))

print(ans)

Submission status: Accepted

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

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

j=0
k=2
ans=10**9

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]]
    ans=min(ans,max(t)-min(t))
print(ans)

Submission status: Accepted

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

from itertools import accumulate

s = list(accumulate(a))
#s = [a[0]]
#for i in range(1, n):
#    s.append(a[i] + s[i-1])

l = 0
r = 2
ans = float("inf")

for m in range(1, n-1):
    while l < m - 1 and abs(s[m] - 2 * s[l]) > abs(s[m] - 2 * s[l+1]):
        l += 1
    while r <= m or r < n - 1 and abs(s[n-1] - 2 * s[r] + s[m]) > abs(s[n-1] - 2 * s[r+1] + s[m]):
        r += 1
    mx = max(s[l], s[m] - s[l], s[r] - s[m], s[n-1] - s[r])
    mn = min(s[l], s[m] - s[l], s[r] - s[m], s[n-1] - s[r])
    ans = min(ans, mx - mn)

print(ans)

Submission status: Accepted

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

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

l = 0
r = 2
ans = float("inf")

for m in range(1, n-1):
    while l < m - 1 and abs(s[m] - 2 * s[l]) > abs(s[m] - 2 * s[l+1]):
        l += 1
    while r <= m or r < n - 1 and abs(s[n-1] - 2 * s[r] + s[m]) > abs(s[n-1] - 2 * s[r+1] + s[m]):
        r += 1
    mx = max(s[l], s[m] - s[l], s[r] - s[m], s[n-1] - s[r])
    mn = min(s[l], s[m] - s[l], s[r] - s[m], s[n-1] - s[r])
    ans = min(ans, mx - mn)

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc102/tasks/arc100_b

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    al = list(map(int, input().split()))

    l, c, r = 1, 2, 3
    P = sum(al[:l])
    Q = sum(al[l:c])
    R = sum(al[c:r])
    S = sum(al[r:])

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

    while c <= n - 2:
        while True:
            if l == c - 1:
                break
            if abs(P - Q) < abs((P + al[l]) - (Q - al[l])):  # これ以上差が縮まらないなら break
                break

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

        while True:
            if r == n - 1:
                break
            if abs(R - S) < abs((R + al[r]) - (S - al[r])): # これ以上差が縮まらないなら break
                break

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

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

        # center を一つ右に進める
        Q += al[c]
        R -= al[c]
        c += 1

    print(ans)

if __name__ == '__main__':
    main()