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:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

AA = np.cumsum(A)
def t(a,b):
    return AA[b] - AA[a] + A[a]

B = np.zeros(N-3)
for i in range(1,N-2):
    old = 1e30
    for j in range(0,i):
        x = t(0,j)
        y = t(j+1,i)
        if abs(x-y) < old:
            old = abs(x-y)
            p = x
            q = y
    old = 1e30
    for j in range(i+1,N-1):
        x = t(i+1,j)
        y = t(j+1,N-1)
        if abs(x-y) < old:
            old = np.abs(x-y)
            r = x
            s = y
    B[i-1] = max([p,q,r,s]) - min([p,q,r,s])

print(int(np.min(B)))

Submission status: Time Limit Exceeded

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]

rs = range(2, n-2)
v = []
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 = (sorted((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))
    v.append(maxx - minn)

print(min(v) if v else max(xs) - min(xs))

Submission status: Time Limit Exceeded

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]

rs = range(2, n-2)
v = []
for i, z in islice(enumerate(zs), 1, n-1):
    j = bisect_left(zs, z//2)
    minmaxs = (sorted((zs[j+k], z - zs[j+k])) for k in (-1, 0, 1) if 0 <= j+k <= i)
    _, max1, min1 = min((x-n, x, n) for n, x in minmaxs)

    j = bisect_left(zs, (total - z)/2 + z)
    minmaxs = (sorted((zs[j+k] - z, total - zs[j+k])) for k in (-1, 0, 1) if i <= j+k <= n-2)
    _, max2, min2 = min((x-n, x, n) for n, x in minmaxs)

    minn, _, _, maxx = sorted([max1, min1, max2, min2])
    v.append(maxx - minn)

print(min(v) if v else max(xs) - min(xs))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
import bisect

N=int(input())
A=[int(x) for x in input().split()]
S=list(accumulate(A))

def solve(x):
  cnt=S[x]
  L=bisect.bisect_left(S,cnt/2)
  R=bisect.bisect_left(S,(cnt+S[N-1])/2)
  L2=bisect.bisect_right(S,cnt/2)
  R2=bisect.bisect_right(S,(cnt+S[N-1])/2)
  res=10**10
  if R!=N:
    ans=[S[L],cnt-S[L],S[R]-cnt,S[N-1]-S[R]]
    ans2=[S[L2-1],cnt-S[L2-1],S[R]-cnt,S[N-1]-S[R]]
    res=min(res,max(ans)-min(ans),max(ans2)-min(ans2))
  if R2!=N:
    ans3=[S[L],cnt-S[L],S[R2-1]-cnt,S[N-1]-S[R2-1]]
    ans4=[S[L2-1],cnt-S[L2-1],S[R2-1]-cnt,S[N-1]-S[R2-1]]
    res=min(res,max(ans3)-min(ans3),max(ans4)-min(ans4))
  return res

res=10**10
for i in range(N):
  a=solve(i)
  res=min(res,a)
print(res)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect

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

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

ans = cums[-1] * 999
for c in range(2,N-1):
    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)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect

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

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

ans = cums[-1] * 999
for c in range(2,N-1):
    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)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools as it

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

csum = [0] + list(it.accumulate(A))

def csum_(a, b):
    return csum[b] - csum[a]

def search(ok, ng, n, m):
    if abs(ok-ng) <= 1:
            return ok
    mid = (ok+ng) // 2
    if csum_(m, mid) < csum_(mid, n):
        return search(mid, ng, n, m)
    else:
        return search(ok, mid, n, m)

fans = []

for c in range(2, n-1):
    d = search(1, c, c, 0)
    f = search(c+1, n, n, c)
    
    ans = []

    if abs(csum_(0, d) - csum_(d, c)) > abs(csum_(0, min(d+1, c-1)) - csum_(min(d+1, c-1), c)):
        d += 1

    if abs(csum_(c, f) - csum_(f, n)) > abs(csum_(c, min(n-1, f+1)) - csum_(min(n-1, f+1), n)):
        f += 1
 
    ans.append(csum_(0, d))
    ans.append(csum_(d, c))
    ans.append(csum_(c, f))
    ans.append(csum_(f, n))

    fans.append(max(ans) - min(ans))

