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:
from itertools import accumulate

N = int(input())
A = list(map(int,input().split()))
A = list(accumulate(A))
ans = []

for i in range(N-3):
    for j in range(i+1, N-2):
        for k in range(j+1, N-1):
            list = []
            p = A[i]
            q = A[j]-A[i]
            r = A[k]-A[j]
            s = A[-1]-A[k]
            list = [p, q, r, s]
            ans.append(max(list) - min(list))

print(min(ans))

Submission status: Time Limit Exceeded

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

def found_cut(X):
    p1 = sum(X)/2
    count1 = 0
    for i in range(len(X)):
        count1 += X[i]
        if p1 <= count1:
            if abs(count1-p1) < abs(count1-X[i]-p1):
                index = i
                break
            else:
                index = i-1
                break
    return index

def found_ans(X,Y,Z,W):
    ans_list = []
    ans_list.append(sum(X))
    ans_list.append(sum(Y))
    ans_list.append(sum(Z))
    ans_list.append(sum(W))
    return max(ans_list)-min(ans_list)

ANS = []
for x in range(1,N-2):
    A_first = A[:x+1]
    A_second = A[x+1:]
    if len(A_first) >= 2 and len(A_second) >= 2:
        wp1 = found_cut(A_first)
        wp2 = found_cut(A_second)
        pattern3_1 = A_first[:wp1+1]
        pattern3_2 = A_first[wp1+1:]
        pattern3_3 = A_second[:wp2+1]
        pattern3_4 = A_second[wp2+1:]
        ANS.append(found_ans(pattern3_1,pattern3_2,pattern3_3,pattern3_4))
print(min(ANS))

Submission status: Time Limit Exceeded

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

def found_cut(X):
    p1 = sum(X)/2
    count1 = 0
    for i in range(len(X)):
        count1 += X[i]
        if p1 <= count1:
            if abs(count1-p1) < abs(count1-X[i]-p1):
                index = i
                break
            else:
                index = i-1
                break
    return index

def found_ans(X,Y,Z,W):
    ans_list = []
    ans_list.append(sum(X))
    ans_list.append(sum(Y))
    ans_list.append(sum(Z))
    ans_list.append(sum(W))
    return max(ans_list)-min(ans_list)

ANS = []
for x in range(N-1):
    A_first = A[:x+1]
    A_second = A[x+1:]

    if len(A_first) >= 3:
        yp1 = found_cut(A_first)
        pattern1_1 = A_first[:yp1+1]
        pattern1_2 = A_first[yp1+1:]
        if len(pattern1_2) != 1:
            yp2 = found_cut(pattern1_2)
            pattern1_2_1 = pattern1_2[:yp2+1]
            pattern1_2_2 = pattern1_2[yp2+1:]
            ANS.append(found_ans(pattern1_1,pattern1_2_1,pattern1_2_2,A_second))
        if len(pattern1_1) != 1:
            yp2 = found_cut(pattern1_1)
            pattern1_1_1 = pattern1_1[:yp2+1]
            pattern1_1_2 = pattern1_1[yp2+1:]
            ANS.append(found_ans(pattern1_1_1,pattern1_1_2,pattern1_2,A_second))
    if len(A_second) >= 3:
        zp1 = found_cut(A_second)
        pattern2_1 = A_second[:zp1+1]
        pattern2_2 = A_second[zp1+1:]
        if len(pattern2_2) != 1:
            zp2 = found_cut(pattern2_2)
            pattern2_2_1 = pattern2_2[:zp2+1]
            pattern2_2_2 = pattern2_2[zp2+1:]
            ANS.append(found_ans(pattern2_1,pattern2_2_1,pattern2_2_2,A_first))
        if len(pattern2_1) != 1:
            zp2 = found_cut(pattern2_1)
            pattern2_1_1 = pattern2_1[:zp2+1]
            pattern2_1_2 = pattern2_1[zp2+1:]
            ANS.append(found_ans(pattern2_1_1,pattern2_1_2,pattern2_2,A_first))
    if len(A_first) >= 2 and len(A_second) >= 2:
        wp1 = found_cut(A_first)
        wp2 = found_cut(A_second)
        pattern3_1 = A_first[:wp1+1]
        pattern3_2 = A_first[wp1+1:]
        pattern3_3 = A_second[:wp2+1]
        pattern3_4 = A_second[wp2+1:]
        ANS.append(found_ans(pattern3_1,pattern3_2,pattern3_3,pattern3_4))
