Problem:


Score : 600 points

Problem Statement

Snuke has an integer sequence A of length N.

He will make three cuts in A and divide it into four (non-empty) contiguous subsequences B, C, D and E.
The positions of the cuts can be freely chosen.

Let P,Q,R,S be the sums of the elements in B,C,D,E, respectively.
Snuke is happier when the absolute difference of the maximum and the minimum among P,Q,R,S is smaller.
Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.

Constraints

4 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.

Sample Input 1

5
3 2 4 1 2

Sample Output 1

2

If we divide A as B,C,D,E=(3),(2),(4),(1,2), then P=3,Q=2,R=4,S=1+2=3.
Here, the maximum and the minimum among P,Q,R,S are 4 and 2, with the absolute difference of 2.
We cannot make the absolute difference of the maximum and the minimum less than 2, so the answer is 2.

Sample Input 2

10
10 71 84 33 6 47 23 25 52 64

Sample Output 2

36

Sample Input 3

7
1 2 3 1000000000 4 5 6

Sample Output 3

999999994



Sample input:
5
3 2 4 1 2


Sample output:
2

Submission status: Accepted

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

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

left_min = right_min = ans = float('INF')
left_max = right_max = 0
p = 0
q = 1
r = N // 2
s = r + 1
for r in range(2, N - 1):
    # 左
    P1, Q1 = P2, Q2 = -1, -1
    low, high = 1, r - 1
    while low + 1 < high:
        mid = (low + high) // 2
        P = SUM[mid - 1]
        Q = SUM[r - 1] - SUM[mid - 1]
        if P < Q:
            low = mid
        else:
            high = mid
    P1, Q1 = SUM[low - 1], SUM[r - 1] - SUM[low - 1]
    P2, Q2 = SUM[high - 1], SUM[r - 1] - SUM[high - 1]
    left_min, left_max = min(P1, Q1), max(P1, Q1)
    if abs(Q1 - P1) > abs(Q2 - P2):
        left_min, left_max = min(P2, Q2), max(P2, Q2)

    # 右
    R1, S1 = R2, S2 = -1, -1
    low, high = r + 1, N - 1
    while low + 1 < high:
        mid = (low + high) // 2
        R = SUM[mid - 1] - SUM[r - 1]
        S = SUM[N - 1] - SUM[mid - 1]
        if R < S:
            low = mid
        else:
            high = mid
    R1, S1 = SUM[low - 1] - SUM[r - 1], SUM[N - 1] - SUM[low - 1]
    R2, S2 = SUM[high - 1] - SUM[r - 1], SUM[N - 1] - SUM[high - 1]
    right_min, right_max = min(R1, S1), max(R1, S1)
    if abs(R1 - S1) > abs(R2 - S2):
        right_min, right_max = min(R2, S2), max(R2, S2)

    # print(P1, Q1, R1, S1, sum([P1, Q1, R1, S1]), sum(A))
    # print(P2, Q2, R2, S2, sum([P2, Q2, R2, S2]), sum(A))
    # print("--------")
    ans = min(max(left_max, right_max) - min(left_min, right_min), ans)

print(ans)

Submission status: Accepted

Solution code:
from statistics import mean

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

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

left_middle = 0
right_middle = 2

ans = float('inf')

for middle in range(1, N - 2):
    left_sum = S[left_middle]
    right_sum = S[middle] - left_sum
    diff = abs(left_sum - right_sum)

    for i in range(left_middle+1, middle):
        left_sum = S[i]
        right_sum = S[middle] - left_sum
        if diff > abs(left_sum - right_sum):
            left_middle = i
            diff = abs(left_sum - right_sum)
        else:
            break
    
    left_sum = S[right_middle] - S[middle]
    right_sum = S[-1] - S[right_middle]
    diff = abs(left_sum - right_sum)

    for i in range(right_middle + 1, N):
        left_sum = S[i] - S[middle]
        right_sum = S[-1] - S[i]
        if diff > abs(left_sum - right_sum):
            right_middle = i
            diff = abs(left_sum - right_sum)
        else:
            break
    
    s1 = S[left_middle]
    s2 = S[middle] - s1
    s3 = S[right_middle] - s1 - s2
    s4 = S[-1] - s1 - s2 - s3

    score = max(s1, s2, s3, s4) - min(s1, s2, s3, s4)
    ans = min(ans, score)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = np.zeros(N + 2, dtype = np.int64)
A[1:-1] = input().split()
np.cumsum(A, out = A)
total = A[-1]
A[-1] = 10 ** 18