print(min(fans))

Submission status: Time Limit Exceeded

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

csum = [0]

for a in A:
    csum.append(csum[-1] + a)

def csum_(a, b):
    return csum[b] - csum[a]

def search(ok, ng, n, m):
    if abs(ok-ng) <= 1:
            return ok
    mid = (ok+ng) // 2
    if csum_(m, mid) < csum_(mid, n):
        return search(mid, ng, n, m)
    else:
        return search(ok, mid, n, m)

fans = []

for c in range(2, n-1):
    d = search(1, c, c, 0)
    f = search(c+1, n, n, c)
    
    ans = []

    if abs(csum_(0, d) - csum_(d, c)) > abs(csum_(0, min(d+1, c-1)) - csum_(min(d+1, c-1), c)):
        d += 1

    if abs(csum_(c, f) - csum_(f, n)) > abs(csum_(c, min(n-1, f+1)) - csum_(min(n-1, f+1), n)):
        f += 1
 
    ans.append(csum_(0, d))
    ans.append(csum_(d, c))
    ans.append(csum_(c, f))
    ans.append(csum_(f, n))

    fans.append(max(ans) - min(ans))

print(min(fans))

Submission status: Time Limit Exceeded

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

csum = [0]

for a in A:
    csum.append(csum[-1] + a)

def csum_(a, b):
    return csum[b] - csum[a]

def search(ok, ng, n, m):
    if abs(ok-ng) <= 1:
            return ok
    mid = (ok+ng) // 2
    if csum_(m, mid) < csum_(mid, n):
        return search(mid, ng, n, m)
    else:
        return search(ok, mid, n, m)

fans = 10**9

for c in range(2, n-1):
    d = search(1, c, c, 0)
    f = search(c+1, n, n, c)
    
    ans = []

    if abs(csum_(0, d) - csum_(d, c)) > abs(csum_(0, min(d+1, c-1)) - csum_(min(d+1, c-1), c)):
        d += 1

    if abs(csum_(c, f) - csum_(f, n)) > abs(csum_(c, min(n-1, f+1)) - csum_(min(n-1, f+1), n)):
        f += 1
 
    ans.append(csum_(0, d))
    ans.append(csum_(d, c))
    ans.append(csum_(c, f))
    ans.append(csum_(f, n))

    fans = min(fans, max(ans) - min(ans))

print(fans)

Submission status: Time Limit Exceeded

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

csum = [0]

for a in A:
    csum.append(csum[-1] + a)

def csum_(a, b):
    return csum[b] - csum[a]

def search(ok, ng, n, m):
    if abs(ok-ng) <= 1:
            return ok
    mid = (ok+ng) // 2
    if csum_(m, mid) < csum_(mid, n):
        return search(mid, ng, n, m)
    else:
        return search(ok, mid, n, m)

fans = []

for c in range(2, n):
    d = search(1, c, c, 0)
    f = search(c+1, n, n, c)
    
    ans = []

    if abs(csum_(0, d) - csum_(d, c)) > abs(csum_(0, min(d+1, c-1)) - csum_(min(d+1, c-1), c)):
        d += 1

    if abs(csum_(c, f) - csum_(f, n)) > abs(csum_(c, min(n-1, f+1)) - csum_(min(n-1, f+1), n)):
        f += 1
 
    ans.append(csum_(0, d))
    ans.append(csum_(d, c))
    ans.append(csum_(c, f))
    ans.append(csum_(f, n))

    fans.append(max(ans) - min(ans))

print(min(fans))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from itertools import combinations as comb
N = int(input())
A = [int(i) for i in input().split()]
# print(N, A)

