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: Time Limit Exceeded

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

# 区間の和を高速に求めたいので累積和
S = [0]*N
S[0] = A[0]
for i in range(1,N):
    S[i] = S[i-1]+A[i]

Ans = 10**15
# 真ん中の分割位置を全探索
for i in range(2,N-1):
    # 前半と後半に分離
    A,B = S[:i],S[i:]
    sumA,sumB = S[i-1],S[N-1]-S[i-1]
    canA,canB = [],[]
    # 前半部分,後半部分をそれぞれできるだけ均等になるように分割
    ax = S[i-1]/2
    ai = bisect(S,ax)
    if abs(S[ai-1]-ax) < abs(S[ai]-ax):
        ai -= 1
    bx = (S[N-1]+S[i-1])/2
    bi = bisect(S,bx)
    if abs(S[bi-1]-bx) < abs(S[bi]-bx):
        bi -= 1
    x1,x2,x3,x4 = S[ai],S[i-1]-S[ai],S[bi]-S[i-1],S[N-1]-S[bi]
    # 考慮した組み合わせで最小のものを記録
    Ans = min(Ans,max(x1,x2,x3,x4)-min(x1,x2,x3,x4))

print(Ans)

Submission status: Time Limit Exceeded

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

# 区間の和を高速に求めたいので累積和
S = [0]*N
S[0] = A[0]
for i in range(1,N):
    S[i] = S[i-1]+A[i]

Ans = 10**15
D = [0,1]
# 真ん中の分割位置を全探索
for i in range(2,N-1):
    # 前半と後半に分離
    A,B = S[:i],S[i:]
    sumA,sumB = S[i-1],S[N-1]-S[i-1]
    canA,canB = [],[]
    # 前半部分,後半部分をそれぞれできるだけ均等になるように分割
    ai = bisect_left(A,sumA/2)
    bi = bisect_left(B,sumB/2+A[-1])
    # 2分探索で分割位置を求め、その次の要素を含める・含めないの2通り考慮する
    for d in D:
        a1 = A[ai-d]
        a2 = A[i-1]
        canA.append((a1,a2))
    for d in D:
        b1 = B[bi-d]
        b2 = B[-1]
        canB.append((b1,b2))
    # 考慮した組み合わせで最小のものを記録
    for a in canA:
        for b in canB:
            x1,x2,x3,x4 = a[0],a[1],b[0],b[1]
            Ans = min(Ans,max(x1,x2-x1,x3-x2,x4-x3)-min(x1,x2-x1,x3-x2,x4-x3))

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
from time import time

st_time = time()
N = int(input())
src = list(map(int,input().split()))

cums = [0]
for a in src:
    cums.append(cums[-1] + a)