left = np.searchsorted(A, A/2)
P1 = A[left - 1]
P2 = A[left]

Q1, Q2 = A - P1, A - P2

np.maximum(P1, Q2, out = P1)
np.minimum(P2, Q1, out = P2)
P, Q = P1, P2
right = np.searchsorted(A, (total + A)/2)
R1 = A[right - 1] - A
R2 = A[right] - A
S1 = total - A[right - 1]
S2 = total - A[right]
np.maximum(R1, S2, out = R1)
np.minimum(R2, S1, out = R2)
R, S = R1, R2

PQRS = np.vstack([P, Q, R, S])
x = np.max(PQRS, axis = 0) - np.min(PQRS, axis = 0)
answer = (x[1: -1].min())
print (answer)

Submission status: Accepted

Solution code:
N = int(input())

#累積和で受け取る
A = [0] * N
S = 0
for i, a in enumerate(input().split()):
    S += int(a)
    A[i] = S

answer = S

#indexは最後に回収する番号
B = 0
D = 0

for C in range(1, N - 2):
    D = max(D, C + 1)
    SB = A[B]
    SC = A[C] - A[B]
    SD = A[D] - A[C]
    SE = S - A[D]
    left_score = abs(SB - SC)
    #BCの境界の調整
    while True:
        B_ = B + 1
        SB_ = A[B_]
        SC_ = A[C] - SB_
        x = abs(SB_  - SC_)
        if left_score > x:
            B, SB, SC, left_score = B_, SB_, SC_, x
            continue
        break

    right_score = abs(SE - SD)
    while True:
        D_ = D + 1
        SD_ = A[D_] - A[C]
        SE_ = S - A[D_]
        x = abs(SD_ - SE_)
        if right_score > x:
            D, SD, SE, right_score = D_, SD_, SE_, x
            continue
        break

    score = max(SB, SC, SD, SE) - min(SB, SC, SD, SE)
    answer = min(score, answer)
print (answer)

Submission status: Accepted

Solution code:
#PypyでもTLE A[:half]のような箇所が遅い？
# -->二分探索のスタート地点を変えるだけで処理すると毎回新規リストを作らなくなる

N = int(input())
A = list(map(int, input().split()))
for i in range(1, N): #累積和
    A[i] += A[i - 1]

def calc(lb, ub):
    max_num = A[ub] #右端を最大値としてとる
    lb -= 1 #左端の一個前
    if lb == -1: #一個前がない
        min_num = 0 #最小値を0とする
    else: #一個前が存在する
        min_num = A[lb] #一個前を最小値とする
    total = A[ub] - min_num #最大値 - 最小値 = この範囲のトータル
    # print (total)
    while (ub - lb) > 1: #indexの差が1より大きいとき
        mid = (lb + ub)//2 #真ん中を定める
        if A[mid] - min_num > total/2: #真ん中までの和が全体の半分を超えているとき
            ub = mid #右半分を真ん中に移動
        else: #真ん中までの和が全体の半分に満たないとき
            lb = mid #左半分を真ん中に移動
    # print ('ub', ub)

    #一番近い場所の左右でより半分に近くなる方を求めて、その値を返す
    a1, b1 = A[ub] - min_num, max_num - A[ub]
    diff1 = abs(b1 - a1)
    # print ('diff1', diff1)
    a2, b2 = A[ub - 1] - min_num, max_num - A[ub - 1]
    diff2 = abs(b2 - a2)
    # print ('diff2', diff2)
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1

# print (calc(A, 0))
# half = 2
# P, Q = calc(0, half - 1)
# print (P, Q)

ans = 10 ** 9 #大きな数を答えとしておく
for half in range(2, N - 1): #左側、右側それぞれに最低2つずつ成分を含む領域でのみ考える
    P, Q = calc(0, half - 1)
    R, S = calc(half, N - 1)
    # print (P, Q, R, S)
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    # print (tmp)
    ans = min(tmp, ans)

# print ('ans', ans)
print (ans)

Submission status: Accepted

Solution code:
#PypyでもTLE A[:half]のような箇所が遅い？

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