num = [i for i in range(N)]
punctuations = [p for p in comb(num, 3)]
diff = []
for p1, p2, p3 in punctuations:
    P, Q, R, S = A[:p1], A[p1:p2], A[p2:p3], A[p3:]
    if P and Q and R and S:
        lis = [sum(P), sum(Q), sum(R), sum(S)]
        diff.append(abs(max(lis) - min(lis)))

print(min(diff))

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
import bisect

sys.setrecursionlimit(10**8)

N = int(input())
A = list(map(int,input().split()))
Asum = [0]
aa = 0

#Asum[i] = A[0]+A[1]+ … +A[i-1]
for i in range(N):
	aa += A[i]
	Asum.append(aa)


ans = 10**20
	
	
for c in range(2,N-1):
	AL = A[:c]
	AR = A[c:]
	
	AsumL = Asum[c]
	AsumR = Asum[-1] - AsumL
	
	Lh = AsumL/2
	Rh = AsumR/2
		
	Lh_i = bisect.bisect_left(Asum,Lh)
	L1 = abs(Asum[Lh_i] - Lh)
	L2 = abs(Asum[Lh_i-1] - Lh)
	if L1 <= L2:
		B = Asum[Lh_i]
	else:
		B = Asum[Lh_i-1]
	
	C = AsumL - B

	Rh_i = bisect.bisect_left(Asum,Rh+AsumL)
	R1 = abs(Asum[Rh_i] - AsumL - Rh)
	R2 = abs(Asum[Rh_i-1] - AsumL - Rh)
	if R1 <= R2:
		D = Asum[Rh_i] - AsumL
	else:
		D = Asum[Rh_i-1] - AsumL
	
	E = AsumR - D
	
	dist = max(B,C,D,E) - min(B,C,D,E)	
	ans = min(ans,dist)
	
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def run(n, a):
    sum_a = [sum(a[0:i+1]) for i in range(n)]
    ret = sum_a[n - 1]
    for i in range(2, n-1):
        j_l = search_j(sum_a[: i], 0)
        j_r = search_j(sum_a[i:], sum_a[i - 1]) + i
        p = sum_a[j_l]
        q = sum_a[i - 1] - p
        r = sum_a[j_r] - q - p
        s = sum_a[n - 1] - r - q - p
        diff = max(p, q, r, s) - min(p, q, r, s)
        if ret > diff:
            ret = diff
    return ret


def search_j(sum_a, before):
    n = len(sum_a)
    sum_l = sum_a[0] - before
    sum_r = sum_a[n - 1] - sum_a[0]
    diff1 = sum_r - sum_l
    ret = 0
    for i in range(n - 1):
        sum_l = sum_a[i] - before
        sum_r = sum_a[n - 1] - sum_a[i]
        diff2 = sum_r - sum_l
        if diff2 < 0:
            if abs(diff1) < abs(diff2):
                return i - 1
            else:
                return i
        else:
            diff1 = diff2
            ret = i
    return ret


def read_line():
    n = int(input())
    a = list(map(int, input().split()))
    return (n, a)


def main():
    n, a = read_line()
    print(run(n, a))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import combinations
N = int(input())
A = np.array(list(map(int, input().split())), dtype= int)
X = A.sum()
A1 = np.cumsum(A)
mincost1 = -1
for r2 in range(1,N-2):
    Y = A1[r2]
    mincost2 = -1
    r1 = 1
    for i in np.arange(-1,2)+np.argmax(A1*(A1<=Y/2)):
        L = A1[i]
        R = Y - L
        cost = np.abs(R-L)
        if mincost2 < 0 or mincost2 >  cost:
            mincost2 = cost
            r1 = i
    P = A1[r1]
    Q = Y - A1[r1]

    mincost3 = -1
    r3 = N-1
    for i in  np.arange(-1,2)+np.argmax(A1*(A1<=(X+Y)/2)):
        L = A1[i] - Y
        R = X - Y - L
        cost = np.abs(R-L)
        if mincost3 < 0 or mincost3 >  cost:
            mincost3 = cost
            r3 = i

    R = A1[r3]-Y
    S = X-A1[r3]
    cost = max(P,Q,R,S) - min(P,Q,R,S)
    if mincost1 < 0 or mincost1 >  cost:
            mincost1 = cost