print(min(ANS))

Submission status: Time Limit Exceeded

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

from itertools import accumulate
l=[0]+list(accumulate(a))
s=l[-1]
ans=10000000000000
import bisect
for i in range(2,N-1):
    ll=l[0:i+1]
    lr=l[i:N+1]
    lls=ll[-1]
    lrs=lr[-1]-lr[0]
    n=bisect.bisect_left(ll,lls//2)
    if n+1>=len(ll):
        n=len(ll)-2
    elif n+1<0:
        n=1
    if min(abs(lls-ll[n]*2),abs(lls-ll[n-1]*2),abs(lls-ll[n+1]*2))==abs(lls-ll[n]*2):
        s=ll[n]
        t=lls-ll[n]
    elif min(abs(lls-ll[n]*2),abs(lls-ll[n-1]*2),abs(lls-ll[n+1]*2))==abs(lls-ll[n-1]*2):
        s=ll[n-1]
        t=lls-ll[n-1]
    else:
        s=ll[n+1]
        t=lls-ll[n+1]
        
    
        
    n=bisect.bisect_left(lr,lr[0]+lrs//2)
    if n+1>=len(lr):
        n=len(lr)-2
    elif n-1<0:
        n=1
    if min(abs(lrs-lr[n]*2+2*lr[0]),abs(lrs-lr[n-1]*2+2*lr[0]),abs(lrs-lr[n+1]*2+2*lr[0]))==abs(lrs-lr[n]*2+2*lr[0]):
        u=lr[n]-lr[0]
        v=lrs-lr[n]+lr[0]
    elif min(abs(lrs-lr[n]*2+2*lr[0]),abs(lrs-lr[n-1]*2+2*lr[0]),abs(lrs-lr[n+1]*2+2*lr[0]))==abs(lrs-lr[n-1]*2+2*lr[0]):
        u=lr[n-1]-lr[0]
        v=lrs-lr[n-1]+lr[0]
    else:
        u=lr[n+1]-lr[0]
        v=lrs-lr[n+1]+lr[0]
    

    ans=min(ans,max(s,t,u,v)-min(s,t,u,v))

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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):
    l = S[:i]
    r = S[i:]
    j = bisect(l,l[-1]/2)
    k = bisect(r,(r[-1]+l[-1])/2)
    for p in {j-1,min(j,len(l)-2)}:
        for q in {k-1,min(k,len(r)-2)}:
            a,b,c,d = l[p],l[-1]-l[p],r[q]-l[-1],r[-1]-r[q]
            m = min(a,b,c,d)
            M = max(a,b,c,d)
            ans = min(ans,M-m)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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):
    l = S[:i]
    r = S[i:]
    j = bisect(l,l[-1]/2)
    k = bisect(r,(r[-1]+l[-1])/2)
    for p in {j-1,min(j,len(l)-2)}:
        for q in {k-1,min(k,len(r)-2)}:
            a,b,c,d = l[p],l[-1]-l[p],r[q]-l[-1],r[-1]-r[q]
            m = min(a,b,c,d)
            M = max(a,b,c,d)
            ans = min(ans,M-m)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    n, *a = map(int, string.split())
    ans = n * 10**9
    for i in range(1, n - 2):
        for j in range(2, n - 1):
            for k in range(3, n):
                s = [sum(a[:i]), sum(a[i:j]), sum(a[j:k]), sum(a[k:])]
                ans = min(ans, max(s) - min(s))
    return str(ans)


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

Submission status: Time Limit Exceeded

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

