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: Wrong Answer

Solution code:
import bisect
from itertools import accumulate


def fix(aac, l, k):
    ofs = aac[l - 1]
    sm = aac[-1] - ofs
    q = sm // k + ofs
    i = bisect.bisect(aac, q, lo=l)
    if i == l:
        i += 1
    print(l, k, sm, q, i, aac[i - 1] - ofs)
    return i


n = int(input())
aaa = list(map(int, input().split()))
aac = [0] + list(accumulate(aaa))
sm = aac[-1]

q1, q2, q3 = sm // 4, sm // 2, sm * 3 // 4

i1 = bisect.bisect(aac, q1)
i2 = bisect.bisect(aac, q2, lo=i1)
i3 = bisect.bisect(aac, q3, lo=i2)

k = 5
ans = float('inf')
for j1 in range(max(1, i1 - k), min(n + 1, i1 + k)):
    for j2 in range(max(j1 + 1, i2 - k), min(n + 1, i2 + k)):
        for j3 in range(max(j2 + 1, i3 - k), min(n + 1, i3 + k)):
            s = [
                aac[j1],
                aac[j2] - aac[j1],
                aac[j3] - aac[j2],
                aac[-1] - aac[j3]
            ]
            ans = min(ans, max(s) - min(s))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def ii():
    return int(input())


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def separate2(A):
    s = sum(A)
    k = 0
    N = len(A)
    for i in range(N):
        k += A[i]
        if k >= s // 2:
            return i


def max_min_diff(*args):
    return max(args) - min(args)


def main():
    N = ii()
    A = lii()
    ai = separate2(A)

    res = 1e10

    for ix in range(ai-3, ai+3+1):
        F = A[:ix]
        L = A[ix:]
        if len(F) <= 1 or len(L) <= 1: continue
        fi = separate2(F)
        li = separate2(L)
        for j in range(fi-3, fi+3+1):
            B = F[:j]
            C = F[j:]
            if len(B) == 0 or len(C) == 0: continue
            P = sum(B)
            Q = sum(C)
            for k in range(li-3, li+3+1):
                D = L[:k]
                E = L[k:]
                if len(D) == 0 or len(E) == 0: continue
                R = sum(D)
                S = sum(E)
                res = min(res, max_min_diff(P, Q, R, S))

    return res


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
# D
N = int(input())
A_list = list(map(int, input().split()))

# cumsum from left
a = 0
A_left = []
for i in range(N):
    a += A_list[i]
    A_left.append(a)
    
# cumsum from right
a = 0
A_right = []
for i in range(N):
    a += A_list[N-1-i]
    A_right.append(a)

# binary search
def search_left(n):
    # 0:n
    S = A_left[n-1]
    S2 = S / 2
    
    left = 0
    right = n-1
    
    temp = abs(S2 - A_left[0])
    
    min_s = min([A_right[0], S - A_right[0]])
    max_s = S - min_s
    
    while left < right - 1:
        center = (left + right) // 2
        if abs(S2 - A_left[center]) < temp:
            min_s = min([A_left[center], S - A_left[center]])
            max_s = S - min_s 
            temp = abs(S2 - A_left[center])

        if A_left[center] < S2:
            left, center = center, (center+right) // 2
        else:
            right, center = center, (center+left) // 2
            
    return min_s, max_s
    
def search_right(n):
    # 0:n
    S = A_right[n-1]
    S2 = S / 2
    
    left = 0
    right = n-1
    
    temp = abs(S2 - A_right[0])
    
    min_s = min([A_right[0], S - A_right[0]])
    max_s = S - min_s
    
    while left < right - 1:
        center = (left + right) // 2
        if abs(S2 - A_right[center]) < temp:
            min_s = min([A_right[center], S - A_right[center]])
            max_s = S - min_s 
            temp = abs(S2 - A_right[center])

        if A_right[center] < S2:
            left, center = center, (center+right) // 2
        else:
            right, center = center, (center+left) // 2
            
    return min_s, max_s