print(mincost1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import combinations
N = int(input())
A = np.array(list(map(int, input().split())), dtype= int)
X = A.sum()
A1 = np.cumsum(A)
mincost1 = -1
for r2 in range(1,N-2):
    Y = A1[r2]
    mincost2 = -1
    r1 = 1
    for i in range(0,r2):
        L = A1[i]
        R = Y - L
        cost = np.abs(R-L)
        if mincost2 < 0 or mincost2 >  cost:
            mincost2 = cost
            r1 = i
    P = A1[r1]
    Q = Y - A1[r1]

    mincost3 = -1
    r3 = N-1
    for i in range(r2+1,N):
        L = A1[i] - Y
        R = X - Y - L
        cost = np.abs(R-L)
        if mincost3 < 0 or mincost3 >  cost:
            mincost3 = cost
            r3 = i

    R = A1[r3]-Y
    S = X-A1[r3]
    cost = max(P,Q,R,S) - min(P,Q,R,S)
    if mincost1 < 0 or mincost1 >  cost:
            mincost1 = cost
print(mincost1)

Submission status: Time Limit Exceeded

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

tmp_arr = [0,0,0,0]
res = 1000000000

for p1 in range(1,n-2):
    tmp_arr[0] = sum(arr_ia[:p1])
    for p2 in range(p1,n-1):
        tmp_arr[1] = sum(arr_ia[p1:p2])
        for p3 in range(p2,n):
            tmp_arr[2] = sum(arr_ia[p2:p3])
            tmp_arr[3] = sum(arr_ia[p3:])
            
            res_arr = sorted(tmp_arr)
            tmp_res = res_arr[-1]-res_arr[0]
            if(res > tmp_res):
                res = tmp_res
            
print(res)

Submission status: Time Limit Exceeded

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

arrSum = list(sum(A[:idx+1]) for idx in range(N))

ans = float('inf')
##2分する区切り目の左のインデックスi: 1 ～ (N - 3)
nextJ, nextK = -1, -1
for i in range(1, (N - 3) + 1):
    ##左側の区間の右端はi番目まである
    ##区切り目の左のインデックスj: 0 ～ (i - 1)
    buf = float('inf')
    nextJ = max(nextJ, 0)
    for j in range(nextJ, i):
        sumB = arrSum[j]
        sumC = arrSum[i] - arrSum[j]
        d = abs(sumB - sumC)
        if buf > d:
            buf = d
            P = sumB
            Q = sumC
            nextJ = j
        else:
            break
    ##右側の区間の左端は(i + 1)番目
    ##区切り目の左のインデックスk: (i + 1) ～ (N - 2)
    buf = float('inf')
    nextK = max(nextK, (i + 1))
    for k in range(nextK, (N - 2) + 1):
        sumD = arrSum[k] - arrSum[i]
        sumE = arrSum[N-1] - arrSum[k]
        d = abs(sumD - sumE)
        if buf > d:
            buf = d
            R = sumD
            S = sumE
            nextK = k
        else:
            break
    arr = list((P, Q, R, S))
    ans = min(ans, max(arr) - min(arr))
print(ans)

Submission status: Time Limit Exceeded

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

arrSum = list(sum(A[:idx+1]) for idx in range(N))

ans = float('inf')
##2分する区切り目の左のインデックスi: 1 ～ (N - 3)
nextJ, nextK = -1, -1
for i in range(1, (N - 3) + 1):
    ##左側の区間の右端はi番目まである
    ##区切り目の左のインデックスj: 0 ～ (i - 1)
    buf = float('inf')
    nextJ = max(nextJ, 0)
    for j in range(nextJ, i):
        sumB = arrSum[j]
        sumC = arrSum[i] - arrSum[j]
        d = abs(sumB - sumC)
        if buf > d:
            buf = d
            P = sumB
            Q = sumC
            nextJ = j
    ##右側の区間の左端は(i + 1)番目
    ##区切り目の左のインデックスk: (i + 1) ～ (N - 2)
    buf = float('inf')
    nextK = max(nextK, (i + 1))
    for k in range(nextK, (N - 2) + 1):
        sumD = arrSum[k] - arrSum[i]
        sumE = arrSum[N-1] - arrSum[k]
        d = abs(sumD - sumE)
        if buf > d:
            buf = d
            R = sumD
            S = sumE
            nextK = k
    arr = list((P, Q, R, S))
    ans = min(ans, max(arr) - min(arr))
print(ans)

Submission status: Time Limit Exceeded

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

arrSum = list(sum(A[:idx+1]) for idx in range(N))

ans = float('inf')
##2分する区切り目の左のインデックスi: 1 ～ (N - 3)
for i in range(1, (N - 3) + 1):
    ##左側の区間の右端はi番目まである
    ##区切り目の左のインデックスj: 0 ～ (i - 1)
    buf = float('inf')
    for j in range(i):
        sumB = arrSum[j]
        sumC = arrSum[i] - arrSum[j]
        d = sumB - sumC
        if buf > abs(d):
            buf = abs(d)
            P = sumB
            Q = sumC
    ##右側の区間の左端は(i + 1)番目
    ##区切り目の左のインデックスk: (i + 1) ～ (N - 2)
    buf = float('inf')
    for k in range((i + 1), (N - 2) + 1):
        sumD = arrSum[k] - arrSum[i]
        sumE = arrSum[N-1] - arrSum[k]
        d = sumD - sumE
        if buf > abs(d):
            buf = abs(d)
            R = sumD
            S = sumE
    arr = list((P, Q, R, S))
    ans = min(ans, max(arr) - min(arr))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy
from bisect import bisect_left, bisect_right

N = int(input())
A = list(map(int, input().split()))
A_sum = numpy.cumsum(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: Time Limit Exceeded

Solution code:
N = int(input())
A_list = [int(elem) for elem in input().split(' ')]
assert N >= 4
assert len(A_list) == N

# cummulative sum
cuml_A_list = [0] * N
cuml_A_list[0] = A_list[0]
for i in range(1, N):
    cuml_A_list[i] = cuml_A_list[i-1] + A_list[i]
 
# initialize
best_diff = max(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])\
        - min(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])