Solution code:
#!/usr/bin/env python3
import sys
import itertools


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

    A2 = list(itertools.accumulate(A))

    ans = float("inf")
    for pi in range(N-3):
        for qi in range(pi+1,N-2):
            for ri in range(qi+1,N-1):
                P = A2[pi]
                Q = A2[qi] - A2[pi]
                R = A2[ri] - A2[qi]
                S = A2[-1] - A2[ri]
                SS = [P,Q,R,S]
                ans = min(ans,max(SS)-min(SS))
    print(ans)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve(k=0,i=0,s=[]):
    if k==3:
        s.append(sum(a[i:]))
        return max(s)-min(s)
    re=[]
    tmp=0
    for ai in range(i,n-2+k):
        tmp+=a[ai]
        re.append(solve(k+1,ai+1,s+[tmp]))
    return min(re)

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

Submission status: Time Limit Exceeded

Solution code:

def get_num_f(data, sum_data):
    left1, left2 = 0, sum_data
    for i in range(len(data)- 1):
        if left1 + data[i] >= left2 - data[i]:
            pre_d = abs(left1 - left2)
            now_d = abs((left1 + data[i]) - (left2 - data[i]))
            if now_d < pre_d:
                left1 += data[i]
                left2 -= data[i]
            break
        left1 += data[i]
        left2 -= data[i]
    return left1, left2




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

    sum_left, sum_righ = sum(data[:2]), sum(data[2:])
    left1, left2 = get_num_f(data[:2], sum_left)
    righ1, righ2 = get_num_f(data[2:], sum_righ)

    ans = max(left1, left2, righ1, righ2) - min(left1, left2, righ1, righ2)

    for i in range(2, num - 2):
        sum_left += data[i]
        sum_righ -= data[i]
        left1, left2 = get_num_f(data[:i + 1], sum_left)
        righ1, righ2 = get_num_f(data[i + 1:], sum_righ)
        ans_kari = max(left1, left2, righ1, righ2) - min(left1, left2, righ1, righ2)

        if ans_kari < ans:
            ans = ans_kari

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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)
for i in range(2,N-1): # [1,i]と(i,N]に分割
    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)

Submission status: Time Limit Exceeded

Solution code:
###############################################################################

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

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
A = list(map(int, list(input().split()))) + [0]

w = 0
for i in range(N+1):
    p = w
    w += A[i]
    A[i] = p

S = [x for x in range(5)]
S[4] = N
KEI = [0] * 4
SA = -1

x = 0
for x in range(2, N-1):

    S[2] = x

    for offset in range(1, 4, 2):
        left = S[offset-1]
        right = S[offset+1]
        allvalue = A[right] - A[left]

        while right - left > 1:
            middle = (left + right) // 2
            if allvalue - ((A[middle] - A[S[offset-1]]) * 2 - (A[middle] - A[middle-1])) < 0:
                right = middle
            elif allvalue - ((A[middle] - A[S[offset-1]]) * 2 + (A[middle+1] - A[middle])) < 0:
                break
            else:
                left = middle

        S[offset] = middle

    for x in range(4):
        KEI[x] = A[S[x+1]] - A[S[x]]

    w = max(KEI) - min(KEI)
    SA = min(SA, w) if SA >= 0 else w

    #print((S, KEI, SA, w))


#print((A, KEI, S))
print(SA)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, list(input().split()))) + [0]

w = 0
for i in range(N+1):
    p = w
    w += A[i]
    A[i] = p

S = [x for x in range(5)]
S[4] = N
KEI = [0] * 4
SA = -1

i = 3
while True:

    s = 0
    for x in range(4):
        KEI[x] = A[S[x+1]] - A[S[x]]

    prew = w
    w = max(KEI) - min(KEI)

    SA = min(SA, w) if SA >= 0 else w
    if S[-3]+1 < S[-2] and w >= prew:
       S[-2] = S[-1] - 1
    else:
       SA = min(SA, w) if SA >= 0 else w

    #print((S, KEI, SA, w, prew))

    for x in range(3, 0, -1):
        if S[x]+1 < S[x+1]:
            S[x] += 1
            break
    else:
        break

    for y in range(x+1, 4):
        S[y] = S[y-1]+1

#print((A, KEI, S))
print(SA)

Submission status: Time Limit Exceeded

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=min(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)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
ruiseki = [0]*(n+1)

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

#右側が大きいときにTrueを返す。
def judge(begin,mid,end):
  if ruiseki[mid]-ruiseki[begin] < ruiseki[end]-ruiseki[mid]:
    return True
  else:
    return False

