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:
def solve():
    N = int(input())
    A = tuple(map(int, input().split()))

    from itertools import accumulate
    CA = list(accumulate(A))

    mindiff = CA[-1]
    for c in range(1,N-2):
        # left side
        p = 0
        q = CA[-1]
        for i in range(0, c):
            pi = CA[i]
            qi = CA[c] - CA[i]
            if abs(pi- qi) < abs(p - q):
                p = pi; q = qi
            else:
                break

        # right side
        r = 0
        s = CA[-1]
        for i in range(c+1, N):
            ri = CA[i] - CA[c]
            si = CA[-1] - CA[i]
            if abs(ri- si) < abs(r - s):
                r = ri; s = si
            else:
                break
    
        mindiff = min(mindiff, max(p, q, r, s) - min(p, q, r, s))
    return mindiff
print(solve())

Submission status: Time Limit Exceeded

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

from itertools import accumulate
CA = list(accumulate(A))

mindiff = CA[-1]
for c in range(1,N-2):
    # left side
    p = 0
    q = CA[-1]
    for i in range(0, c):
        pi = CA[i]
        qi = CA[c] - CA[i]
        if abs(pi- qi) < abs(p - q):
            p = pi; q = qi
        else:
            break

    # right side
    r = 0
    s = CA[-1]
    for i in range(c+1, N):
        ri = CA[i] - CA[c]
        si = CA[-1] - CA[i]
        if abs(ri- si) < abs(r - s):
            r = ri; s = si
        else:
            break
    
    mindiff = min(mindiff, max(p, q, r, s) - min(p, q, r, s))
print(mindiff)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = tuple(map(int, input().split()))
CA = []
cumsum = 0
for a in A:
    cumsum += a
    CA.append(cumsum)

mindiff = CA[-1]
for c in range(1,N-2):
    # left side
    p = 0
    q = CA[-1]
    for i in range(0, c):
        pi = CA[i]
        qi = CA[c] - CA[i]
        if abs(pi- qi) <= abs(p - q):
            p = pi; q = qi
        else:
            break

    # right side
    r = 0
    s = CA[-1]
    for i in range(c+1, N):
        ri = CA[i] - CA[c]
        si = CA[-1] - CA[i]
        if abs(ri- si) <= abs(r - s):
            r = ri; s = si
        else:
            break
    
    mindiff = min(mindiff, max([p, q, r, s]) - min([p, q, r, s]))
print(mindiff)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = tuple(map(int, input().split()))
CA = []
cumsum = 0
for a in A:
    cumsum += a
    CA.append(cumsum)

mindiff = CA[-1]
for i in range(0, N-3):
    p = CA[i]
    for j in range(i+1, N-2):
        q =  CA[j] - CA[i]
        for k in range(j+1, N-1):
            r = CA[k] - CA[j]
            s = CA[-1] - CA[k]
            mindiff = min(mindiff, max([p, q, r, s]) - min([p, q, r, s]))
print(mindiff)

Submission status: Time Limit Exceeded

Solution code:
def min_diff(x, base=0):
    n = len(x)
    ok = - 1  # x[ok] - base < x[n - 1] - x[ok]
    ng = n - 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if x[mid] - base < x[n - 1] - x[mid]:
            ok = mid
        else:
            ng = mid
    d_ok = abs((x[ok] - base) - (x[n - 1] - x[ok]))
    d_ng = abs((x[ng] - base) - (x[n - 1] - x[ng]))
    if d_ok < d_ng:
        return (x[ok] - base), (x[n - 1] - x[ok])
    else:
        return (x[ng] - base), (x[n - 1] - x[ng])


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    X = [0 for _ in range(N)]  # cum sum
    X[0] = A[0]
    for i in range(1, N):
        X[i] = X[i - 1] + A[i]
    # split to 2 parts (X_0, ..., X_(i-1)), (X_i, ..., X_(N-1))
    min_d = 10**10
    for i in range(2, N - 1):
        p, q = min_diff(X[:i])
        r, s = min_diff(X[i:], base=X[i - 1])
        d = max([p, q, r, s]) - min([p, q, r, s])
        min_d = min([min_d, d])
    print(min_d)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
    F[b] = F[b - 1] + A[b]