# B | C split
res = A_left[N-1]
for s in range(2, N-1):
    a, b = search_left(s)
    c, d = search_right(N-s)
    r = max([a,b,c,d]) - min([a,b,c,d])
    if r < res:
        res = r
if N == 4:
    res = max(A_list) - min(A_list)
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
l = list(map(int ,input().split()))
a1 = 0
b1 = sum(l)
for i in range(N):
    c1 = abs(a1-b1)
    a1 += l[i]
    b1 -= l[i]
    if c1 < abs(a1-b1):
        break
a2 = 0
b2 = sum(l[:i])
for j in range(i):
    c2 = abs(a2-b2)
    a2 += l[j]
    b2 -= l[j]
    if c2 < abs(a2-b2):
        a2 -=l[j]
        b2 +=l[j]
        break
a3 = 0
b3 = sum(l[i:])
for k in range(i,N):
    c3 = abs(a3-b3)
    a3 += l[k]
    b3 -= l[k]
    if c3< abs(a3-b3):
        a3 -=l[k]
        b3 +=l[k]
        break
a4 = 0
b4 = sum(l[j:k])
for m in range(j,k):
    c4 = abs(a4-b4)
    a4 += l[m]
    b4 -= l[m]
    if c4< abs(a4-b4):
        a4 -=l[m]
        b4 +=l[m]
        break

print(max(a2,a4,b4,b3)-min(a2,a4,b4,b3))

Submission status: Wrong Answer

Solution code:
def ii():
    return int(input())


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def separate2(A):
    s = sum(A)
    k = 0
    N = len(A)
    for i in range(N):
        k += A[i]
        if k >= s // 2:
            return i


def max_min_diff(*args):
    return max(args) - min(args)


def main():
    N = ii()
    A = lii()
    ai = separate2(A)

    res = 1e10

    for ix in [ai-1, ai, ai+1]:
        F = A[:ix]
        L = A[ix:]
        if len(F) <= 1 or len(L) <= 1: continue
        fi = separate2(F)
        li = separate2(L)
        for j in [fi-1, fi, fi+1]:
            B = F[:j]
            C = F[j:]
            if len(B) == 0 or len(C) == 0: continue
            P = sum(B)
            Q = sum(C)
            for k in [li-1, li, li+1]:
                D = L[:k]
                E = L[k:]
                if len(D) == 0 or len(E) == 0: continue
                R = sum(D)
                S = sum(E)
                res = min(res, max_min_diff(P, Q, R, S))

    return res


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
# D
N = int(input())
A_list = list(map(int, input().split()))

# cumsum from left
a = 0
A_left = []
for i in range(N):
    a += A_list[i]
    A_left.append(a)
    
# cumsum from right
a = 0
A_right = []
for i in range(N):
    a += A_list[N-1-i]
    A_right.append(a)

# binary search
def search_left(n):
    # 0:n
    S = A_left[n-1]
    S2 = S / 2
    
    left = 0
    right = n-1
    
    temp = abs(S2 - A_left[0])
    
    min_s = min([A_right[0], S - A_right[0]])
    max_s = S - min_s
    
    while left < right - 1:
        center = (left + right) // 2
        if abs(S2 - A_left[center]) < temp:
            min_s = min([A_left[center], S - A_left[center]])
            max_s = S - min_s 
            temp = abs(S2 - A_left[center])

        if A_left[center] < S2:
            left, center = center, (center+right) // 2
        else:
            right, center = center, (center+left) // 2
            
    return min_s, max_s
    
def search_right(n):
    # 0:n
    S = A_right[n-1]
    S2 = S / 2
    
    left = 0
    right = n-1
    
    temp = abs(S2 - A_right[0])
    
    min_s = min([A_right[0], S - A_right[0]])
    max_s = S - min_s
    
    while left < right - 1:
        center = (left + right) // 2
        if abs(S2 - A_right[center]) < temp:
            min_s = min([A_right[center], S - A_right[center]])
            max_s = S - min_s 
            temp = abs(S2 - A_right[center])

        if A_right[center] < S2:
            left, center = center, (center+right) // 2
        else:
            right, center = center, (center+left) // 2
            
    return min_s, max_s