ans = cums[-1] * 999
c = bisect(cums, cums[-1]//2)
d = 1
while time() - st_time < 1.85:
    if abs(d) >= N: break
    if 2 <= c <= N-2:
        b1 = bisect(cums[:c], cums[c]//2)
        b2 = bisect(cums[c:], (cums[c]+cums[-1])//2) + c
        pq_cands = []
        for i in (b1,b1-1):
            if not 0 < i < c: continue
            p = cums[i]
            q = cums[c] - cums[i]
            pq_cands.append((p,q))
        rs_cands = []
        for i in (b2,b2-1):
            if not c < i < N: continue
            r = cums[i] - cums[c]
            s = cums[-1] - cums[i]
            rs_cands.append((r,s))
        for p,q in pq_cands:
            for r,s in rs_cands:
                mn = min(p,q,r,s)
                mx = max(p,q,r,s)
                ans = min(ans, mx-mn)
    c += d
    d = (abs(d)+1) * [1,-1][d%2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
from time import time

st_time = time()
N = int(input())
src = list(map(int,input().split()))

cums = [0]
for a in src:
    cums.append(cums[-1] + a)

ans = cums[-1] * 999
c = bisect(cums, cums[-1]//2)
d = 1
while time() - st_time < 1.9:
    if abs(d) >= N: break
    if 2 <= c <= N-2:
        b1 = bisect(cums[:c], cums[c]//2)
        b2 = bisect(cums[c:], (cums[c]+cums[-1])//2) + c
        pq_cands = []
        for i in (b1,b1-1):
            if not 0 < i < c: continue
            p = cums[i]
            q = cums[c] - cums[i]
            pq_cands.append((p,q))
        rs_cands = []
        for i in (b2,b2-1):
            if not c < i < N: continue
            r = cums[i] - cums[c]
            s = cums[-1] - cums[i]
            rs_cands.append((r,s))
        for p,q in pq_cands:
            for r,s in rs_cands:
                mn = min(p,q,r,s)
                mx = max(p,q,r,s)
                ans = min(ans, mx-mn)
    c += d
    d = (abs(d)+1) * [1,-1][d%2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
from time import time

st_time = time()
N = int(input())
src = list(map(int,input().split()))

cums = [0]
for a in src:
    cums.append(cums[-1] + a)

ans = cums[-1] * 999
c = bisect(cums, cums[-1]//2)
d = 1
while time() - st_time < 1.94:
    if abs(d) >= N: break
    if 2 <= c <= N-2:
        b1 = bisect(cums[:c], cums[c]//2)
        b2 = bisect(cums[c:], (cums[c]+cums[-1])//2) + c
        pq_cands = []
        for i in (b1,b1-1):
            if not 0 < i < c: continue
            p = cums[i]
            q = cums[c] - cums[i]
            pq_cands.append((p,q))
        rs_cands = []
        for i in (b2,b2-1):
            if not c < i < N: continue
            r = cums[i] - cums[c]
            s = cums[-1] - cums[i]
            rs_cands.append((r,s))
        for p,q in pq_cands:
            for r,s in rs_cands:
                mn = min(p,q,r,s)
                mx = max(p,q,r,s)
                ans = min(ans, mx-mn)
    c += d
    d = (abs(d)+1) * [1,-1][d%2]
print(ans)

Submission status: Time Limit Exceeded

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

l = 1
r = 3
w = a[0]
x = a[1]
y = a[2]
z = sum(a[3:])
result = max(w,x,y,z) - min(w,x,y,z)

for i in range(2, n - 1):
    if r == i:
        r += 1
    w = sum(a[:l])
    x = sum(a[l:i])
    res_l = abs(w - x)
    y = sum(a[i:r])
    z = sum(a[r:])
    res_r = abs(y - z)
    temp = l
    while temp < i:
        p = sum(a[:temp])
        q = sum(a[temp:i])
        sum_temp = abs(q - p)
        if sum_temp < res_l:
            res_l = sum_temp
            l = temp
            w = p
            x = q
        if p >= q:
            break
        temp += 1
    temp = r
    while temp < n:
        p = sum(a[i:temp])
        q = sum(a[temp:])
        sum_temp = abs(q - p)
        if sum_temp < res_r:
            res_r = sum_temp
            r = temp
            y = p
            z = q
        if p >= q:
            break
        temp += 1
    temp_res = max(w,x,y,z) - min(w,x,y,z)
#    print(temp_res, w, x, y, z, l, i, r)
    if temp_res < result:
        result = temp_res

print(result)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
n = int(input())
nums = list(map(int,input().split()))  

def check(a,b):
    sums = [0 for i in range(b-a+1)]
    sums[0]  = nums[a]
    for i in range(b-a):
        sums[i+1] = sums[i] + nums[a+i+1]
    i = 0
    while 2 * sums[i] < sums[-1]:
        i += 1
    if abs(2 * sums[i] - sums[-1]) >= abs(sums[-1] - 2 * sums[i-1]):
        A = sums[i-1]
        B = sums[-1] - sums[i-1]
    else:
        A = sums[i]
        B =sums[-1] - sums[i]
    return A,B


minv = 1000000000000
for mid in range(1,n-1):
    P,Q = check(0,mid-1)
    R,S = check(mid,n-1)
    List = [P,Q,R,S]
    minv = min(minv, max(List) - min(List))

print(minv)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
#N = 5
#A = list(map(int,"3 2 4 1 2".split()))
AA = [0  for x in range(N)]
for i,a in enumerate(A):
    AA[i] = sum(A[:i]) + a
ans = 99999999999999999
ed = 2
st = 0
_bc = AA[-1]
_de = AA[-1]
for i in range(1,N-2):
    for j in range(st,i):
        B = AA[j]
        C = AA[i] - AA[j]
        if abs(B -C) <= _bc:
            _bc = abs(B -C)
        else:
            st = j -1
            _bc = abs(2 * AA[j-1] - AA[i+1])
            B = AA[j-1]
            C = AA[i] - AA[j-1]
            break
    for k in range(ed,N-1):
        D = AA[k] - AA[i]
        E = AA[-1] - AA[k]
        if _de >= abs(D-E):
            _de = abs(D-E)
        else:
            ed = k 
            _de = abs(2 * AA[k-1] - AA[i+1] -AA[-1])
            D = AA[k-1] - AA[i]
            E = AA[-1] - AA[k-1]
            break
    sample = max([abs(B-C),abs(B-D),abs(B-E),abs(C-D),abs(C-E),abs(D-E)])
    if ans > sample:
        ans = sample
        #print(ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def section_sum(a, b):
    return acc[b] - acc[a]


def minimize(s2):
    lsum = float("inf")
    for s1 in range(1, s2):
        if abs(section_sum(0, s1) - section_sum(s1, s2)) < lsum:
            q = section_sum(0, s1)
            r = section_sum(s1, s2)
            lsum = abs(q - r)
        else:
            break

    rsum = float("inf")
    for s3 in range(s2, len(a)):
        if abs(section_sum(s2, s3) - section_sum(s3, len(a))) < rsum:
            s = section_sum(s2, s3)
            t = section_sum(s3, len(a))
            rsum = abs(s - t)
        else:
            break

    cut = [q, r, s, t]
    return abs(min(cut) - max(cut))


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

acc = [0]
for x in a:
    acc.append(acc[-1] + x)


ans = float("inf")
for s2 in range(2, len(a) - 1):
    ans = min(ans, minimize(s2))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from bisect import bisect_left

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

def helper(i,j):
  m = (C[j]+C[i])/2
  k = bisect_left(C, m, lo=i+1,hi=j-1)

  if k > i+1:
    _,a,b = min((abs(m-C[x]),C[x]-C[i],C[j]-C[x]) for x in (k-1,k))
  else:
    a,b = C[k]-C[i],C[j]-C[k]
  return a,b


m = bisect_left(C,C[N]/2)
if m < 2:
  m = 2
elif m > N-2:
  m = N-2

L = helper(0,m)+helper(m,N)
best = max(L)-min(L)

i = m+1
while i < N-1 and abs(abs(C[N]-C[i])-abs(C[i])) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i += 1

i = m-1
while i > 1 and abs(abs(C[N]-C[i])-abs(C[i])) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i -= 1


print(best)

Submission status: Time Limit Exceeded

Solution code:
inf = float("inf")

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

SU = sum(A)

bb = inf
for B in range(1, N - 2):
    P = sum(A[:B])
    for C in range(B + 1, N - 1):
        Q = sum(A[B:C])
        if abs(P - Q) > bb:
            continue
        for D in range(C + 1, N):
            R = sum(A[C:D])
            S = SU - (P + Q + R)
            bb = min(bb, max(P,Q,R,S) - min(P,Q,R,S))
print(bb)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = 10**10
indexm = 0
indexl = 0
indexr = 0
for index in range(2, n - 1):
    for i in range(1, index):
        for j in range(index + 1, n):
            t = [sum(a[index:j]), sum(a[j:]), sum(a[:i]), sum(a[i:index])]
            if m > abs(max(t) - min(t)):
                m = abs(max(t) - min(t))
                indexm = index
                indexl = i
                indexr = j
ans = sorted([sum(a[:indexl]),sum(a[indexl:indexm]),sum(a[indexm:indexr]),sum(a[indexr:])])
print(ans[3] - ans[0])

Submission status: Time Limit Exceeded

Solution code:
inf = float("inf")

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

bb = inf
for B in range(1, N - 2):
    for C in range(B + 1, N - 1):
        for D in range(C + 1, N):
            P = sum(A[:B])
            Q = sum(A[B:C])
            R = sum(A[C:D])
            S = sum(A[D:])
            bb = min(bb, max(P,Q,R,S) - min(P,Q,R,S))
print(bb)

Submission status: Time Limit Exceeded

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

def helper(i,j):
  m = (C[j]+C[i])/2
  k = bisect(C, m, lo=i,hi=j)
  if k == i:
    k += 1
  elif k == j:
    k -= 1

  if k > 0:
    _,a,b = min((abs(m-C[x]),C[x]-C[i],C[j]-C[x]) for x in (k-1,k))
  else:
    a,b = C[k]-C[i],C[j]-C[k]

  return a,b

m = bisect(C,C[N]/2)
if m < 2:
  m = 2
elif m > N-2:
  m = N-2

L = helper(0,m)+helper(m,N)
best = max(L)-min(L)
i = m+1
while i < N-1 and (2*C[i]-C[N]) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i += 1
i = m-1
while i > 1 and (C[N]-2*C[i]) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i -= 1


print(best)

Submission status: Time Limit Exceeded

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

minv = -1
for i in range(0, len(a) - 2):
    for j in range(i + 1, len(a) - 1):
        for k in range(j + 1, len(a) - 0):
                p = sum(a[:i])
                q = sum(a[i:j])
                r = sum(a[j:k])
                s = sum(a[k:])
                v = max(p, q, r, s) - min(p, q, r, s)
                if minv == -1 or v < minv:
                    minv = v
print(minv)

Submission status: Time Limit Exceeded

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

def helper(i,j):
  m = (C[j]+C[i])/2
  k = bisect(C, m, lo=i,hi=j)
  if k == i:
    k += 1
  elif k == j:
    k -= 1

  if k > 0:
    _,a,b = min((abs(m-C[x]),C[x]-C[i],C[j]-C[x]) for x in (k-1,k))
  else:
    a,b = C[k]-C[i],C[j]-C[k]

  return a,b

best = float('inf')

for i in range(2,N-1):
  L = helper(0,i)+helper(i,N)
  best = min(best,max(L)-min(L))

print(best)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect, bisect_left
from itertools import accumulate, product

N = int(input())
A = list(map(int, input().split()))
S = list(accumulate(A))
T = sum(A)
ans = 10**16

for j in range(1, N-1):
    PQ = S[j]
    RS = T - S[j]
    #print("PQ RS", PQ, RS)
    
    i1 = bisect(S, PQ/2) - 1
    i2 = bisect_left(S, PQ/2)
    
    k1 = bisect(S, RS/2 + PQ) - 1
    k2 = bisect_left(S, RS/2 + PQ)
    
    for i, k in product([i1, i2], [k1, k2]):
        #print(i, j, k)
        if i < 0 or i==j or j == k or k == N-1:
            continue
        PQRS = [S[i], S[j] - S[i], S[k] - S[j], T - S[k]]
        #print(PQRS)
        ans = min(ans, abs(max(PQRS) - min(PQRS)))

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
D=[0]
d=0
for i in A:
  d+=i
  D.append(d)
s=D[-1]
D=D[1:-1]
d=s
import bisect
for i in range(1,len(D)-1):
  a=D[i]/2
  b=(D[i]+s)/2
  l=bisect.bisect_left(D,a)
  r=bisect.bisect_left(D,b)
  L,R=[],[]
  if l-1<i:
    L.append(l-1)
  if r-1<len(D):
    R.append(r-1)
  if l<i:
    L.append(l)
  if r<len(D):
    R.append(r)
  for j in L:
    for k in R:
      mi=min(s-D[k],D[k]-D[i],D[i]-D[j],D[j])
      ma=max(s-D[k],D[k]-D[i],D[i]-D[j],D[j])
      d=min(d,ma-mi)
print(d)

Submission status: Accepted

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

SUM = sum(A)
left = 0
right = 0
L = 0
M = 0
R = 0

ans = float('inf')

for mid in range(N):
    while abs(M - 2 * L) > abs(M - 2 * L - 2 * A[left]):
        L += A[left]
        left += 1
    
    while right < N and abs(SUM + M - 2 * R) > abs(SUM + M - 2 * R - 2 * A[right]):
        R += A[right]
        right += 1
    
    ans = min(ans, max(L, M - L, R - M, SUM - R) - min(L, M - L, R - M, SUM - R))
    
    M += A[mid]

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
tmp=0
ca=[tmp]
for x in a:
  tmp+=x
  ca.append(tmp)
ans=float('inf')
bidx=0
cidx=1
didx=2
eidx=3

for didx in range(1,n-1):
  p=ca[cidx]-ca[bidx]
  q=ca[didx]-ca[cidx]
  r=ca[eidx]-ca[didx]
  s=ca[-1]-ca[eidx]
  
  np=ca[cidx+1]-ca[bidx]
  nq=ca[didx]-ca[cidx+1]
  while cidx+1<didx and abs(p-q)>abs(np-nq):
    cidx+=1
    p,q=np,nq
    np=ca[cidx+1]-ca[bidx]
    nq=ca[didx]-ca[cidx+1]

  nr=ca[eidx+1]-ca[didx]
  ns=ca[-1]-ca[eidx+1]
  while eidx+1<n and abs(r-s)>abs(nr-ns):
    eidx+=1
    r,s=nr,ns
    nr=ca[eidx+1]-ca[didx]
    ns=ca[-1]-ca[eidx+1]

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

Submission status: Accepted

Solution code:
import bisect
import itertools
N = int(input())
A = [int(_) for _ in input().split()]
cum = list(itertools.accumulate(A))
ans = 10**10
for i2 in range(1, N - 2):
    i1 = i = bisect.bisect_left(cum, cum[i2] // 2)
    c = abs(cum[i2] - 2 * cum[i1])
    for j in range(i - 1, i + 2):
        if 0 <= j < i2 and abs(cum[i2] - 2 * cum[j]) < c:
            i1 = j
            c = abs(cum[i2] - 2 * cum[j])
    i3 = i = bisect.bisect_left(cum, (cum[i2] + cum[N - 1]) // 2)
    c = abs(cum[N - 1] + cum[i2] - 2 * cum[i3])
    for j in range(i - 1, i + 2):
        if i2 < j < N - 1 and abs(cum[N - 1] + cum[i2] - 2 * cum[j]) < c:
            i3 = j
            c = abs(cum[N - 1] + cum[i2] - 2 * cum[j])
    B = [cum[i1], cum[i2] - cum[i1], cum[i3] - cum[i2], cum[N - 1] - cum[i3]]
    ans = min(ans, max(B) - min(B))
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

csum = list(accumulate(As, initial=0))

P_end = 1
R_end = 3
ans = 10 ** 18
for Q_end in range(2, N - 1):
    former_half = csum[Q_end] / 2
    latter_half = (csum[-1] - csum[Q_end]) / 2
    while P_end + 1 <= Q_end and csum[P_end + 1] < former_half:
        P_end += 1
    while R_end + 1 < N and csum[R_end + 1] - csum[Q_end] < latter_half:
        R_end += 1
    
    if abs(csum[P_end] - former_half) > abs(csum[P_end + 1] - former_half):
        P = csum[P_end + 1]
    else:
        P = csum[P_end]
    Q = csum[Q_end] - P

    if abs(csum[R_end] - csum[Q_end] - latter_half) > abs(csum[R_end + 1] - csum[Q_end] - latter_half):
        R = csum[R_end + 1] - csum[Q_end]
        S = csum[-1] - csum[R_end + 1]
    else:
        R = csum[R_end] - csum[Q_end]
        S = csum[-1] - csum[R_end]

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

print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    ans = 10**15
    from itertools import accumulate
    S = list(accumulate([0] + A))
    idx = [1, 2, 3]
    for center in range(2, N-1):
        idx[1] = center
        P_sum = S[idx[0]] - S[0]
        Q_sum = S[idx[1]] - S[idx[0]]
        mae_diff = abs(P_sum - Q_sum)
        while idx[0] < center - 1 and \
                abs((P_sum + A[idx[0]]) - (Q_sum - A[idx[0]])) < mae_diff:
            idx[0] += 1
            P_sum = S[idx[0]] - S[0]
            Q_sum = S[idx[1]] - S[idx[0]]
            mae_diff = abs(P_sum - Q_sum)

        R_sum = S[idx[2]] - S[idx[1]]
        S_sum = S[N] - S[idx[2]]
        usi_diff = abs(R_sum - S_sum)
        while idx[2] < N and \
                abs((R_sum + A[idx[2]]) - (S_sum - A[idx[2]])) < usi_diff:
            idx[2] += 1
            R_sum = S[idx[2]] - S[idx[1]]
            S_sum = S[N] - S[idx[2]]
            usi_diff = abs(R_sum - S_sum)

        ans = min(ans, abs(max(P_sum, Q_sum, R_sum, S_sum) -
                           min(P_sum, Q_sum, R_sum, S_sum)))
        if idx[1] + 1 == idx[2]:
            idx[2] += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import bisect
N = int(input())
A = list(map(int,input().split()))

P = A[0]
Q = A[1]
Lsum = P+Q
Ldiff = abs(P-Q)
Li = 1
Rsum = sum(A) - Lsum
R = A[2]
S = Rsum - R
Rdiff = abs(R-S)
Ri = 3
while abs(R-S+2*A[Ri]) < Rdiff:
    R += A[Ri]
    S -= A[Ri]
    Ri += 1
    Rdiff = abs(R-S)
 
def diff(x):
    x.sort()
    return x[-1] - x[0]

ans = diff([P,Q,R,S])
for i in range(3, N-1):
    Q += A[i-1]
    R -= A[i-1]
    Ldiff = abs(P-Q)
    Rdiff = abs(R-S)
    while abs(P-Q+2*A[Li]) < Ldiff:
        P += A[Li]
        Q -= A[Li]
        Li += 1
        Ldiff = abs(P-Q)
    while abs(R-S+2*A[Ri]) < Rdiff:
        R += A[Ri]
        S -= A[Ri]
        Ri += 1
        Rdiff = abs(R-S)
    ans = min(ans, diff([P,Q,R,S]))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
ren=[0]*n
ren[0]= A[0]
for i in range(n-1):
    ren[i+1]= ren[i]+ A[i+1]
import bisect as bi
ans=float("inf")
for cen in range(1, n-2):
    maru= ren[cen]
    a=ren[bi.bisect(ren, maru//2)-1]
    if a==ren[-1]: a=float("inf")
    b=maru-a
    c=ren[bi.bisect(ren, maru//2)]
    if c==maru: c=float("inf")
    d=maru-c
    
    e=ren[bi.bisect(ren,(maru+ren[-1])//2)-1]-maru 
    if e==0: e= float("inf")
    f=ren[-1]-e-maru
    g=ren[bi.bisect(ren,(maru+ren[-1])//2)]-maru
    if g==ren[-1]-maru: g=float("INF")
    h=ren[-1]-g-maru

    q=[max(a,b,e,f)-min(a,b,e,f), max(a,b,g,h)-min(a,b,g,h), max(c,d,e,f)-min(c,d,e,f), max(c,d,g,h)-min(c,d,g,h)]
    ans= min(ans, min(q))
    
    #print(ren)
    
    #print(a,b,c,d,e,f,g,h)
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())
from itertools import accumulate
from bisect import bisect_right
cum = list(accumulate(As))

ans = 10**18
for i in range(1, N-2):
    c = cum[i]
    l_target = c/2
    r_target = (cum[-1]+c)/2
    l_idx = bisect_right(cum, l_target)
    r_idx = bisect_right(cum, r_target)
    if abs(l_target-cum[l_idx])<=abs(l_target-cum[l_idx-1]):
        first = cum[l_idx]
    else:
        first = cum[l_idx-1]
    second = c-first
    if abs(r_target-cum[r_idx])<=abs(r_target-cum[r_idx-1]):
        third = cum[r_idx]-c
        forth = cum[-1]-cum[r_idx]
    else:
        third = cum[r_idx-1]-c
        forth = cum[-1]-cum[r_idx-1]
    lis = [first, second, third, forth]
    ans = min(ans, max(lis)-min(lis))
print(ans)

Submission status: Accepted

Solution code:
def left(i):
    s=cum[i]
    l,r=-1,i
    while(r-l>1):
        mid=(l+r)//2
        if cum[mid]>s/2:
            r=mid
        else:
            l=mid
    a,b=cum[r],cum[i]-cum[r]
    c,d=cum[l],cum[i]-cum[l]

    if (abs(b-a)<abs(c-d)):
        return a,b
    else:
        return c,d
def right(i):
    s=cum[N]-cum[i]
    l,r=i-1,N+1
    while(r-l>1):
        mid=(l+r)//2
        if cum[mid]-cum[i]>s/2:
            r=mid
        else:
            l=mid
    a,b=cum[r]-cum[i],cum[N]-cum[r]
    c,d=cum[l]-cum[i],cum[N]-cum[l]

    if (abs(b-a)<abs(c-d)):
        return a,b
    else:
        return c,d
        
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]
ans=10**30
for i in range(2,N-1):
    a,b=left(i)
    c,d=right(i)
    ans=min(ans,max([a,b,c,d])-min([a,b,c,d]))
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
from bisect import *
def calc(p,q):
  ind = bisect_right(cum,(cum[q]+cum[p])/2)
  M = cum[ind]-cum[p]
  if ind>0:
    M = min(M,cum[q]-cum[ind-1])
  m = cum[q]-cum[p] - M
  return M, m
ans = float('inf')
N = int(input())
A = list(map(int, input().split()))
cum = [0]+list(accumulate(A))
for i in range(2,N-1):
  lis = [*calc(0,i),*calc(i,N)]
  ans = min(ans,max(lis)-min(lis))
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
from bisect import *
def solve():
  ans = float('inf')
  N = int(input())
  A = list(map(int, input().split()))
  cum = list(accumulate(A))
  for i in range(1,N-2):
    mae = cum[i]
    usiro = cum[-1]-cum[i]
    ind = bisect_right(cum,mae/2)
    mae_max = min(cum[ind],mae-cum[ind-1])
    if ind==0:
      mae_max = cum[ind]
    mae_min = mae - mae_max
    ind2 = bisect_right(cum,usiro/2+cum[i])
    usiro_max = min(cum[ind2]-cum[i],cum[-1]-cum[ind2-1])
    if ind2==i+1:
      usiro_max = cum[ind2]-cum[i]
    usiro_min = usiro - usiro_max
    lis = [mae_max,mae_min,usiro_max,usiro_min]
    ans = min(ans,max(lis)-min(lis))
  return ans
print(solve())

Submission status: Accepted

Solution code:
def solution(a,b,c,d):
  return(max(a,max(b,max(c,d)))-min(a,min(b,min(c,d))))
n=int(input())
a=list(map(int,input().split()))
tot=sum(a)
pointer1=1
p=a[0]
q=a[1]
pointer2=0
s=tot-p-q
r=0
pointer2=2
while r+a[pointer2]<s-a[pointer2]:
  r+=a[pointer2]
  s-=a[pointer2]
  pointer2+=1
ans=solution(p,q,r,s)
ans=min(ans,solution(p,q,r+a[pointer2],s-a[pointer2]))
for i in range(2,n-1):
  q+=a[i]
  r-=a[i]
  while p+a[pointer1]<q-a[pointer1]:
    p+=a[pointer1]
    q-=a[pointer1]
    pointer1+=1
  while r+a[pointer2]<s-a[pointer2]:
    r+=a[pointer2]
    s-=a[pointer2]
    pointer2+=1
  ans=min(ans,solution(p,q,r,s))
  ans=min(ans,solution(p+a[pointer1],q-a[pointer1],r,s))
  ans=min(ans,solution(p+a[pointer1],q-a[pointer1],r+a[pointer2],s-a[pointer2]))
  ans=min(ans,solution(p,q,r+a[pointer2],s-a[pointer2]))
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 + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]

res = sum(a)
for m in range(1, N - 1):
  lsm = cs[m]
  rsm = cs[-1] - cs[m]
  l = bl(cs, lsm / 2)
  l -= l == m
  for i in range(l - 1, l + 2):
    if i == 0: continue
    if i == m: break
    if abs(cs[l] - (cs[m] - cs[l])) > abs(cs[i] - (cs[m] - cs[i])): l = i
  r = bl(cs, rsm // 2 + lsm)
  r -= r == N
  for i in range(r - 1, r + 2):
    if i == m: continue
    if i == N: break
    if abs(cs[-1] - cs[r] - (cs[r] - cs[m])) > abs(cs[-1] - cs[i] - (cs[i] - cs[m])): r = i
  mx = max(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r])
  mn = min(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r])
  res = min(res, mx - mn)
  #print(l, m, r, res)
print(res)