def solvediff(begin,mid,end):
  return abs( ruiseki[mid]-ruiseki[begin] - (ruiseki[end]-ruiseki[mid]) )

def solve_num1(begin,mid,end):
  return abs( ruiseki[mid]-ruiseki[begin] )

def solve_num2(begin,mid,end):
  return abs( ruiseki[end]-ruiseki[mid] )


ans = float("inf")
for i in range(2,n-1):
  
  #PQの探索
  ok = i
  ng = 0
  min_num = float("inf")
  while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if judge(0,mid,i):
      ng = mid
    else:
      ok = mid
    if min_num > solvediff(0,mid,i):
      min_num = solvediff(0,mid,i)
      num1 = solve_num1(0,mid,i)
      num2 = solve_num2(0,mid,i)
  
  #RSの探索
  ok = n
  ng = i
  min_num = float("inf")
  while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if judge(i,mid,n):
      ng = mid
    else:
      ok = mid
    if min_num > solvediff(i,mid,n):
      min_num = solvediff(i,mid,n)
      num3 = solve_num1(i,mid,n)
      num4 = solve_num2(i,mid,n)
      
  ans = min(ans, max(num1,num2,num3,num4) - min(num1,num2,num3,num4))
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
a = [int(i) for i in input().split(" ")]
ar = a[::-1]
a = [0] + a
ar = [0] + ar
s = [0] * (n + 1)
sr = [0] * (n + 1)

for i in range(1, n + 1):
    s[i] = a[i] + s[i - 1]
    sr[i] = ar[i] + sr[i - 1]
    
def bs(s, l, r, rr):
    if l == r:
        return l
    else:
        h = math.ceil((l + r) / 2)
        if s[h] * 2 > s[rr]:
            return bs(s, l, h - 1, rr)
        else:
            return bs(s, h, r, rr)
        
def min_2(s, i, rr):
    a = abs(s[i] - (s[rr] - s[i]))
    b = abs(s[i + 1] - (s[rr] - s[i + 1]))
    if a <= b:
        return i
    else:
        return i + 1
    
def f(a):
    return max(a) - min(a)

m_min = 2 * 10**14
for i in range(2, n - 1):
    pq = bs(s, 1, i, i)
    rs = bs(sr, 1, n - i, n - i)
    pq = min_2(s, pq, i)
    rs = min_2(sr, rs, n - i)
    m = f([s[pq], s[i] - s[pq], sr[rs], sr[n - i] - sr[rs]])
    if m < m_min:
        m_min = m
        
print(m_min)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

lst_accum = list(itertools.accumulate(lst))

def shaku(lst_accum, first):
    all_sum = lst_accum[-1]
    min_diff = 10**100
    for k in range(len(lst_accum)-1):
        diff = abs(all_sum - 2*lst_accum[k] + first)
        if min_diff > diff:
            index = k
            min_diff = diff
            P = lst_accum[k] - first
    return P, all_sum - P - first

min_diff = 10**100
for k in range(1, len(lst_accum)-2):
    lst_first = lst_accum[:k+1]
    lst_second = lst_accum[k+1:]
    #print('length_first: ', len(lst_first))
    P, Q = shaku(lst_first, 0)
    #print('length_second: ', len(lst_second))
    R, S = shaku(lst_second, lst_accum[k])
    min_diff = min(min_diff, max(P, Q, R, S) - min(P, Q, R, S))
print(min_diff)

Submission status: Time Limit Exceeded

Solution code:
# /user/bin/python
# -*- coding: utf-8 -*-
import sys 


## input
N = int(sys.stdin.readline().rstrip())
An = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
sum = [0] * (N+1)
for i in range(1, N+1):
  sum[i] = sum[i-1] + An[i]