# B | C split
res = A_left[N-1]
for s in range(2, N-1):
    a, b = search_left(s)
    c, d = search_right(N-s)
    r = max([a,b,c,d]) - min([a,b,c,d])
    if r < res:
        res = r
        
print(res)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=float('inf')
tmp=0
ca=[tmp]
for x in a:
  tmp+=x
  ca.append(tmp)
from bisect import bisect_left as bl
for i in range(2,n-1):
  bc=ca[:i+1]
  de=ca[i+1:]
  de=[0]+[x-ca[i] for x in de]
  sumbc=bc[-1]
  bcidx=bl(bc,sumbc//2)
  p=bc[bcidx]
  q=bc[-1]-bc[bcidx]
  if bcidx>1:
    np=bc[bcidx-1]
    nq=bc[-1]-bc[bcidx-1]
    if abs(p-q)>abs(np-nq):p,q=np,nq

  sumde=de[-1]
  deidx=bl(de,sumde//2)
  r=de[deidx]
  s=de[-1]-de[deidx]
  if deidx>1:
    nr=de[deidx-1]
    ns=de[-1]-de[deidx-1]
    if abs(r-s)>abs(nr-ns):r,s=nr,ns
  ans=min(ans,max(p,q,r,s)-min(p,q,r,s))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
    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]
    
    ans = int(1e15)
    for i in range(n):
        sub = []
        for l, r, ll, rr in zip([0, i], [i, n], [0, i], [i, n]):
            while r-l > 1:
                k = (r+l) // 2
                if s[k] - s[ll] < s[rr] - s[k]:
                    l = k
                else:
                    r = k

            if abs(s[ll] + s[rr] - s[l]*2) > abs(s[ll] + s[rr] - s[r]*2):
                k = r
            else:
                k = l
            sub.append(s[k] - s[ll])
            sub.append(s[rr] - s[k])
        judge = max(sub) - min(sub)
        ans = min(ans, judge)
    
    print(ans)


    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    sa = [0,a[0]]
    for i in a[1::]:
        sa.append(sa[-1]+i)

    mi = 10**18
    ll = 1
    rr = 3
    for ci in range(2,n-1):
        ls = sa[ci]
        rs = sa[-1]
        nms = []
        pld = 10**18
        for l in range(ll,ci):
            al = sa[l]
            d = abs(ls-2*al)
            if pld > d:
                pld = d
                sl = (al,ls-al)
            else:
                ll = l-1
                break
        nms.append(sl[0])
        nms.append(sl[1])
        pld = 10**18
        for r in range(rr,n):
            ar = sa[r]
            d = abs(rs+ls-2*ar)
            if pld > d:
                pld = d
                sl = (rs-ar,ar-ls)
            else:
                rr = r-1
                break
        nms.append(sl[0])
        nms.append(sl[1])
        d = max(nms)-min(nms)
        if mi > d:
            mi = d

    print(mi)


    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
from numba import jit

n = int(input())
sa = np.cumsum(np.array([0]+list(map(int,input().split()))))

@jit
def solve():
    ans = 10**15
    for i in range(1,n-2):
        left = sa[i+1]
        right = sa[-1] - sa[i+1]
        lsplit = min(sa[:i+1].searchsorted(left//2, side="right") - 2, i-1)
        rsplit = min(sa[i+1:].searchsorted(right//2 + left, side="right") + i-1, n-2)
        lleft = [(sa[lsplit + 1],sa[i+1] - sa[lsplit + 1]),(sa[lsplit + 2],sa[i+1] - sa[lsplit + 2])]
        rright = [(sa[rsplit+1] - sa[i+1],sa[-1] - sa[rsplit+1]),(sa[rsplit+2] - sa[i+1],sa[-1] - sa[rsplit+2])]
        for s,t in [(0,0),(0,1),(1,0),(1,1)]:
            l = lleft[s]
            r = rright[t]
            m = min(l+r)
            M = max(l+r)
            ans = min(ans,M-m)
    return ans

print(solve())

Submission status: Time Limit Exceeded

Solution code:
# arc 100 D

def ruiseki(n,array):
    res = [0]*(n+1)
    for i in range(n):
        res[i+1] = res[i] + array[i]
    return res

n = int(input())
A = list(map(int,input().split()))
sa = ruiseki(n,A)

from bisect import bisect_right

ans = 10**15
for i in range(1,n-2):
    left = sa[i+1]
    right = sa[-1] - sa[i+1]

    lsplit = min(bisect_right(sa[:i+1],left//2) - 2,i-1)
    rsplit = min(bisect_right(sa[i+1:],right//2 + left) + i-1,n-2)
    lleft = [(sa[lsplit + 1],sa[i+1] - sa[lsplit + 1]),(sa[lsplit + 2],sa[i+1] - sa[lsplit + 2])]
    rright = [(sa[rsplit+1] - sa[i+1],sa[-1] - sa[rsplit+1]),(sa[rsplit+2] - sa[i+1],sa[-1] - sa[rsplit+2])]
    lM = min(max(lleft[0]),max(lleft[1]))
    rM = min(max(rright[0]),max(rright[1]))

    M = max(lM,rM)
    m = min(sa[i+1]-lM,sa[-1] - sa[i+1] - rM)
    ans = min(ans, M-m)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
n=int(input())
l=[0]+list(accumulate(list(map(int,input().split()))))
ans=float("INf")

for center in range(2,n-1):
    lnow=1
    laim=l[center]//2
    while lnow+1<center and l[lnow+1]<laim:lnow+=1
    rnow=center+1
    raim=(l[-1]-l[center])//2
    while rnow+1<n and l[rnow+1]-l[center]<raim:rnow+=1
    for i,j in ((0,0),(1,0),(1,1),(0,1)):
        if lnow+i<center and rnow+j<n:
            a,b,c,d=sorted([l[lnow+i],l[center]-l[lnow+i],l[rnow+j]-l[center],l[-1]-l[rnow+j]])
            ans=min(ans,d-a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# arc 100 D

def ruiseki(n,array):
    res = [0]*(n+1)
    for i in range(n):
        res[i+1] = res[i] + array[i]
    return res

n = int(input())
A = list(map(int,input().split()))
sa = ruiseki(n,A)

from bisect import bisect_right

ans = 10**15
for i in range(1,n-2):
    left = sa[i+1]
    right = sa[-1] - sa[i+1]

    lsplit = min(bisect_right(sa[:i+1],left//2) - 2,i-1)
    rsplit = min(bisect_right(sa[i+1:],right//2 + left) + i-1,n-2)
    lleft = [(sa[lsplit + 1],sa[i+1] - sa[lsplit + 1]),(sa[lsplit + 2],sa[i+1] - sa[lsplit + 2])]
    rright = [(sa[rsplit+1] - sa[i+1],sa[-1] - sa[rsplit+1]),(sa[rsplit+2] - sa[i+1],sa[-1] - sa[rsplit+2])]
    for s,t in [(0,0),(0,1),(1,0),(1,1)]:
        l = lleft[s]
        r = rright[t]
        m = min(l+r)
        M = max(l+r)
        ans = min(ans,M-m)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# arc 100 D

def ruiseki(n,array):
    res = [0]*(n+1)
    for i in range(n):
        res[i+1] = res[i] + array[i]
    return res

n = int(input())
A = list(map(int,input().split()))
sa = ruiseki(n,A)

from bisect import bisect_right
import itertools
ans = 10**15
for i in range(1,n-2):
    left = sa[i+1]
    right = sa[-1] - sa[i+1]

    lsplit = min(bisect_right(sa[:i+1],left//2) - 2,i-1)
    rsplit = min(bisect_right(sa[i+1:],right//2 + left) + i-1,n-2)
    lleft = [(sa[lsplit + 1],sa[i+1] - sa[lsplit + 1]),(sa[lsplit + 2],sa[i+1] - sa[lsplit + 2])]
    rright = [(sa[rsplit+1] - sa[i+1],sa[-1] - sa[rsplit+1]),(sa[rsplit+2] - sa[i+1],sa[-1] - sa[rsplit+2])]
    for l,r in itertools.product(lleft,rright):
        m = min(l+r)
        M = max(l+r)
        ans = min(ans,M-m)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    import itertools
    import math
    B = list(itertools.accumulate(A))
    C = [i*A[i] for i in range(N)]
    D = list(itertools.accumulate(C))

    g = math.floor(D[-1]/B[-1])
    g1 = math.floor(D[g]/B[g])
    g2 = math.floor((D[-1]-D[g])/(B[-1]-B[g]))

    answer = pow(10, 10)
    for i in range(-100, 101):
        for j in range(-100, 101):
            for k in range(-100, 101):
                if 0 <= g1+i and g1+i < g+j and g+j < g2+k and g2+k < N:
                    m = min(B[g1+i], B[g+j]-B[g1+i], B[g2+k]-B[g+j], B[-1]-B[g2+k])
                    M = max(B[g1+i], B[g+j]-B[g1+i], B[g2+k]-B[g+j], B[-1]-B[g2+k])
                    answer = min(answer, M-m)

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

ans = 10**20
for i in range(2, N-1):
    m = bisect.bisect(S[:i], S[:i][-1]//2)

    if m == 0:
        L = [S[:i][0], S[:i][-1]-S[:i][0]]
    else:
        L = [S[:i][m], S[:i][-1]-S[:i][m]]
        L2 = [S[:i][m-1], S[:i][-1]-S[:i][m-1]]

        if(abs(L[0]-L[1]) > abs(L2[0]-L2[1])): L = L2

    m = bisect.bisect(S[i:], (S[i:][-1]+S[:i][-1])//2)
    if m == 0:
        R = [S[i:][0]-S[:i][-1], S[i:][-1]-S[i:][0]]
    else:
        R = [S[i:][m]-S[:i][-1], S[i:][-1]-S[i:][m]]
        R2 = [S[i:][m-1]-S[:i][-1], S[i:][-1]-S[i:][m-1]]

        if(abs(R[0]-R[1]) > abs(R2[0]-R2[1])): R = R2

    #print(L, end="")
    #print(R)

    ans = min(ans, max(L[0],L[1],R[0],R[1]) - min(L[0],L[1],R[0],R[1]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

ans = 1e18
for i in range(2, N-1):
    left = S[:i]
    m = bisect.bisect(left, left[-1]/2)

    if m == 0:
        L = [left[0], left[-1]-left[0]]
    else:
        L = [left[m], left[-1]-left[m]]
        L2 = [left[m-1], left[-1]-left[m-1]]

        if(abs(L[0]-L[1]) > abs(L2[0]-L2[1])): L = L2

    right = S[i:]
    m = bisect.bisect(right, (right[-1]-left[-1])/2 + left[-1])
    if m == 0:
        R = [right[0]-left[-1], right[-1]-right[0]]
    else:
        R = [right[m]-left[-1], right[-1]-right[m]]
        R2 = [right[m-1]-left[-1], right[-1]-right[m-1]]

        if(abs(R[0]-R[1]) > abs(R2[0]-R2[1])): R = R2

    #print(L)
    #print(R)

    ans = min(ans, max(L[0],L[1],R[0],R[1]) - min(L[0],L[1],R[0],R[1]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ARC100D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


import numpy as np
import bisect
n = int(input())
a = np.array(list(map(int, input().split())))
ca = [None] * n #ca[i] = a0~aiの和
# s = 0
# for i,num in enumerate(a):
#     s += a[i]
#     ca[i] = s
ca = a.cumsum()

def sub(l, init):
    if len(l)==0:
        return 0,0
    elif len(l)==1:
        return 0,l[0]-init
    target = (init + l[-1])/2
    i = bisect.bisect_right(l, target)
    p1 = (l[i]-init, l[-1]-l[i])
    p2 = (l[i-1]-init, l[-1]-l[i-1])
    if abs(p1[0] - p1[1]) < abs(p2[0] - p2[1]):
        return min(p1), max(p1)
    else:
        return min(p2), max(p2)
best = 10**15
for i in range(1,n):
    p1 = sub(ca[:i], 0)
    p2 = sub(ca[i:], ca[i-1])
    nn = max(p1[1]-p2[0], p2[1]-p1[0], p1[1]-p1[0], p2[1]-p2[0])
    best = min(best, nn)
print(best)

Submission status: Time Limit Exceeded

Solution code:
# ARC100D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


import bisect
n = int(input())
a = list(map(int, input().split()))
ca = [None] * n #ca[i] = a0~aiの和
s = 0
for i,num in enumerate(a):
    s += a[i]
    ca[i] = s
    
def sub(l, init):
    if len(l)==0:
        return 0,0
    elif len(l)==1:
        return 0,l[0]-init
    target = (init + l[-1])/2
    i = bisect.bisect_right(l, target)
    p1 = (l[i]-init, l[-1]-l[i])
    p2 = (l[i-1]-init, l[-1]-l[i-1])
    if abs(p1[0] - p1[1]) < abs(p2[0] - p2[1]):
        return min(p1), max(p1)
    else:
        return min(p2), max(p2)
best = 10**15
for i in range(1,n):
    p1 = sub(ca[:i], 0)
    p2 = sub(ca[i:], ca[i-1])
    nn = max(p1[1]-p2[0], p2[1]-p1[0], p1[1]-p1[0], p2[1]-p2[0])
    best = min(best, nn)
print(best)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()

def min_max(arr):
    """リストの中を二つに分けて、総和の小さい方と大きい方を返す"""
    left = 0; right = len(arr)-1
    l_total = arr[left]
    r_total = arr[right]
    while left + 1 < right:
        if l_total <= r_total:
            left += 1
            l_total += arr[left]
        else:
            right -= 1
            r_total += arr[right]
    mi, ma = min(l_total, r_total), max(l_total, r_total)
    return mi, ma

answer = 10 ** 15
mid = N // 2
used = set([0, 1, N-1])

def F(l, mid, r):
    global answer, used
    used.add(mid)
    l_min, l_max = min_max(A[:mid])
    r_min, r_max = min_max(A[mid:])
    temp = max(l_max, r_max) - min(l_min, r_min)
    if temp < answer:
        answer = temp
    if l_min <= r_min:
        m = (mid+r)//2
        if m not in used:
            F(mid, m, r)
    else:
        m = (mid+l)//2
        if m not in used:
            F(l, m, mid)
    if l_max >= r_max:
        m = (mid+l)//2
        if m not in used:
            F(l, m, mid)
    else:
        m = (mid+r)//2
        if m not in used:
            F(mid, m, r)

F(0, mid, N-1)
print(answer)
# 08

Submission status: Time Limit Exceeded

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

b = [0]
for i in a:
    b.append(b[-1] + i)


def get(i, j):
    i, j = min(i, j), max(i, j)
    return b[j]-b[i]


j = 0
k = 0
ans = 10**18
for i in range(n):
    while j < n and abs(get(0, j) - get(j, i)) > abs(get(0, j + 1) - get(j + 1, i)):
        j += 1
    while k < n and abs(get(i, k) - get(k, n)) > abs(get(i, k + 1) - get(k + 1, n)):
        k += 1
    an = [get(0, j), get(j, i), get(i, k), get(k, n)]
    ans = min(ans,max(an)-min(an))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(map(int,input().split()))
a=[0]
for _ in range(n):
    a.append(sum(s[:_+1]))

ans=10**9
f=1
g=3
for i in range(2,n-1):
    while f < i and abs(a[f]-(a[i]-a[f])) > abs(a[f+1]-(a[i]-a[f+1])):
        f+=1
    while g < n and abs(a[g]-a[i]-(a[n]-a[g])) > abs(a[g+1]-a[i]-(a[n]-a[g+1])):
        g+=1
    ls=[a[f],a[i]-a[f],a[g]-a[i],a[n]-a[g]]
    ans=min(ans,max(ls)-min(ls))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=10**9
f=1
g=3
for i in range(2,n-1):
    while f < i and abs(sum(a[:f])-sum(a[f:i])) > abs(sum(a[:f+1])-sum(a[f+1:i])):
        f+=1
    while g < n and abs(sum(a[i:g])-sum(a[g:])) > abs(sum(a[i:g+1])-sum(a[g+1:])):
        g+=1
    ans=min(ans,max(abs(sum(a[:f])-sum(a[f:i])),abs(sum(a[:f])-sum(a[i:g])),abs(sum(a[:f])-sum(a[g:]))
                ,abs(sum(a[f:i])-sum(a[i:g])),abs(sum(a[f:i])-sum(a[g:])),abs(sum(a[i:g])-sum(a[g:]))))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
from collections import deque
ans=10**9
f=1
g=3
for i in range(2,n-1):
    l=a[:i]
    r=a[i:]
    k1=deque(a[:f])
    k2=deque(a[f:i])
    k3=deque(a[i:g])
    k4=deque(a[g:])
    while len(k2) > 1 and abs(sum(k1)-sum(k2)) > abs((sum(k1)+k2[0])-(sum(k2)-k2[0])):
        k1.append(k2.popleft())
        f+=1
    while len(k4) > 1 and abs(sum(k3)-sum(k4)) > abs((sum(k3)+k4[0])-(sum(k4)-k4[0])):
        k3.append(k4.popleft())
        g+=1
    ans=min(ans,max(abs(sum(k1)-sum(k2)),abs(sum(k1)-sum(k3)),abs(sum(k1)-sum(k4))
                ,abs(sum(k2)-sum(k3)),abs(sum(k2)-sum(k4)),abs(sum(k3)-sum(k4))))
print(ans)

Submission status: Time Limit Exceeded

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

ans = []
for _ in range(2, N-1):
    p = A[:_]
    q = A[_:]
    P = sum(p)
    Q = sum(q)
    p_sa = 10**15
    q_sa = 10**15
    for i in range(1,len(p)):
        s = sum(p[:i])
        sa = abs(P-s*2)
        if sa < p_sa:
            n = [s,P-s]
            p_sa = sa
    for i in range(1,len(q)):
        s = sum(q[:i])
        sa = abs(Q - s*2)
        if sa < q_sa:
            m = [s,Q-s]
            q_sa = sa
    ans.append(max(n+m)-min(n+m))
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
total = 0
mini = maxi = a[0]
s = list()
for i in a:
    if i > maxi:
        maxi = i
    if i < mini:
        mini = i
    total += i
    s.append(total)

minimini=1000000000
for i2 in range(1, n-2):
    i1 = i2//2
    t = s[i2] - 2*s[i1]
    at = abs(t)
    while True:
        if t < 0:
            it = i1 - 1
        else:
            it = i1 + 1
        if it < 0 or it >= i2:
            break
        tt = s[i2] - 2*s[it]
        if at <= abs(tt):
            break
        at = abs(tt)
        t = tt
        i1 = it
    i3 = i1
    i1 = i2 + (n - i2)//2
    t = (s[-1] - s[i1]) - (s[i1] - s[i2])
    at = abs(t)
    while True:
        if t < 0:
            it = i1 - 1
        else:
            it = i1 + 1
        if it <= i2 or it >= n:
            break
        tt = s[-1] - 2*s[it] + s[i2]
        if at <= abs(tt):
            break
        at = abs(tt)
        t = tt
        i1 = it
    mini = maxi = s[i3]
    s2 = s[i2] - s[i3]
    if mini > s2:
        mini = s2
    if maxi < s2:
        maxi = s2
    s2 = s[i1] - s[i2]
    if mini > s2:
        mini = s2
    if maxi < s2:
        maxi = s2
    s2 = s[-1] - s[i1]
    if mini > s2:
        mini = s2
    if maxi < s2:
        maxi = s2
    minitmp = maxi - mini
    if minitmp < minimini:
        minimini = minitmp
#print(i3, i2, i1)
#print(s[i3], s[i2], s[i1], s[-1])
#print(s[i3], s[i2]-s[i3], s[i1]-s[i2], s[-1]-s[i1])
print(minimini)

Submission status: Time Limit Exceeded

Solution code:
def check_min(i1, i2, i3):
    mini = maxi = s1 = s[i1]
    s2 = s[i2] - s1
    if mini < s2:
        mini = s2
    if maxi > s2:
        maxi = s2
    s3 = s[i3] - s2
    if mini < s3:
        mini = s3
        maxi = s3
    s4 = s[-1] - s3
    if mini < s4:
        mini = s4
    if maxi > s4:
        maxi = s4
    s3 = s[i3] - s4
    return maxi - mini

n = int(input())
a = list(map(int, input().split()))
total = 0
mini = maxi = a[0]
s = list()
for i in a:
    if i > maxi:
        maxi = i
    if i < mini:
        mini = i
    total += i
    s.append(total)

minmin=1000000000
for i1 in range(0, n-2):
    s1 = s[i1]
    for i2 in range(i1+1, n-1):
        s2 = s[i2] - s[i1]
        if s1 > s2:
            min1 = s2
            max1 = s1
        else:
            min1 = s1
            max1 = s2
        for i3 in range(i2+1, n):
            s3 = s[i3] - s[i2]
            s4 = s[-1] - s[i3]
            if s3 > s4:
                min2 = s4
                max2 = s3
            else:
                min2 = s3
                max2 = s4
            if max1 > max2:
                max3 = max1
            else:
                max3 = max2
            if min1 > min2:
                min3 = min2
            else:
                min3 = min1
            minmin1 = max3 - min3
            if minmin > minmin1:
                minmin = minmin1
print(minmin)

Submission status: Time Limit Exceeded

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

ll = sorted(a)[-1]
ss = sum(a)
minmin=1000000000
for i10 in range(1,n-2):
    s1 = sum(a[0:i10])
    if s1 > ss // 4 - ll:
        break
i10 -= 1
for i1 in range(i10,n-2):
    s1 = sum(a[0:i1])
    if s1 > ss // 4 + ll:
        break
    for i2 in range(i1+1, n-1):
        s2 = sum(a[i1:i2])
        if s1 > s2:
            min1 = s2
            max1 = s1
        else:
            min1 = s1
            max1 = s2
        for i3 in range(i2, n):
            s3 = sum(a[i2:i3])
            s4 = sum(a[i3:])
            if s3 > s4:
                min2 = s4
                max2 = s3
            else:
                min2 = s3
                max2 = s4
            if max1 > max2:
                max3 = max1
            else:
                max3 = max2
            if min1 > min2:
                min3 = min2
            else:
                min3 = min1
            minmin1 = max3 - min3
            if minmin > minmin1:
                minmin = minmin1
#            print("{} {} {}: {} {} {} {} -> {}".format(i1, i2, i3, s1, s2, s3, s4, max3 - min3))
print(minmin)

Submission status: Time Limit Exceeded

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

ll = sorted(a)[-1]
ss = sum(a)
minmin=1000000000
for i10 in range(1,n-2):
    s1 = sum(a[0:i10])
    if s1 > ss // 4 - ll:
        break
for i1 in range(i10,n-2):
    s1 = sum(a[0:i1])
    for i20 in range(i1+1, n-1):
        s2 = sum(a[i1:i20])
        if s2 > ss // 4 - ll:
            break
    for i2 in range(i20, n-1):
        s2 = sum(a[i1:i2])
        if s1 > s2:
            min1 = s2
            max1 = s1
        else:
            min1 = s1
            max1 = s2
        for i3 in range(i2+1, n):
            s3 = sum(a[i2:i3])
            s4 = sum(a[i3:])
            if s3 > s4:
                min2 = s4
                max2 = s3
            else:
                min2 = s3
                max2 = s4
            if max1 > max2:
                max3 = max1
            else:
                max3 = max2
            if min1 > min2:
                min3 = min2
            else:
                min3 = min1
            minmin1 = max3 - min3
            if minmin > minmin1:
                minmin = minmin1
#            print("{} {} {}: {} {} {} {} -> {}".format(i1, i2, i3, s1, s2, s3, s4, max3 - min3))
print(minmin)