def calc(lb, ub):
    max_num = A[ub]
    lb -= 1
    if lb == -1:
        min_num = 0
    else:
        min_num = A[lb]
    total = A[ub] - min_num
    # print (total)
    while (ub - lb) > 1:
        mid = (lb + ub)//2
        if A[mid] - min_num > total/2:
            ub = mid
        else:
            lb = mid
    # print ('ub', ub)
    a1, b1 = A[ub] - min_num, max_num - A[ub]
    diff1 = abs(b1 - a1)
    # print ('diff1', diff1)
    a2, b2 = A[ub - 1] - min_num, max_num - A[ub - 1]
    diff2 = abs(b2 - a2)
    # print ('diff2', diff2)
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1

# print (calc(A, 0))
# half = 2
# P, Q = calc(0, half - 1)
# print (P, Q)

ans = 10 ** 9
for half in range(2, N - 1):
    # print (A[:half], end = ' ')
    # print (A[half:])
    P, Q = calc(0, half - 1)
    R, S = calc(half, N - 1)
    # print (P, Q, R, S)
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    # print (tmp)
    ans = min(tmp, ans)

# print ('ans', ans)
print (ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
sa = [0]
for ai in a:
    sa.append(sa[-1] + ai)

def binary_search(lo, hi, v):
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if sa[mid] > v:
            hi = mid
        else:
            lo = mid
    return lo

def calc(m1, m2, m3):
    if m1 <= 0 or m2 - m1 <= 0 or m3 - m2 <= 0 or n - m3 <= 0:
        return sa[n]
    values = (sa[m1], sa[m2] - sa[m1], sa[m3] - sa[m2], sa[n] - sa[m3])
    return max(values) - min(values)

ret = sa[n]
for m2 in range(2, n - 1):
    m1 = binary_search(0, m2, sa[m2] // 2)
    m3 = binary_search(m2, n, (sa[n] + sa[m2]) // 2)
    for i1 in (0, 1):
        for i2 in (0, 1):
            for i3 in (0, 1):
                ret = min(ret, calc(m1 + i1, m2 + i2, m3 + i3))
print(ret)

Submission status: Accepted

Solution code:
N = int(input())
f = list(map(int, input().split()))
for i in range(N-1):
    f[i+1] += f[i]
l, r = 0, 2
ans = float('inf')
for m in range(1, N-2):
    while l+1 < m and abs(2*f[l+1]-f[m]) < abs(2*f[l]-f[m]):
        l += 1
    while r+1 < N and abs(2*f[r+1]-f[m]-f[N-1]) < abs(2*f[r]-f[m]-f[N-1]):
        r += 1
    tmp = max(f[l], f[m]-f[l], f[r]-f[m], f[N-1]-f[r]) - min(f[l], f[m]-f[l], f[r]-f[m], f[N-1]-f[r])
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

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

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

leftMiddle = 0
rightMiddle = 2

ans = float('inf')

for middle in range(2, N-1) :
    leftS = S[leftMiddle]
    rightS = S[middle] - leftS
    diff = abs(leftS - rightS)

    # 左側の更新
    for i in range(leftMiddle, middle) :
        leftS += A[i]
        rightS -= A[i]
        if diff > abs(leftS - rightS) :
            leftMiddle += 1
            diff = abs(leftS - rightS)
        else :
            break

    leftS = S[rightMiddle] - S[middle]
    rightS = S[-1] - S[rightMiddle]
    diff = abs(leftS - rightS)

    # 右側の更新
    for i in range(rightMiddle, N) :
        leftS += A[i]
        rightS -= A[i]
        if diff > abs(leftS - rightS) :
            rightMiddle += 1
            diff = abs(leftS - rightS)
        else :
            break

    B = S[leftMiddle]
    C = S[middle] - B
    D = S[rightMiddle] - S[middle]
    E = S[-1] - B - C - D

    diff = max(B, C, D, E) - min(B, C, D, E)
    ans = min(ans, diff)

print(ans)

Submission status: Accepted

Solution code:
inf = float('inf')

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

c_sum = [0]
t = 0
for aa in a:
    t += aa
    c_sum.append(t)

ans = inf
p, q = 0, 2  # c_sum上のindex
for cut in range(2, N - 2 + 1):
    # [0, cut)と[cut, N)に分ける
    # 各区間を二分割する
    # 分割位置は、要素の合計の差が最小になるように取る

    # c_sum上のカーソルpを動かす
    # 右区間に一つ以上の要素が含まれるように、pはcut-1まで取る
    # c_sum[p]: 二分割した左区間の和
    # c_sum[cut] - c_sum[p]: 二分割した右区間の和
    while p < cut - 1:
        if abs(c_sum[cut] - c_sum[p] * 2) >= abs(c_sum[cut] - c_sum[p + 1] * 2):
            p += 1
        else:
            break

    # c_sum上のカーソルqを動かす
    # 右区間に一つ以上の要素が含まれるように、qはN-1まで取る
    # c_sum[q]: 二分割した左区間の和
    # c_sum[N] - c_sum[q]: 二分割した右区間の和
    while q < N - 1:
        if abs(c_sum[N] - c_sum[q] - (c_sum[q] - c_sum[cut])) >= abs(
                c_sum[N] - c_sum[q + 1] - (c_sum[q + 1] - c_sum[cut])):
            q += 1
        else:
            break

    cands = [c_sum[cut] - c_sum[p], c_sum[p], c_sum[N] - c_sum[q], c_sum[q] - c_sum[cut]]
    # print(cands)
    ans = min(ans, max(cands) - min(cands))
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:
from bisect import bisect_left, bisect_right
from itertools import accumulate

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

ans = A_sum[N-1]
for m in range(2,N-1):
    sum_left = A_sum[m-1]
    i=bisect_left(A_sum,sum_left/2)
    sum1=A_sum[i]
    if i!= 0:
        if A_sum[i]+A_sum[i-1] > sum_left:
            sum1=A_sum[i-1]
    sum2 = sum_left - sum1
    
    sum_right=A_sum[N-1]-sum_left
    i=bisect_left(A_sum,sum_left+sum_right/2)
    sum3=A_sum[i]-sum_left
    if i!=m:
        if A_sum[i]+A_sum[i-1]-2*sum_left>sum_right:
            sum3=A_sum[i-1]-sum_left
    sum4=sum_right-sum3
    max_sum=max(sum1,sum2,sum3,sum4)
    min_sum=min(sum1,sum2,sum3,sum4)
    dif=max_sum-min_sum
    if dif<ans:
        ans=dif
        
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.zeros(N+2, dtype=np.int64)
A[1:-1] = input().split()

np.cumsum(A, out = A)
total = A[-1]
A[-1] = 10 ** 18

left = np.searchsorted(A, A/2)
P1 = A[left-1]
P2 = A[left]
Q1,Q2 = A-P1, A-P2

np.maximum(P1,Q2,out = P1)
np.minimum(P2,Q1,out = P2)
P,Q = P1,P2

right = np.searchsorted(A,(total+A)/2)
R1 = A[right-1] - A
R2 = A[right] - A
S1 = total - A[right-1]
S2 = total - A[right]
np.maximum(R1,S2,out=R1)
np.minimum(R2,S1,out=R2)
R,S = R1,R2

PQRS = np.vstack([P,Q,R,S])
x = np.max(PQRS, axis=0) - np.min(PQRS, axis=0)
answer = (x[1:-1].min())
print(answer)

Submission status: Accepted

Solution code:
def absdiff(a, b):
    return abs(b - a)


def solve(s):
    n, *a = map(int, s.split())
    l, r, ans = 1, 3, sum(a)
    sll, slr, srl, srr = a[0], 0, sum(a[1:3]), sum(a[3:])
    for c in range(1, n - 1):
        slr += a[c]
        srl -= a[c]
        r = max(c, r)
        while l < c and absdiff(sll + a[l], slr - a[l]) < absdiff(sll, slr):
            sll, slr, l = sll + a[l], slr - a[l], l + 1
        while r < len(a) and absdiff(srl + a[r], srr - a[r]) < absdiff(srl, srr):
            srl, srr, r = srl + a[r], srr - a[r], r + 1
        _max, _min = max(sll, slr, srl, srr), min(sll, slr, srl, srr)
        ans = min(ans, absdiff(_min, _max))
    return ans


print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
import bisect
from collections import deque
from fractions import gcd
#from math import factorial
from math import sqrt
from math import ceil
from itertools import permutations
from copy import deepcopy

#S=input()
#s=input()
from collections import defaultdict

N=int(input())
A=list(map(int,input().split()))
B=list(A)
B.reverse()
l=[0]*(N+1)
for i in range(N):
    l[i+1]=l[i]+A[i]
r=[0]*(N+1)
for i in range(N):
    r[i+1]=r[i]+B[i]
ans=10**9
for i in range(2,N-1):
    S=l[i]
    a=bisect.bisect_left(l,S/2)
    b=a-1
    if abs(l[a]-S/2)<=abs(l[b]-S/2):
        c=a
    else: c=b
    T=l[-1]-S
    a=bisect.bisect_left(r,T/2)
    b=a-1
    if abs(r[a]-T/2)<=abs(r[b]-T/2):
        d=a
    else: d=b
    p=[l[c],S-l[c],r[d],T-r[d]]
    p.sort()
    ans=min(ans,p[-1]-p[0])
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate, islice
from bisect import bisect_left
 
n = int(input())
xs = [int(x) for x in input().split()]
 
ys = list(accumulate(xs))
zs, total = ys[:-1], ys[-1]
 
res = max(xs) - min(xs)
for i, z in islice(enumerate(zs), 1, n-1):
    j = bisect_left(zs, z//2)
    splits = ((zs[j+k], z - zs[j+k]) for k in (-1, 0, 1) if 0 <= j+k <= i)
    a, b = min(splits, key=lambda s:abs(s[0]-s[1]))
 
    j = bisect_left(zs, (total - z)//2 + z)
    splits = ((zs[j+k] - z, total - zs[j+k]) for k in (-1, 0, 1) if i <= j+k <= n-2)
    c, d = min(splits, key=lambda s:abs(s[0]-s[1]))
 
    minn, _, _, maxx = sorted((a,b,c,d))
    if maxx - minn < res:
        res = maxx - minn
 
print(res)

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]

#真ん中の仕切りを固定し、左右の配列についてさらに仕切りを動かして確認する
#累積和なので単調増加だから、左右の二つの配列について、仕切りを追加したときに差が最も小さい仕切りの位置を保存
l = 0
r = 2
ans = float("inf")
#mは真ん中の仕切りの位置
for m in range(1, n-1):
        #累積和が単調増加だから、mを固定したとき2a[l]-a[m]も単調増加で、lを増加させていくと徐々に減少しlとl+1で逆転する部分を左の仕切りとする。
        #2倍しないと累積和が単調増加のためずっと右辺が小さいままになる
        #部分配列の平均値に近い部分を二分探索で探すことも可能だが、平均計算処理と探索処理に加え、候補がbisectで求めた位置の前後も含まれるのでめんどくさい
        while abs(2*a[l] - a[m]) > abs(2*a[l+1] - a[m]): 
                l += 1
        while abs(2*a[r] - a[n-1] - a[m]) > abs(2*a[r+1] - a[n-1] - a[m]):
                r += 1

        bcde = [a[l], a[m]-a[l], a[r]-a[m],  a[n-1]-a[r]]
        ans = min(ans, max(bcde)-min(bcde))
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate


def solve(string):
    n, *a = map(int, string.split())
    *a, = accumulate(a)
    l, r, e, ans = 0, 2, a[-1], a[-1]
    for c in a[1:-2]:
        while a[l] + a[l + 1] < c:
            l += 1
        while a[r] + a[r + 1] < c + e:
            r += 1
        t = sorted([a[l], c - a[l], a[r] - c, e - a[r]])
        ans = min(ans, t[-1] - t[0])
    return str(ans)


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
from itertools import accumulate


def solve(string):
    n, *a = map(int, string.split())
    *a, = accumulate(a)
    l, r, e = 0, 2, a[-1]
    ans = e
    for c in a[1:-2]:
        while a[l] + a[l + 1] < c:
            l += 1
        while a[r] + a[r + 1] < c + e:
            r += 1
        tmp = sorted([a[l], c - a[l], a[r] - c, e - a[r]])
        ans = min(ans, tmp[-1] - tmp[0])
    return str(ans)


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
from itertools import accumulate


def solve(string):
    n, *a = map(int, string.split())
    *a, = accumulate(a)
    l, c, r = 0, 1, 2
    sll, slr, srl, srr = a[l], a[c] - a[l], a[r] - a[c], a[-1] - a[r]
    ans = max(sll, slr, srl, srr) - min(sll, slr, srl, srr)
    while c < n - 1:
        while abs(a[c] - 2 * a[l + 1]) < abs(a[c] - 2 * a[l]):
            l += 1
        while abs(a[-1] + a[c] - 2 * a[r + 1]) < abs(a[-1] + a[c] - 2 * a[r]):
            r += 1
        sll, slr, srl, srr = a[l], a[c] - a[l], a[r] - a[c], a[-1] - a[r]
        ans = min(ans, max(sll, slr, srl, srr) - min(sll, slr, srl, srr))
        c+=1
    return str(ans)


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
def tmp(a, b, c):
    return abs(a - b), abs(a - b + 2 * c)


def solve(string):
    n, *a = map(int, string.split())
    l, c, r = 1, 2, 3
    sll, slr, srl, srr = sum(a[:l]), sum(a[l:c]), sum(a[c:r]), sum(a[r:])
    ans = max(sll, slr, srl, srr) - min(sll, slr, srl, srr)
    while c < n - 1:

        d, dn = tmp(sll, slr, a[l])
        while dn < d:
            sll, slr, l = sll + a[l], slr - a[l], l + 1
            d, dn = tmp(sll, slr, a[l])
        d, dn = tmp(srl, srr, a[r])
        while dn < d:
            srl, srr, r = srl + a[r], srr - a[r], r + 1
            d, dn = tmp(srl, srr, a[r])
        ans = min(ans, max(sll, slr, srl, srr) - min(sll, slr, srl, srr))
        slr, srl, c = slr + a[c], srl - a[c], c + 1
    return str(ans)


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
def solve(string):
    n, *a = map(int, string.split())
    l, c, r = 1, 2, 3
    sll, slr, srl, srr = sum(a[:l]), sum(a[l:c]), sum(a[c:r]), sum(a[r:])
    ans = max(sll, slr, srl, srr) - min(sll, slr, srl, srr)
    while c < n - 1:
        d = abs(sll - slr)
        dn = abs(sll + 2 * a[l] - slr)
        while dn < d:
            sll, slr = sll + a[l], slr - a[l]
            l += 1
            d = abs(sll - slr)
            dn = abs(sll + 2 * a[l] - slr)
        d = abs(srl - srr)
        dn = abs(srl + 2 * a[r] - srr)
        while dn < d:
            srl, srr = srl + a[r], srr - a[r]
            r += 1
            d = abs(srl - srr)
            dn = abs(srl + 2 * a[r] - srr)
        ans = min(ans, max(sll, slr, srl, srr) - min(sll, slr, srl, srr))
        slr += a[c]
        srl -= a[c]
        c += 1
    return str(ans)


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from itertools import accumulate as ac
N = int(input())
A = list(ac(map(int, input().split())))
l, r, t = 0, 2, A[-1]
c = t

for m in A[1:-2]:
    while t+m > A[r]+A[r+1]:
        r += 1
    while m > A[l]+A[l+1]:
        l += 1
    x = sorted([A[l],m-A[l],A[r]-m,t-A[r]])
    c = min(c,x[-1]-x[0])
print(c)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, A: "List[int]"):
    acc = list(accumulate(A))
    li = 1
    rdiff = float('inf')
    ri = 0
    for i in range(3, len(acc)):
        d = acc[-1] - acc[i-1]
        c = acc[i-1] - acc[1]
        if abs(d - c) < rdiff:
            rdiff = abs(d -c)
            ri = i
    ci = 2

    def _g(li, ci, ri):
        a = acc[li - 1]
        b = acc[ci - 1] - acc[li-1]
        c = acc[ri - 1] - acc[ci - 1]
        d = acc[-1] - acc[ri - 1]
        cr = max([a, b, c, d]) - min([a, b, c, d])
        return cr

    def _f(h, m, l):
        bbb = acc[l-1] if 0 < l else 0
        return abs((acc[h - 1] - acc[m-1]) - (acc[m - 1] - bbb))
  
    r = _g(li, ci, ri)
    for i in range(3, len(acc) - 1):
        while _f(i, (li+1), 0) <  _f(i, li, 0):
            li += 1
        while _f(len(acc), (ri+1), i) <  _f(len(acc), ri, i):
            ri += 1
        cr = _g(li, i, ri)
        if cr < r:
            r = cr
    return r


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]"
    result = solve(N, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

answer = S

# index は最後に回収する番号で管理
B = 0
D = 2

for C in range(1,N-2):
  D = max(D,C+1)
  SB = A[B]
  SC = A[C] - A[B]
  SD = A[D] - A[C]
  SE = S - A[D]
  left_score = abs(SB - SC)
  # BCの境界の調整
  while True:
    B_ = B+1
    SB_ = A[B_]
    SC_ = A[C] - SB_
    x = abs(SB_ - SC_)
    if left_score > x:
      B,SB,SC,left_score = B_,SB_,SC_,x
      continue
    break
  right_score = abs(SD-SE)
  # DEの境界の調整
  while True:
    D_ = D+1
    SD_ = A[D_] - A[C]
    SE_ = S - A[D_]
    x = abs(SD_ - SE_)
    if right_score > x:
      D,SD,SE,right_score = D_,SD_,SE_,x
      continue
    break
  score = max(SB,SC,SD,SE) - min(SB,SC,SD,SE)
  answer = min(answer,score)
  
print(answer)

Submission status: Accepted

Solution code:

def main():
    num = int(input())
    data = list(map(int, input().split()))

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

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

    while c <= num-2:
        while True:
            if abs(P-Q) < abs((P+data[l])-(Q-data[l])):
                break

            if l == c-1:
                break

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

        while True:
            if abs(R-S) < abs((R+data[r])-(S-data[r])):
                break
            if r == num-1:
                break

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

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

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, os
from itertools import accumulate
import bisect

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

n = f()[0]
def get_mid(b, i):
    global n
    front_i_sum = b[i]

    idx1 = bisect.bisect_right(b, front_i_sum/2)
    if idx1 == 0:
        idx1 = 1
        max_fisrt = max(b[0], b[i]-b[0])
        min_first = min(b[0], b[i]-b[0])
    
    else:


        max1 = b[idx1]
        min1 = b[i] - b[idx1]

        max2 = b[i] - b[idx1-1]
        min2 = b[idx1-1]

        if max1 - min1 >= max2 - min2:
            max_fisrt = max2
            min_first = min2
        else:
            max_fisrt = max1
            min_first = min1


    idx2 = bisect.bisect_right(b, front_i_sum + (b[n-1] - b[i])/2)

    if idx2 == i+1:
        max_s = max(b[i+1]- b[i], b[n-1]- b[i+1])
        min_s = min(b[i+1]- b[i], b[n-1]- b[i+1])

    else:
        max1 = b[idx2] - front_i_sum
        min1 = b[n-1] - b[idx2]

        max2 = b[n-1] - b[idx2-1]
        min2 = b[idx2-1] - front_i_sum

        if max1 - min1 >= max2 - min2:
            max_s = max2
            min_s = min2
        else:
            max_s = max1
            min_s = min1
    
    return max(max_fisrt, max_s) - min(min_first, min_s)


def solve():
    a = f()
    b = list(accumulate(a))

    ans = int(2e14)
    for i in range(1, n-2):
        ans = min(ans, get_mid(b, i))

    print(ans)




solve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
SUM = [0]
ans = 10**20
for a in A:
    SUM.append(SUM[-1]+a)

# P < Qとなるような区切れ目を探す
def binary_search1(a, ok, ng, i):
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if a[mid] < a[i]-a[mid]: ok = mid
        else: ng = mid
    return ok

# R < Sとなるような区切れ目を探す
def binary_search2(a, ok, ng, i):
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if a[mid]-a[i] < a[N]-a[mid]: ok = mid
        else: ng = mid
    return ok

for i in range(2,N-1): # [1,i]と(i,N]に分割
    m = binary_search1(SUM, 0, i+1, i)
    P1, Q1 = SUM[m], SUM[i]-SUM[m]
    P2, Q2 = SUM[m+1], SUM[i]-SUM[m+1]
    if abs(P1-Q1) < abs(P2-Q2): P, Q = P1, Q1
    else: P, Q = P2, Q2
    m = binary_search2(SUM, i, N+1, i)
    R1, S1 = SUM[m]-SUM[i], SUM[N]-SUM[m]
    R2, S2 = SUM[m+1]-SUM[i], SUM[N]-SUM[m+1]
    if abs(R1-S1) < abs(R2-S2): R, S = R1, S1
    else: R, S = R2, S2
    ans = min(max(P,Q,R,S) - min(P,Q,R,S), ans)
print(ans)

Submission status: Accepted

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

X = list(accumulate(A))

# A[:m]をできるだけ均等に、A[:l + 1], A[l + 1:]に分けるようなlを探す
l = 0
L = [-1] * N
for m in range(2, N - 1):
    target = X[m - 1] / 2
    while (l + 1 <= m) and abs(target - X[l]) >= abs(target - X[l + 1]):
        l += 1
    L[m] = l

# A[m:]をできるだけ均等に、A[:r + 1], A[r + 1:]に分けるようなrを探す
r = N - 1
r_sum = 0
R = [-1] * N
for m in reversed(range(2, N - 1)):
    target = (X[-1] - X[m - 1]) / 2
    while (r - 1 >= m) and abs((target - r_sum)) >= abs((target - (r_sum + A[r]))):
        r_sum += A[r]
        r -= 1
    R[m] = r

ans = float('inf')
for m in range(2, N - 1):
    li, ri = L[m], R[m]
    B, C, D, E = X[li], X[m - 1] - X[li], X[ri] - X[m - 1], X[-1] - X[ri]
    ans = min(ans, max(B, C, D, E) - min(B, C, D, E))

print(ans)

Submission status: Accepted

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

cul_sum = [0 for _ in range(N+1)]
for i in range(N):
    cul_sum[i+1] = A[i] + cul_sum[i]

def diff_left(center, left):
    return abs(cul_sum[center+1] - 2 * cul_sum[left+1])

def diff_right(center, right):
    return abs(cul_sum[N]-2*cul_sum[right+1]+cul_sum[center+1])

L = [-1 for _ in range(N-1)]
R = [-1 for _ in range(N-1)]
# 真ん中の切り方が i と i+1 の間
l = 0
r = 2
ans = float('inf')
for i in range(1, N-2):
    while l < i and diff_left(i, l) > diff_left(i, l+1):
        l += 1
    if r <= i:
        r = i+1
    while r < N and diff_right(i, r) > diff_right(i, r+1):
        r += 1
    part_sum = [
        cul_sum[l+1],
        cul_sum[i+1] - cul_sum[l+1],
        cul_sum[r+1] - cul_sum[i+1],
        cul_sum[N] - cul_sum[r+1],
    ]
    ans = min(ans, max(part_sum)-min(part_sum))

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()
B = list(accumulate(A))

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

ans = INF

for c in range(1, N-1):
	while True:
		if abs(P-Q) < abs((P+A[l])-(Q-A[l])):
			break
		if l == c-1:
			break
		P += A[l]
		Q -= A[l]
		l += 1

	while True:
		if abs(R-S) < abs((R+A[r])-(S-A[r])):
			break
		if r == N-1:
			break
		R += A[r]
		S -= A[r]
		r += 1

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

	Q += A[c]
	R -= A[c]

print(ans)

Submission status: Accepted

Solution code:
import sys


def cumsum(li):
    ret = [0]
    sum = 0
    for i in li:
        sum += i
        ret.append(sum)
    return ret


sys.setrecursionlimit(10000)
INF = float('inf')

N = int(input())
A = list(map(int, input().split()))
# 最初が0
cs = cumsum(A)
assert len(cs) == N + 1


def calc_diff(d1, d2, d3):
    diffs = [
        cs[d1] - cs[0],
        cs[d2] - cs[d1],
        cs[d3] - cs[d2],
        cs[N] - cs[d3]
    ]
    return max(diffs) - min(diffs)


# 切る位置
# dn: n 番目の数列の開始インデックス
d0 = 0
d1 = 1
d2 = 2
d3 = 3
d4 = N
ans = INF
while d2 < d4 - 1:
    d012 = abs((cs[d1] - cs[d0]) - (cs[d2] - cs[d1]))
    while d1 < d2 - 1 and d012 > abs((cs[d1 + 1] - cs[d0]) - (cs[d2] - cs[d1 + 1])):
        d1 += 1
        d012 = abs((cs[d1] - cs[d0]) - (cs[d2] - cs[d1]))
    d234 = abs((cs[d3] - cs[d2]) - (cs[d4] - cs[d3]))
    while d3 < d4 - 1 and d234 > abs((cs[d3 + 1] - cs[d2]) - (cs[d4] - cs[d3 + 1])):
        d3 += 1
        d234 = abs((cs[d3] - cs[d2]) - (cs[d4] - cs[d3]))
    ans = min(ans, calc_diff(d1, d2, d3))
    d2 += 1

print(ans)

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(acc(map(int,input().split())))

ans=a[-1]
p=0
q=2
for j in range(1,N-2):
    q=max(q,j+1)
    while p<j-1 and abs(a[j]-a[p]*2)>abs(a[j]-a[p+1]*2):
        p+=1
    while q<N-2 and abs(a[j]+a[N-1]-a[q]*2)>abs(a[j]+a[N-1]-a[q+1]*2):
        q+=1

    x=[ a[p], a[j]-a[p], a[q]-a[j], a[N-1]-a[q] ]
    ans=min(ans, max(x)-min(x))

print(ans)

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
p=0
q=2
for j in range(1,N-2):
    q=max(q,j+1)
    while p<j-1 and abs(a[j]-a[p]*2)>abs(a[j]-a[p+1]*2):
        p+=1
    while q<N-2 and abs(a[j]+a[N-1]-a[q]*2)>abs(a[j]+a[N-1]-a[q+1]*2):
        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)