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

Solution (Python):
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)

    
    
    
    ans = min(max(left_max, right_max) - min(left_min, right_min), ans)

print(ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
N = int(input())


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

answer = S


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)
    
    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)

Solution (Python):



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 
    
    while (ub - lb) > 1: 
        mid = (lb + ub)//2 
        if A[mid] - min_num > total/2: 
            ub = mid 
        else: 
            lb = mid 
    

    
    a1, b1 = A[ub] - min_num, max_num - A[ub]
    diff1 = abs(b1 - a1)
    
    a2, b2 = A[ub - 1] - min_num, max_num - A[ub - 1]
    diff2 = abs(b2 - a2)
    
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1






ans = 10 ** 9 
for half in range(2, N - 1): 
    P, Q = calc(0, half - 1)
    R, S = calc(half, N - 1)
    
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    
    ans = min(tmp, ans)


print (ans)

Solution (Python):


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
    
    while (ub - lb) > 1:
        mid = (lb + ub)//2
        if A[mid] - min_num > total/2:
            ub = mid
        else:
            lb = mid
    
    a1, b1 = A[ub] - min_num, max_num - A[ub]
    diff1 = abs(b1 - a1)
    
    a2, b2 = A[ub - 1] - min_num, max_num - A[ub - 1]
    diff2 = abs(b2 - a2)
    
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1






ans = 10 ** 9
for half in range(2, N - 1):
    
    
    P, Q = calc(0, half - 1)
    R, S = calc(half, N - 1)
    
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    
    ans = min(tmp, ans)


print (ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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  
for cut in range(2, N - 2 + 1):
    
    
    

    
    
    
    
    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

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

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
INF = float('inf')
from bisect import bisect
N = int(input())
A = list(map(int,input().split()))
S = [0]*N
for i in range(N):
    S[i] = S[i-1]+A[i]

ans = INF
for i in range(2,N-1):
    j = bisect(S,S[i-1]/2)
    k = bisect(S,(S[-1]+S[i-1])/2)
    for p in {j-1,min(j,i-2)}:
        for q in {k-1,i,min(k,N-2)}:
            a,b,c,d = S[p],S[i-1]-S[p],S[q]-S[i-1],S[-1]-S[q]
            m = min(a,b,c,d)
            M = max(a,b,c,d)
            ans = min(ans,M-m)

print(ans)

Solution (Python):
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()])))

Solution (Python):
import bisect
from collections import deque
from fractions import gcd

from math import sqrt
from math import ceil
from itertools import permutations
from copy import deepcopy



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)

Solution (Python):
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)

Solution (Python):
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")

for m in range(1, n-1):
        
        
        
        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)

Solution (Python):
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()])))

Solution (Python):
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()])))

Solution (Python):
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()])))

Solution (Python):
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()])))

Solution (Python):
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()])))

Solution (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)

Solution (Python):

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 bs(a, lo, hi, f):
    olo = lo
    ohi = hi
    while (lo + 1) < hi:
        mid = (lo + hi) // 2
        v = f(ohi, mid, olo)
        if 0 < v:
            lo = mid
        elif v < 0:
            hi = mid
        else:
            return mid
    if abs(f(ohi, lo, olo)) < abs(f(ohi, hi, olo)):
        return lo
    else:
        return hi

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

    def _g(li, ci, ri):
        a = acc[li - 1] - acc[0]
        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):
        return ((acc[h - 1] - acc[m-1]) - (acc[m - 1] - acc[l - 1]))

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

    ret = float('inf')
    for i in range(3, len(acc) - 1):
        li = bs(acc, 1, i, _f)
        ri = bs(acc, i, len(acc), _f)
        cv = _g(li, i, ri)
        ret = min(ret, cv)
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [ int(next(tokens)) for _ in range(N) ]  
    result = solve(N, A)
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):

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))  
    A = [ int(next(tokens)) for _ in range(N) ]  
    result = solve(N, A)
    print(result)

if __name__ == '__main__':
    main()

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

answer = S


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)
  
  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)
  
  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)

Solution (Python):

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)

        
        Q += data[c]
        R -= data[c]
        c += 1

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
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()

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


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


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): 
    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)

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

SUM = [0]
ans = 10**20
for a in A:
    SUM.append(SUM[-1]+a)
for i in range(2,N-1): 
    low, high = 1, i
    while high - low > 1:
        mid = (low + high)//2
        if SUM[mid] >= SUM[i] - SUM[mid]: high = mid
        else: low = mid
    P1, Q1 = SUM[low], SUM[i]-SUM[low]
    P2, Q2 = SUM[high], SUM[i]-SUM[high]
    if abs(P1-Q1) < abs(P2-Q2): P, Q = P1, Q1
    else: P, Q = P2, Q2
    low, high = i+1, N
    while high - low > 1:
        mid = (low + high)//2
        if SUM[mid]-SUM[i] >= SUM[N]-SUM[mid]: high = mid
        else: low = mid
    R1, S1 = SUM[low]-SUM[i], SUM[N]-SUM[low]
    R2, S2 = SUM[high]-SUM[i], SUM[N]-SUM[high]
    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)

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

X = list(accumulate(A))


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


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)

Solution (Python):


from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance





def calc_partsum(asumlist, start, end):
    floor = start
    bound = (start + end) // 2
    ceil = end - 1
    ret = (float('inf'), None, None)

    while True:
        p = asumlist[bound - 1] - asumlist[start - 1]
        q = asumlist[end - 1] - asumlist[bound - 1]

        if p == q:
            return p, q
        ret = min(ret, (abs(p - q), p, q))
        if floor >= ceil:
            _, p, q = ret
            return p, q

        if p > q:
            ceil = bound - 1
        if p < q:
            floor = bound + 1
        bound = (floor + ceil) // 2


def calc_sadness(asumlist, n, k):
    p, q = calc_partsum(asumlist, 1, k)
    r, s = calc_partsum(asumlist, k, n)
    return max([p, q, r, s]) - min([p, q, r, s])


def main():
    n = intin()
    alist = intina()

    asum = 0
    asumlist = [0]
    for a in alist:
        asum += a
        asumlist.append(asum)

    ans = float('inf')
    for i in range(3, n):
        ans = min(ans, calc_sadness(asumlist, n + 1, i))
    print(ans)


if __name__ == '__main__':
    main()