left_sep = 0
right_sep = 2 + 1

# time complexity: O(N)?
for mid_sep in range(2, N - 1):
    left_sum = cuml_A_list[mid_sep - 1]
    right_sum = cuml_A_list[-1] - cuml_A_list[mid_sep - 1]
    for left_sep_cand in range(left_sep, mid_sep):
        # obtain the best first separation position
        if abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep_cand]) < abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep]):
            left_sep = left_sep_cand
    for right_sep_cand in range(right_sep, N):
        # obtain the best third separation position
        if abs(cuml_A_list[-1] - cuml_A_list[right_sep_cand] - (cuml_A_list[right_sep_cand] - cuml_A_list[mid_sep]))\
            < abs(cuml_A_list[-1] - cuml_A_list[right_sep] - (cuml_A_list[right_sep] - cuml_A_list[mid_sep])):
            right_sep = right_sep_cand
    diff = max(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])\
        - min(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])
    best_diff = min(best_diff, diff)
print(best_diff)

Submission status: Time Limit Exceeded

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

def func2(a,i):   
    bb,bc=func3(a[:i])
    cb,cc=func3(a[i:])
    *l,=map(sum,[bb,bc,cb,cc])
    return abs(max(l)-min(l))

def func3(b):
    i=0
    s=10**10
    m,n=0,sum(b)
    for j in range(len(b)-1):
        m+=b[j]
        n-=b[j]
        t=abs(m-n)
        if s>t:
            s=t
            i=j+1
        else:
            break
    return b[:i],b[i:]