ans = sys.maxsize
for i in range(2, N-1):
  ## Split BC
  left, right = 1, i
  while(right-left > 1):
    mid = (left + right) // 2
    sum_l = sum[mid]
    sum_r = sum[i] - sum[mid]
    if sum_l > sum_r:
      left, right = left, mid
    else:
      left, right = mid, right

  P1,Q1 = sum[left], sum[i] - sum[left]
  P2,Q2 = sum[right], sum[i] - sum[right]
  if abs(P1-Q1) >= abs(P2-Q2):
    P,Q = P2, Q2
  else:
    P,Q = P1, Q1

  ## Split DE
  left, right = i+1, N
  while(right-left > 1):
    mid = (left + right) // 2
    sum_l = sum[mid] - sum[i]
    sum_r = sum[N] - sum[mid]
    if sum_l > sum_r:
      left, right = left, mid
    else:
      left, right = mid, right

  R1,S1 = sum[left]-sum[i], sum[N]-sum[left]
  R2,S2 = sum[left+1]-sum[i], sum[N]-sum[left+1]
  if abs(R1-S1) >= abs(R2-S2):
    R,S = R2, S2
  else:
    R,S = R1, S1

  ans = min(ans, 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()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)
def spl_l(i,b):
    while abs(h[i]-2*h[b])>abs(h[i]-2*h[b+1]):
        b+=1
    return b
def spl_r(i,b):
    while abs(h[-1]-2*h[b]+h[i])>abs(h[-1]-2*h[b+1]+h[i]):
        b+=1
    return b
def calc(j,i,k,h):
    j=spl_l(i,j)
    k=spl_r(i,k)
    pqrs=[h[j],h[i]-h[j],h[k]-h[i],h[-1]-h[k]]
    ans=max(pqrs)-min(pqrs)
    return ans

j=0
k=2
ans=calc(j,1,k,h)
for i in range(2,N-2):
    ans=min(ans,calc(j,i,k,h))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def spl1(a):
    delta=[]
    for i in range(len(a)-1):
        delta.append(abs(a[-1]-2*a[i]))
    m=min(delta)
    index=[]
    for i in range(len(delta)):
        if delta[i]==m:
            index.append(i)
    return index
def spl2(a,b):
    delta=[]
    for i in range(len(a)-1):
        delta.append(abs(a[-1]-2*a[i]+b))
    m=min(delta)
    index=[]
    for i in range(len(delta)):
        if delta[i]==m:
            index.append(i)
    return index
N=int(input())
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)
ans=10**18
for i in range(N):
    if i>0 and i<N-2:
        for j in spl1(h[:i+1]):
            for k in spl2(h[i+1:],h[i]):
                p=h[j]
                q=h[i]-h[j]
                r=h[k+i+1]-h[i]
                s=h[-1]-h[k+i+1]
                if (max([p,q,r,s])-min([p,q,r,s]))<ans:
                    ans=max([p,q,r,s])-min([p,q,r,s])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def spl(a):
    delta=[]
    for i in range(len(a)-1):
        delta.append(abs(a[-1]-2*a[i]))
    m=min(delta)
    index=[]
    for i in range(len(delta)):
        if delta[i]==m:
            index.append(i)
    return index

N=int(input())
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)
ans=10**18
for i in range(N):
    if i>0 and i<N-2:
        g=[l-h[i] for l in h[i+1:]]
        for j in spl(h[:i+1]):
            for k in spl(g):
                p=h[j]
                q=h[i]-h[j]
                r=h[k+i+1]-h[i]
                s=h[-1]-h[k+i+1]
                if (max([p,q,r,s])-min([p,q,r,s]))<ans:
                    ans=max([p,q,r,s])-min([p,q,r,s])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + a[i]