res = [0]*4
data = [10 ** 18] * 2
ex = [0]*4
ans = 10 ** 18
s = 0
t = 2
for i in range(1, n - 2):
    for j in range(s, i):
        res[0] = F[j]
        res[1] = F[i] - F[j]
        if data[0] > abs(res[1] - res[0]) or j == s:
            s = j
            ex[0] = res[0]
            ex[1] = res[1]
            data[0] = abs(res[1] - res[0])
    for k in range(t, n):
        res[2] = F[k] - F[i]
        res[3] = F[n - 1] - F[k]
        if data[1] > abs(res[3] - res[2]) or k == t:
            t = k
            ex[2] = res[2]
            ex[3] = res[3]
            data[1] = abs(res[3] - res[2])
    ans = min(ans, max(ex) - min(ex))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
    F[b] = F[b - 1] + A[b]



res = [0]*4
data = [10 ** 18] * 2
ex = [0]*4
ans = 10 ** 18
for i in range(1, n - 1):
    for j in range(0, i):
        res[0] = F[j]
        res[1] = F[i] - F[j]
        if data[0] > abs(res[1] - res[0]) or j == 0:
            ex[0] = res[0]
            ex[1] = res[1]
            data[0] = abs(res[1] - res[0])
    for k in range(i + 1, n):
        res[2] = F[k] - F[i]
        res[3] = F[n - 1] - F[k]
        if data[1] > abs(res[3] - res[2]) or k == i + 1:
            ex[2] = res[2]
            ex[3] = res[3]
            data[1] = abs(res[3] - res[2])
    ans = min(ans, max(ex) - min(ex))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
    F[b] = F[b - 1] + A[b]
res = [0]*4
ans = 10**18
data = res[:]
s = 0
t = 2
for i in range(1, n - 1):
    for j in range(s, i):
        res[0] = F[j]
        res[1] = F[i] - F[j]
        for k in range(t, n-1):
            res[2] = F[k] - F[i]
            res[3] = F[n - 1] - F[k]
            if ans > max(res) - min(res):
                s = j
                t = k
                data = res[:]
                ans = min(ans, max(res) - min(res))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
    F[b] = F[b - 1] + A[b]
res = [0]*4
ans = 10**18
for i in range(1, n - 1):
    for j in range(0, i):
        res[0] = F[j]
        res[1] = F[i] - F[j]
        for k in range(i + 1, n):
            res[2] = F[k] - F[i]
            res[3] = F[n - 1] - F[k]
            ans = min(ans, max(res) - min(res))
            if res[2] > res[3]:
                break
        if res[0] > res[1]:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
    F[b] = F[b - 1] + A[b]
res = [0]*4
ans = 10**18
for i in range(1, n - 1):
    for j in range(0, i):
        res[0] = F[j]
        res[1] = F[i] - F[j]
        for k in range(i + 1, n):
            res[2] = F[k] - F[i]
            res[3] = F[n - 1] - F[k]
            ans = min(ans, max(res) - min(res))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 15
from itertools import accumulate

def equal_l(cumsum,i):
    f = lambda j:abs(cumsum[i + 1] - 2*cumsum[j])
    l = 1
    r = i + 1
    while r - l > 1:
        mid = (l + r)//2
        if f(mid) - f(mid - 1) >= 0:
            r = mid
        else:
            l = mid
    #print('equeal_l:{0},{1}'.format(l,r))
    return cumsum[i + 1] - cumsum[l],cumsum[l]

def equal_r(cumsum,i,N):
    f = lambda j:abs(cumsum[-1] - cumsum[i + 1] - 2*(cumsum[j] - cumsum[i + 1]))
    l = i + 2
    r = N
    while r - l > 1:
        mid = (l + r)//2
        if f(mid) -  f(mid - 1) >= 0:
            r = mid
        else:
            l = mid
    #print('equeal_r:{0},{1}'.format(l,r))
    return  cumsum[-1] - cumsum[l],cumsum[l] - cumsum[i + 1]

def main():
    N = int(input())
    A = list(map(int,input().split()))
    cumsum = list(accumulate([0] + A))
    ans = INF
    for i in range(1,N - 2):
        a,b = equal_l(cumsum,i)
        c,d = equal_r(cumsum,i,N)
        ret = max(a,b,c,d) - min(a,b,c,d)
        ans = min(ans,ret)
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from itertools import product
import sys
try:
    from typing import List