m=10**10
for i in range(2,n-1):
    t=func2(a,i)
    if t<m:
        m=t
print(m)

Submission status: Time Limit Exceeded

Solution code:
import numpy

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

ans=A_sum[N-1]
for m in range(2,N-1):
  sum_left=A_sum[m-1]
  for i in range(1,m):
    if A_sum[i-1]>=sum_left/2:
      break
  sum1=A_sum[i-1]
  if i!=1:
    if A_sum[i-1]+A_sum[i-2]>sum_left:
      sum1=A_sum[i-2]
  sum2=sum_left-sum1

  sum_right=A_sum[N-1]-sum_left
  for i in range(m+1,N):
    if A_sum[i-1]-sum_left>=sum_right/2:
      break
  sum3=A_sum[i-1]-sum_left
  if i!=m+1:
    if A_sum[i-1]+A_sum[i-2]-2*sum_left>sum_right:
      sum3=A_sum[i-2]-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: Time Limit Exceeded

Solution code:
import numpy as np
import math


N = int(input())
A = np.array(list(map(int, input().split())))
CumA = np.cumsum(A)

res = 10 ** 16
for i in range(2, N-1):
    idx1 = np.argmin(np.abs(CumA[i-1] - 2 * CumA[:i]))
    P, Q = CumA[idx1], CumA[i-1] - CumA[idx1]
    idx2 = np.argmin(np.abs(CumA[-1] - 2 * CumA[i:] + CumA[i-1]))
    R, S = CumA[i + idx2] - CumA[i-1], CumA[-1] - CumA[i + idx2]
    res = min(res, max([P, Q, R, S]) - min([P, Q, R, S]))
print(res)

Submission status: Time Limit Exceeded

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

def func2(a,i):   
    bb,bc=func3(a[:i])
    cb,cc=func3(a[i:])
    *l,=map(sum,[bb,bc,cb,cc])
    return abs(max(l)-min(l))

def func3(b):
    i=0
    s=10**10
    for j in range(1,len(b)):
        t=abs(sum(b[:j])-sum(b[j:]))
        if s>t:
            s=t
            i=j
        else:
            break
    return b[:i],b[i:]

m=10**10
for i in range(2,n-1):
    t=func2(a,i)
    if t<m:
        m=t
print(m)

Submission status: Time Limit Exceeded

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

def func2(a,i):   
    bb,bc=func3(a[:i])
    cb,cc=func3(a[i:])
    *l,=map(sum,[bb,bc,cb,cc])
    return abs(max(l)-min(l))

def func3(b):
    i=0
    s=10**10
    for j in range(1,len(b)):
        t=abs(sum(b[:j])-sum(b[j:]))
        if s>t:
            s=t
            i=j
    return b[:i],b[i:]

m=10**10
for i in range(2,n-1):
    t=func2(a,i)
    if t<m:
        m=t
print(m)

Submission status: Time Limit Exceeded

Solution code:
import numpy

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

ans=A_sum[N-1]
for m in range(2,N-1):
  sum_left=A_sum[m-1]
  for i in range(1,m):
    sum1=A_sum[i-1]
    sum2=sum_left-sum1
    if sum2<sum1:
      break
  if i!=1:
    if sum1-sum2>sum_left-2*A_sum[i-2]:
      sum1=A_sum[i-2]
      sum2=sum_left-sum1
  
  sum_right=A_sum[N-1]-sum_left
  for i in range(m+1,N):
    sum3=A_sum[i-1]-sum_left
    sum4=sum_right-sum3
    if sum4<sum3:
      break
  if i!=m+1:
    if sum3-sum4>sum_right-2*(A_sum[i-2]-sum_left):
      sum3=A_sum[i-2]-sum_left
      sum4=sum_left-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: Time Limit Exceeded

Solution code:
import statistics
import math

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