cum.append(10**10)
mincost = 10 ** 10
for mid in range(2,n-1):
    ll = bisect.bisect_left(cum[:mid], cum[mid]//2)
    rl = bisect.bisect_left(cum[mid:], cum[mid+1] + (cum[n] - cum[mid+1])//2) + mid
    s = [0] * 4
    lw = abs(2*cum[ll] - cum[mid]) > abs(2*cum[ll-1] - cum[mid])
    rw = abs(2*cum[rl] - cum[mid] - cum[n]) > abs(2*cum[rl-1] - cum[mid] - cum[n])
    sums = [cum[ll - lw], cum[mid] - cum[ll - lw], cum[rl - rw] - cum[mid], cum[n] - cum[rl - rw]]
    mincost = min(mincost, max(sums) - min(sums))
print(mincost)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + a[i]
cum.append(10**10)
mincost = 10 ** 10
#print(cum)
for mid in range(2,n-1):
    ll = bisect.bisect_left(cum[:mid], cum[mid]//2)
    rl = bisect.bisect_left(cum[mid:], cum[mid+1] + (cum[n] - cum[mid+1])//2) + mid
    s = [0] * 4
    for i in range(4):
        s[0] = cum[ll - (i&1)]
        s[1] = cum[mid] - cum[ll - (i&1)]
        s[2] = cum[rl - ((i&2) >> 1)] - cum[mid]
        s[3] = cum[n] - cum[rl - ((i&2) >> 1)]
#        print(ll - (i&1), mid, rl - ((i&2) >> 1), s)
        mincost = min(mincost, max(s) - min(s))
print(mincost)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import bisect

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

    B = []
    t = 0
    for a in A:
        t += a
        B.append(t)

    T = B[N - 1]

    i2 = bisect.bisect_left(B, T / 2, lo = 1, hi = N - 2)
    i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
    i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)

    P = B[i1]
    Q = B[i2] - B[i1]
    R = B[i3] - B[i2]
    S = T - B[i3]

    min_d = max(P, Q, R, S) - min(P, Q, R, S)
    min_half = T / 2 - min_d
    max_half = T / 2 + min_d

    i2_lo = bisect.bisect_left(B, min_half, lo = 1, hi = N - 2)
    i2_hi = bisect.bisect_left(B, max_half, lo = i2_lo, hi = N - 2)

    for i2 in range(i2_lo, i2_hi + 1):
        if min_d * 2 < abs(T - 2 * B[i2]):
            continue

        i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
        i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)
        i1_lo = i1_hi = i1
        i3_lo = i3_hi = i3
        if B[i1] * 2 != B[i2] and 0 < i1:
            i1_lo -= 1
        if B[i3] * 2 != T + B[i2] and i2 + 1 < i3:
            i3_lo -= 1

        for i1 in range(i1_lo, i1_hi + 1):
            for i3 in range(i3_lo, i3_hi + 1):
                P = B[i1]
                Q = B[i2] - B[i1]
                R = B[i3] - B[i2]
                S = T - B[i3]
                d = max(P, Q, R, S) - min(P, Q, R, S)
                if d < min_d:
                    min_d = d


    print(min_d)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import bisect

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

    B = []
    t = 0
    for a in A:
        t += a
        B.append(t)

    i2 = bisect.bisect_left(B, B[N - 1] / 2, lo = 1, hi = N - 2)
    i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
    i3 = bisect.bisect_left(B, (B[N - 1] + B[i2]) / 2, lo = i2 + 1)

    P = B[i1]
    Q = B[i2] - B[i1]
    R = B[i3] - B[i2]
    S = B[N - 1] - B[i3]

    min_d = max(P, Q, R, S) - min(P, Q, R, S)
    min_half = B[N - 1] / 2 - min_d
    max_half = B[N - 1] / 2 + min_d

    i2_lo = bisect.bisect_left(B, min_half, lo = 1, hi = N - 2)
    i2_hi = bisect.bisect_left(B, max_half, lo = i2_lo, hi = N - 2)

    for i2 in range(i2_lo, i2_hi + 1):
        if min_d * 2 < abs(B[N - 1] - 2 * B[i2]):
            continue

        i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
        i3 = bisect.bisect_left(B, (B[N - 1] + B[i2]) / 2, lo = i2 + 1)
        i1_lo = i1_hi = i1
        i3_lo = i3_hi = i3
        if B[i1] * 2 != B[i2] and 0 < i1:
            i1_lo -= 1
        if B[i3] * 2 != B[N - 1] + B[i2] and i2 + 1 < i3:
            i3_lo -= 1

        for i1 in range(i1_lo, i1_hi + 1):
            for i3 in range(i3_lo, i3_hi + 1):
                P = B[i1]
                Q = B[i2] - B[i1]
                R = B[i3] - B[i2]
                S = B[N - 1] - B[i3]
                d = max(P, Q, R, S) - min(P, Q, R, S)
                if d < min_d:
                    min_d = d


    print(min_d)


if __name__ == '__main__':
    main()