except ImportError:
    pass


def bsearch1(i: int, a: "List[int]"):
    lb = 0
    rb = len(a) + 1
    while lb + 1 < rb:
        m = (lb + rb) // 2
        if a[m] > i:
            rb = m
        else:
            lb = m
    return lb


def bsearch2(i: int, a: "List[int]"):
    lb = 0
    rb = len(a) + 1
    while lb + 1 < rb:
        m = (lb + rb) // 2
        if a[m] > i:
            lb = m
        else:
            rb = m
    return lb


def solve(N: int, A: "List[int]"):
    cumleft = [0] * (N + 1)
    for i in range(N):
        cumleft[i + 1] = cumleft[i] + A[i]

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

    mleft = [bsearch1(cumi // 2, cumleft) for cumi in cumleft]
    mright = [bsearch2(cumi // 2, cumright) for cumi in cumright]
    ans = cumright[0]
    for i in range(2, N + 1 - 2):
        j1s = {mleft[i] - 1, mleft[i], mleft[i] + 1} - {0, i}
        j2s = {mright[i] - 1, mright[i], mright[i] + 1} - {i, N}
        for j1, j2 in product(j1s, j2s):
            p = cumleft[j1]
            q = cumleft[i] - cumleft[j1]
            r = cumleft[j2] - cumleft[i]
            s = cumright[j2]
            ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
    print(ans)


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:
import bisect
n=int(input())
A=list(map(int,input().split()))
S=[A[0]]
for i in range(n-1):
  S.append(S[-1]+A[i+1])
ans=10**15
for i in range(2,n-1):
  A1=A[0:i]
  A2=A[i:n]
  if len(A1)==2:
    M1=max(A1)
    m1=min(A1)
  else:
    x=bisect.bisect_left(S,S[i-1]//2,lo=0,hi=i+1)
    M11=max(S[x-1],S[i-1]-S[x-1])
    m11=min(S[x-1],S[i-1]-S[x-1])
    M12=max(S[x],S[i-1]-S[x])
    m12=min(S[x],S[i-1]-S[x])
    M1=min(M11,M12)
    m1=max(m11,m12)
  if len(A2)==2:
    M2=max(A2)
    m2=min(A2)
  else:
    x=bisect.bisect_left(S,S[i-1]+(S[-1]-S[i-1])//2,lo=0,hi=len(S))
    M21=max(S[x-1]-S[i-1],S[-1]-S[x-1])
    m21=min(S[x-1]-S[i-1],S[-1]-S[x-1])
    M22=max(S[x]-S[i-1],S[-1]-S[x])
    m22=min(S[x]-S[i-1],S[-1]-S[x])
    M2=min(M21,M22)
    m2=max(m21,m22)
  a=max(M1,M2)-min(m1,m2)
  if a<ans:
    ans=a
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(n-1):
  S.append(S[-1]+A[i+1])
ans=10**15
for i in range(2,n-1):
  A1=A[0:i]
  A2=A[i:n]
  if len(A1)==2:
    M1=max(A1)
    m1=min(A1)
  else:
    x=bisect.bisect_left(S,S[i-1]//2,lo=0,hi=i+1)
    M11=max(S[x-1],S[i-1]-S[x-1])
    m11=min(S[x-1],S[i-1]-S[x-1])
    M12=max(S[x],S[i-1]-S[x])
    m12=min(S[x],S[i-1]-S[x])
    M1=min(M11,M12)
    m1=max(m11,m12)
  S2=[A[i]]
  for i in range(i+1,n):
    S2.append(S2[-1]+A[i])
  if len(A2)==2:
    M2=max(A2)
    m2=min(A2)
  else:
    x=bisect.bisect_left(S2,S2[-1]//2,lo=0,hi=len(S2))
    M21=max(S2[x-1],S2[-1]-S2[x-1])
    m21=min(S2[x-1],S2[-1]-S2[x-1])
    M22=max(S2[x],S2[-1]-S2[x])
    m22=min(S2[x],S2[-1]-S2[x])
    M2=min(M21,M22)
    m2=max(m21,m22)
  a=max(M1,M2)-min(m1,m2)
  if a<ans:
    ans=a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 2つの部分列に分ける
def eqcut(start, end):
    target = (cumA[start - 1] + cumA[end]) / 2  # start = 0のときcumA[-1] = 0

    ok = start
    ng = end + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if cumA[mid] <= target:
            ok = mid
        else:
            ng = mid
    # okかok+1
    if ok == end:
        return ok
    else:
        diff1 = abs( (cumA[end] - cumA[ok]) - (cumA[ok] - cumA[start - 1]))
        diff2 = abs( (cumA[end] - cumA[ok + 1]) - (cumA[ok + 1] - cumA[start - 1]))
        if diff1 <= diff2:
            return ok
        else:
            return ok + 1
            

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

cumA = [A[0]] + [0] * N  # 累積和  cumA[-1] = 0となるように最後にダミー
for i in range(1, N):
    cumA[i] = cumA[i - 1] + A[i]

S = [0, 0, 0, 0]
B = [0, 0]
ans = cumA[N - 1]
# 3本の境界線のうち中央を探す
for i in range(1, N - 2):
    B[0] = eqcut(0, i)  # A[0], ..., A[i]を要素の総和が最小となる2つの部分列に分ける
    S[0] = cumA[B[0]]
    S[1] = cumA[i] - cumA[B[0]]

    B[1] = eqcut(i + 1, N - 1)
    S[2] = cumA[B[1]] - cumA[i]
    S[3] = cumA[N - 1] - cumA[B[1]]

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

print(ans)

Submission status: Time Limit Exceeded

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

def bs_left(mid,mp):
  sum2=abs(2*slist[mid]-slist[mp])
  if mid==0:
    sum1=sum2
  else:
    sum1=abs(2*slist[mid-1]-slist[mp])
  if mid==mp:
    sum3=sum2
  else:
    sum3=abs(2*slist[mid+1]-slist[mp])

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    

def bs_right(mid,mp):
  sum2=abs(2*(slist[mid]-slist[mp])-(slist[-1]-slist[mp]))
  if mid==0:
    sum1=sum2
  else:
    sum1=abs(2*(slist[mid-1]-slist[mp])-(slist[-1]-slist[mp]))
  if mid==mp:
    sum3=sum2
  else:
    sum3=abs(2*(slist[mid+1]-slist[mp])-(slist[-1]-slist[mp]))

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    
  
slist=[]
asum=0
for a in alist:
  asum+=a
  slist.append(asum)
#print(alist)
#print(slist)

dic_lp,dic_rp={},{}
for mp in range(1,N-2):  
  #lp
  l,r=0,mp
  while(l<=r):
    mid=(l+r)//2
    ret=bs_left(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_lp[mp]=mid
      #print(mp,mid)
      break
  
  #rp
  l,r=mp+1,N-2
  while(l<=r):
    mid=(l+r)//2
    ret=bs_right(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_rp[mp]=mid
      #print(mp,mid)
      break
    
min_diff=10**9
for mp in range(1,N-2):
  lp=dic_lp[mp]
  rp=dic_rp[mp]
  
  sum1=slist[lp]
  sum2=slist[mp]-slist[lp]
  sum3=slist[rp]-slist[mp]
  sum4=slist[-1]-slist[rp]
  #print(sum1,sum2,sum3,sum4)
  
  sum_list=[sum1,sum2,sum3,sum4]
  sum_list.sort()
  diff=sum_list[-1]-sum_list[0]
  #print(lp,mp,rp,diff)
  if diff<min_diff:
    min_diff=diff    
  
print(min_diff)

Submission status: Time Limit Exceeded

Solution code:
#dame datta
def main():
    N = int(input())
    A = list(map(int, input().split()))
    Al = [A[0]]
    r = (10**9)*(2*(10**5))
    for i in A[1:]:
        Al.append(Al[-1] + i)
    for t in range(2, N-1):
        t1 = -1
        m = (10**9)*(2*(10**5))
        for i in range(1,t):
            ii = abs(Al[t-1] - Al[i-1] - Al[i-1])
            if m > ii:
                t1 = i
                m = ii
        t2 = -1
        m = (10**9)*(2*(10**5))
        for i in range(t+1, N):
            ii = abs(Al[-1] - Al[i-1] - Al[i-1] + Al[t-1])
            if m > ii:
                t2 = i
                m = ii
        x = Al[-1] - Al[t2-1]
        y = Al[t2-1] - Al[t-1]
        z = Al[t-1] - Al[t1-1]
        w = Al[t1-1]
        r = min(max(x,y,z,w) - min(x,y,z,w), r)
    return r
print(main())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, *A = map(int, open(0).read().split())
B = np.cumsum(A)
j = 1
a = A[0]
b = A[1]
c = A[2]
d = B[-1]-B[2]
j = 0
h = 2
while h<N:
  if abs(d-c)>abs(d-c-2*A[h+1]):
    h += 1
    c += A[h]
    d -= A[h]
    continue
  break
x = max(a,b,c,d)
y = min(a,b,c,d)
ans = x-y
for i in range(2,N-2):
  b += A[i]
  c -= A[i]
  while j<i:
    if abs(b-a)>abs(b-a-2*A[j+1]):
      j += 1
      a += A[j]
      b -= A[j]
      continue
    break
  while h<N:
    if abs(d-c)>abs(d-c-2*A[h+1]):
      h += 1
      c += A[h]
      d -= A[h]
      continue
    break
  x = max(a,b,c,d)
  y = min(a,b,c,d)
  ans = min(ans,x-y)
print(ans)

Submission status: Time Limit Exceeded

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

A2 = [0] * (N + 1)

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


def find(_l, _r):
    l, r = _l, _r
    lv, rv = A2[l - 1], A2[r]
    while l < r - 1:
        m = (r + l) // 2
        a = A2[m] - lv
        if a <= (rv - lv) / 2:
            l = m
        else:
            r = m
    if l < _r:
        if abs((A2[l] - lv) - (rv - A2[l])) > abs((A2[l + 1] - lv) - (rv - A2[l + 1])):
            return A2[l + 1] - lv, rv - A2[l + 1]
    return A2[l] - lv, rv - A2[l]


ans = 1e10
for i in range(2, N - 1):
    p, q = find(1, i)
    r, s = find(i + 1, N)
    # print(p, q, r, s)
    ans = min(ans, abs(max(p, q, r, s) - min(p, q, r, s)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
cs = [0] * N
cs[0] = a[0]
for i in range(N - 1): cs[i + 1] = cs[i] + a[i + 1]
res = float("inf")
for m in range(1, N - 1):
  l = bl(cs[: m], cs[m] // 2)
  r = bl(cs[m: ], cs[m] + (cs[-1] - cs[m]) // 2) + m
  l -= l == m
  r += r == m
  nl = l + 0
  nr = r + 0
  for i in range(3):
    if i == 1: continue
    if 0 <= l + i - 1 < m:
      if abs(cs[m] - 2 * cs[l + i - 1]) < abs(cs[m] - 2 * cs[l]):
        nl = l + i - 1
    if m < r + i - 1 < N:
      if abs(cs[-1] - 2 * cs[r + i - 1] + cs[m]) < abs(cs[-1] - 2 * cs[r] + cs[m]):
        nr = r + i - 1
  l = nl
  r = nr
  res = min(res, max(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]) - min(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]))
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
cs = [0] * N
cs[0] = a[0]
for i in range(N - 1): cs[i + 1] = cs[i] + a[i + 1]
res = float("inf")
for m in range(1, N - 1):
  l = bl(cs[: m], cs[m] // 2)
  r = bl(cs[m: ], cs[m] + (cs[-1] - cs[m]) // 2) + m
  l -= l == m
  r += r == m
  nl = l + 0
  nr = r + 0
  for i in range(3):
    if 0 <= l + i - 1 < m:
      if abs(cs[m] - 2 * cs[l + i - 1]) < abs(cs[m] - 2 * cs[l]):
        nl = l + i - 1
    if m < r + i - 1 < N:
      if abs(cs[-1] - 2 * cs[r + i - 1] + cs[m]) < abs(cs[-1] - 2 * cs[r] + cs[m]):
        nr = r + i - 1
  l = nl
  r = nr
  res = min(res, max(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]) - min(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]))
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
cs = [0] * N
cs[0] = a[0]
for i in range(N - 1): cs[i + 1] = cs[i] + a[i + 1]
#print(cs)
def solve(m):
  l = bl(cs[: m], cs[m] // 2)
  r = bl(cs[m: ], cs[m] + (cs[-1] - cs[m]) // 2) + m
  l -= l == m
  r += r == m
  nl = l + 0
  nr = r + 0
  for i in range(3):
    if 0 <= l + i - 1 < m:
      if abs(cs[m] - 2 * cs[l + i - 1]) < abs(cs[m] - 2 * cs[l]):
        nl = l + i - 1
    if m < r + i - 1 < N:
      if abs(cs[-1] - 2 * cs[r + i - 1] + cs[m]) < abs(cs[-1] - 2 * cs[r] + cs[m]):
        nr = r + i - 1
  l = nl
  r = nr
  return max(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]) - min(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r])
res = float("inf")
for i in range(1, N - 1):
  res = min(res, solve(i))
  #print(solve(i))
print(res)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

n = int(input())
A = list(map(int,input().split()))
AA = []
res = 0
for a in A:
	res += a
	AA.append(res)

ans = float('inf')
for idx_mid in range(2,n-1):
	# print(idx_mid)
	idx_left = bisect_left(AA,AA[idx_mid-1]//2,1)
	# print(idx_left)
	idx_right = bisect_left(AA,AA[idx_mid-1]+((AA[-1]-AA[idx_mid-1])//2),idx_mid+1,n-1)
	# print(idx_right)

	a = sum(A[:idx_left])
	# print(A[:idx_left])
	b = sum(A[idx_left:idx_mid])
	if a < b-A[idx_left] and len(A[idx_left:idx_mid]) >= 2:
		a += A[idx_left]
		b -= A[idx_left]
		idx_left -= 1
	# print(A[idx_left:idx_mid])
	c = sum(A[idx_mid:idx_right])
	if b < c-A[idx_mid] and len(A[idx_mid:idx_right]) >= 2:
		b += A[idx_mid]
		c -= A[idx_mid]
		idx_mid -= 1
	# print(A[idx_mid:idx_right])
	d = sum(A[idx_right:])
	if c < d-A[idx_right] and len(A[idx_right:]) >= 2:
		c += A[idx_right]
		d -= A[idx_right]
		idx_right -= 1
	# print(A[idx_right:])

	ans = min(ans,max(a,b,c,d)-min(a,b,c,d))
	# print('ans=',ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

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

s = sum(A)
for i in range(1, N) :
    A[i] += A[i-1]


def check(d) :
    ifr = bisect_left(A, (s - 3 * d) // 4)
    ito = bisect_left(A, (s + 3 * d) // 4)
    for i in range(ifr, min(N, ito + 1)) :
        jfr = bisect_left(A, A[i] + (s - A[i] - 2 * d) // 3)
        jto = bisect_left(A, A[i] + (s - A[i] + 2 * d) // 3)
        for j in range(max(i + 1, jfr), min(N, jto + 1)) :
            kfr = bisect_left(A, A[j] + (s - A[j] - d) // 2)
            kto = bisect_left(A, A[j] + (s - A[j] + d) // 2)
            for k in range(max(j + 1, kfr), min(N - 1, kto + 1)) :
                cut = [A[i], A[j] - A[i], A[k] - A[j], s - A[k]]
                if max(cut) - min(cut) <= d :
                    return True
    return False

ng, ok = 0, s
while ok - ng > 1 :
    mid = (ng + ok) // 2
    
    if check(mid) :
        ok = mid
    else :
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=[sum(a[:i])+a[i] for i in range(len(a))]
j=0
k=2
ans=10**9

for i in range(1,n-1):
    while abs(a[j]*2-a[i])>abs(a[j+1]*2-a[i]):
        j+=1
    while abs(a[k]*2-a[i]-a[n-1])>abs(a[k+1]*2-a[i]-a[n-1]):
        k+=1
    t=[a[j],a[i]-a[j],a[k]-a[i],a[n-1]-a[k]]
    ans=min(ans,max(t)-min(t))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=list(map(int,input().split()))
ans=float('inf')
rui=[0]*(n+1)
for i in range(n):
    rui[i+1]=rui[i]+a[i]
for i in range(2,n-1):
    p,q,r,s=0,0,0,0
    # left=sum(a[:i])
    # right=sum(a[i:])
    # print()
    # print(left)
    # print(right)
    tmppq=[float('inf'),0,0]
    tmprs=[float('inf'),0,0]
    for j in range(i-1):
        p=rui[j+1]
        q=rui[i]-p
        if tmppq[0]>abs(p-q):
            tmppq=[abs(p-q),p,q]
    for j in range(i,n-1):
        r=rui[j+1]-rui[i]
        s=rui[n]-rui[j+1]
        # print(r)
        # print(s)
        if tmprs[0]>abs(r-s):
            tmprs=[abs(r-s),r,s]
    ans=min(ans,max(tmppq[1],tmppq[2],tmprs[1],tmprs[2])-min(tmppq[1],tmppq[2],tmprs[1],tmprs[2]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=list(map(int,input().split()))
ans=float('inf')

for i in range(2,n-1):
    p,q,r,s=0,0,0,0
    left=sum(a[:i])
    right=sum(a[i:])
    # print()
    # print(left)
    # print(right)
    tmppq=[float('inf'),0,0]
    tmprs=[float('inf'),0,0]
    for j in range(i-1):
        p+=a[j]
        q=left-p
        if tmppq[0]>abs(p-q):
            tmppq=[abs(p-q),p,q]
    for j in range(i,n-1):
        r+=a[j]
        s=right-r
        if tmprs[0]>abs(r-s):
            tmprs=[abs(r-s),r,s]
    ans=min(ans,max(tmppq[1],tmppq[2],tmprs[1],tmprs[2])-min(tmppq[1],tmppq[2],tmprs[1],tmprs[2]))
print(ans)

Submission status: Time Limit Exceeded

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

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

left_min = right_min = ans = float('INF')
left_max = right_max = 0

for r in range(2, N - 1):
    # 左のしゃくとり
    P, Q = P2, Q2 = -1, -1
    p = 0
    q = 1
    while True:
        P2, Q2 = P, Q
        P = SUM[q - 1]
        Q = SUM[r - 1] - SUM[q - 1]
        if P < Q and q < r:
            q += 1
        else:
            break
    left_min, left_max = min(P, Q), max(P, Q)
    if P2 != -1:
        if abs(Q - P) > abs(Q2 - P2):
            left_min, left_max = min(P2, Q2), max(P2, Q2)

    # 右のしゃくとり
    R, S = R2, S2 = -1, -1
    s = r + 1
    while True:
        R2, S2 = R, S
        R = SUM[s - 1] - SUM[r - 1]
        S = SUM[N - 1] - SUM[s - 1]
        if R < S and s < N - 1:
            s += 1
        else:
            break
    right_min, right_max = min(R, S), max(R, S)
    if R2 != -1:
        if abs(R - S) > abs(R2 - S2):
            right_min, right_max = min(R2, S2), max(R2, S2)

    # print(p, q, r, s)
    # print(P, Q, R, S)
    # print(P2, Q2, R2, S2)
    # print("----------")

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from statistics import mean

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

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


ans = float('inf')

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

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

for x in range(n):
    for y in range(x + 1, n):
        for z in range(y + 1, n):
            b = s[x] - s[0]
            c = s[y] - s[x]
            d = s[z] - s[y]
            e = s[n] - s[z]
            diff = max(b, c, d, e) - min(b, c, d, e)
            ans = min(diff, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from statistics import mean

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

def separate_equally(nums):
    left = 0
    right = sum(nums)
    pre_diff = abs(left - right)
    for num in nums:
        left += num
        right -= num
        diff = abs(left - right)
        if diff < pre_diff:
           pre_diff = diff
        else:
            return [left - num, right + num]

min_score = float('inf')
for i in range(2, N - 1):
    left_A = A[:i]
    right_A = A[i:]
    sums = separate_equally(left_A)
    sums.extend(separate_equally(right_A))
    score = max(sums) - min(sums)
    if score < min_score:
        min_score = score
    
print(min_score)

Submission status: Time Limit Exceeded

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

min_score = float('inf')
for i in range(1, N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            l = [sum(A[:i]), sum(A[i:j]), sum(A[j:k]), sum(A[k:])]
            score = max(l) - min(l)
            if score < min_score:
                min_score = score

print(min_score)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

# print (calc(A, 0))

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

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