B = []
C = []
D = []
E = []
ureshimi = []

for i in range(N-3):
    BC = A[0 : i + 2]
    s = 0
    for j in range(i + 2):
        s += BC[j]
        if s + BC[j + 1] > sum(BC) / 2:
            if BC[j + 1] / 2 >= sum(BC) / 2 - s:
                B = BC[0 : j + 1]
                C = BC[j + 1 : i + 2]
            else:
                B = BC[0 : j + 2]
                C = BC[j + 2 : i + 2]
            break
    DE = A[i + 2 : N + 1]
    s = 0
    for j in range(N - i - 3):
        s += DE[j]
        if j == N - i - 2:
            D = DE[0 : j + 1]
            D = DE[0 : j + 1]
            E = DE[j + 1 : N - i]
            break
        elif s + DE[j + 1] > sum(DE) / 2:
            if DE[j + 1] / 2 >= sum(DE) / 2 - s:
                D = DE[0 : j + 1]
                E = DE[j + 1 : N - i]
            else:
                D = DE[0 : j + 2]
                E = DE[j + 2 : N - i]
            break
    ureshimi.append(max(sum(B), sum(C), sum(D), sum(E)) - min(sum(B), sum(C), sum(D), sum(E)))



print(min(ureshimi))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = [int(elem) for elem in input().split(' ')]
assert N >= 4
assert len(A_list) == N

# cummulative sum
cuml_A_list = [0] * N
cuml_A_list[0] = A_list[0]
for i in range(1, N):
    cuml_A_list[i] = cuml_A_list[i-1] + A_list[i]
 
# initialize
best_diff = max(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])\
        - min(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])

for mid_sep in range(2, N - 1):
    left_sum = cuml_A_list[mid_sep - 1]
    right_sum = cuml_A_list[-1] - cuml_A_list[mid_sep - 1]
    left_sep = 0
    right_sep = mid_sep + 1
    for left_sep_cand in range(0, mid_sep):
        # obtain the best first separation position
        if abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep_cand]) < abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep]):
            left_sep = left_sep_cand
    for right_sep_cand in range(mid_sep, N):
        # obtain the best third separation position
        if abs(cuml_A_list[-1] - cuml_A_list[right_sep_cand] - (cuml_A_list[right_sep_cand] - cuml_A_list[mid_sep]))\
            < abs(cuml_A_list[-1] - cuml_A_list[right_sep] - (cuml_A_list[right_sep] - cuml_A_list[mid_sep])):
            right_sep = right_sep_cand
    diff = max(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])\
        - min(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])
    best_diff = min(best_diff, diff)
print(best_diff)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

def Split(cum_):
    S_ = cum_[-1]
    idx_ = np.argmin(np.abs(S_ - 2 * cum_))
    cum1_ = cum_[:idx_ + 1]
    cum2_ = cum_[idx_ + 1:] - cum_[idx_]
    return cum1_[-1], cum2_[-1]


N = int(input())
A = np.array(list(map(int, input().split())))
CumA = np.cumsum(A)

res = 10 ** 15
for i in range(1, N-2):
    P, Q = Split(CumA[: i+1])
    R, S = Split(CumA[i+1:] - CumA[i])
    res = min(res, max([P, Q, R, S]) - min([P, Q, R, S]))
print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
res = 20000000002
for k in range(n-3):
    for l in range(k+1,n-2):
        for m in range(l+1,n-1):
            f = [sum(a[:k+1]),sum(a[k+1:l+1]),sum(a[l+1:m+1]),sum(a[m+1:])]
            kari = max(f)-min(f)
            if kari < res: res = kari
print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
res = 20000000002
for k in range(n-3):
    b = sum(a[:k+1])
    for l in range(k+1,n-2):
        c = sum(a[k+1:l+1])
        for m in range(l+1,n-1):
            d = sum(a[l+1:m+1])
            e = sum(a[m+1:])
            f=[b,c,d,e]
            kari = max(f)-min(f)
            if kari < res:
                res = kari
print(res)

Submission status: Time Limit Exceeded

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

s=sum(a)
ans=s
b=a[0]
for i in range(n-3):
	b=0
	for l in range(i+2):
		b+=a[l]
	c=s-b
	j=0
	k=0
	while k-b/2<0:
		k+=a[j]
		j+=1
	if k-b/2>b/2+a[j-1]-k:
		k-=a[j-1]
	x=min(k,b-k)
	y=max(k,b-k)
	j=-1
	k=0
	while k-c/2<0:
		k+=a[j]
		j-=1
	if k-c/2>c/2+a[j+1]-k:
		k-=a[j+1]
	z=min(k,c-k)
	w=max(k,c-k)
	t=max(y,w)-min(x,z)
	if ans>t:
		ans=t
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
B, E = [], []
B_prev, E_prev = 0, 0
for idx in range(N):
    B.append(B_prev + A[idx])
    B_prev += A[idx]

tot = sum(A)
res = 1e12
for bidx in range(N - 3):
    for cidx in range(bidx, N - 2):
        for didx in range(cidx, N - 1):
            max_v = max(B[bidx], B[cidx] - B[bidx], B[didx] - B[cidx], tot - B[didx])
            min_v = min(B[bidx], B[cidx] - B[bidx], B[didx] - B[cidx], tot - B[didx])
            if res > abs(max_v - min_v):
                res = max_v - min_v
print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

def Split(cum_):
    S_ = cum_[-1]
    idx_ = np.argmin(np.abs(S_ - 2 * cum_))
    cum1_ = cum_[:idx_ + 1]
    cum2_ = cum_[idx_ + 1:] - cum_[idx_]
    return cum1_[-1], cum2_[-1]


N = int(input())
A = np.array(list(map(int, input().split())))
CumA = np.cumsum(A)

res = 10 ** 15
for ib in range(N-3):
    for ic in range(ib+1, N-2):
        P = CumA[ib]
        Q = CumA[ic] - P
        R, S = Split(CumA[ic+1:] - CumA[ic])
        res = min(res, max([P, Q, R, S]) - min([P, Q, R, S]))

print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = pow(10,10)
for i in range(1, N - 2):
	for j in range(i + 1, N - 1):
		for k in range(j + 1, N):
			B = list(A[:i])
			C = list(A[i:j])
			D = list(A[j:k])
			E = list(A[k:])
			P = sum(B)
			Q = sum(C)
			R = sum(D)
			S = sum(E)
			ans = min(ans, abs(max(P, Q, R, S) - min(P, Q, R, S)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

b = [0]

for i in a:
    b.append(b[-1]+i)
ans=10**10
for i in range(1,n-1):
    c = b[i]
    for j in range(1,n-i):
        d = b[i+j]-b[i]
        for k in range(1,n-i-j+1):
            e = b[i+j+k]-b[i+j]
            f = b[-1]-b[i+j+k]
            ans = min(ans,max(c,d,e,f)-min(c,d,e,f))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
d = []
all_min = float('inf')
for i in range(1, n-2):
    for j in range(i+1,n-1):
        for k in range(j+1, n):
            d = []
            p = sum(a[:i])
            d.append(sum(a[i:j]))
            d.append(sum(a[j:k]))
            d.append(sum(a[k:]))
            max = p
            min = p
            for d_i in d:
                if(max < d_i):
                    max = d_i
                if(min > d_i):
                    min = d_i
            sub = abs(max-min)
            if(all_min > sub):
                all_min = sub

print(all_min)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
res = 20000000002
for k in range(n-3):
    b = sum(a[:k+1])
    for l in range(k+1,n-2):
        c = sum(a[k+1:l+1])
        for m in range(l+1,n-1):
            d = sum(a[l+1:m+1])
            e = sum(a[m+1:])
            f=[b,c,d,e]
            f.sort()
            kari = f[-1]-f[0]
            if kari < res:
                res = kari
print(res)