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:
n = int(input())
a = list(map(int, input().split()))

minmin=1000000000
for i1 in range(1,n-2):
    s1 = sum(a[0:i1])
    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+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)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate, product

    def binary_search(a, x, lo, hi):
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        return lo

    n = int(input())
    *a, = map(int, input().split())
    acc = (0,) + tuple(accumulate(a))

    # [0,i), [i,j), [j,k), [k, n)

    ret = acc[-1]
    for j in range(2, n - 1):
        left = acc[j]
        right = acc[-1] - left

        i = binary_search(acc, left // 2, 2, j + 2)
        k = binary_search(acc, left + (right // 2), j + 2, n + 1)

        li = i - 1, i
        rk = k - 1, k

        for i, k in product(li, rk):
            if i <= 0 or k <= j:
                continue
            pqrs = acc[i], left - acc[i], acc[k] - left, acc[-1] - acc[k]
            ret = min(
                ret,
                max(pqrs) - min(pqrs)
            )

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate, product

    def binary_search(a, x, lo, hi):
        while abs(hi - lo) > 0:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        return hi

    n = int(input())
    *a, = map(int, input().split())
    acc = (0,) + tuple(accumulate(a))

    # [0,i), [i,j), [j,k), [k, n)

    ret = acc[-1]
    for j in range(2, n - 1):
        left = acc[j]
        right = acc[-1] - left

        i = binary_search(acc, left // 2, 2, j + 2)
        k = binary_search(acc, left + (right // 2), j + 2, n + 1)

        li = i - 1, i
        rk = k - 1, k

        for i, k in product(li, rk):
            if i <= 0 or k <= j:
                continue
            pqrs = acc[i], left - acc[i], acc[k] - left, acc[-1] - acc[k]
            ret = min(
                ret,
                max(pqrs) - min(pqrs)
            )

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

global csA
MAXINT = 2 ** 63 - 1

def getsumanddiff(i, j, k):
    tmp = csA[j+1]
    p = tmp - csA[i]
    q = csA[k+1] - tmp
    return p, q, abs(p - q)

N = int(input())
A = np.array(list(map(int, input().split())))
# N = 1000000
# A = np.arange((N))
csA = np.cumsum(A)

# init
mid0 = 0
mid2 = 2

p, q, r, s = [0]*4
diff = MAXINT

csAN = csA[N-1]
for mid1 in range(1, N - 2):
    diff0 = MAXINT
    diff2 = MAXINT
    csAmid1 = csA[mid1]

    # mid0 search
    for i in range(mid0, mid1):
        # tmpp, tmpq, tmpdiff0 = getsumanddiff(0, i, mid1)
        tmpp = csA[i]
        tmpq = csAmid1 - tmpp
        tmpdiff0 = abs(tmpp - tmpq)
        if diff0 > tmpdiff0:
            mid0 = i
            diff0 = tmpdiff0
            p = tmpp
            q = tmpq
        else:
            break

    # mid2 search
    start = mid1 if mid2 < mid1 else mid2
    for i in range(start, N - 1):
        # tmpr, tmps, tmpdiff2 = getsumanddiff(mid1+1, i, N - 1)
        csAi = csA[i]
        tmpr = csAi - csAmid1
        tmps = csAN - csAi
        tmpdiff2 = abs(tmpr - tmps)
        if diff2 > tmpdiff2:
            mid2 = i
            diff2 = tmpdiff2
            r = tmpr
            s = tmps
        else:
            break

    tmpdiff = max(p, q, r, s) - min(p, q, r, s)
    if diff > tmpdiff:
        diff = tmpdiff

print(diff)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

global csA
MAXINT = 2 ** 63 - 1

def getsumanddiff(i, j, k):
    tmp = csA[j+1]
    p = tmp - csA[i]
    q = csA[k+1] - tmp
    return p, q, abs(p - q)

N = int(input())
csA = np.zeros((N+1), dtype=int)
for idx, i in enumerate(list(map(int, input().split()))):
    csA[idx+1] = csA[idx] + int(i)

# init
mid0 = 0
mid2 = 2

p, q, r, s = [0]*4
diff = MAXINT

csAN = csA[N]
for mid1 in range(1, N - 2):
    diff0 = MAXINT
    diff2 = MAXINT
    csAmid1 = csA[mid1+1]

    # mid0 search
    for i in range(mid0, mid1):
        # tmpp, tmpq, tmpdiff0 = getsumanddiff(0, i, mid1)
        tmpp = csA[i+1]
        tmpq = csAmid1 - tmpp
        tmpdiff0 = abs(tmpp - tmpq)
        if diff0 > tmpdiff0:
            mid0 = i
            diff0 = tmpdiff0
            p = tmpp
            q = tmpq
        else:
            break

    # mid2 search
    start = mid1 if mid2 < mid1 else mid2
    for i in range(start, N - 1):
        # tmpr, tmps, tmpdiff2 = getsumanddiff(mid1+1, i, N - 1)
        csAi = csA[i+1]
        tmpr = csAi - csAmid1
        tmps = csAN - csAi
        tmpdiff2 = abs(tmpr - tmps)
        if diff2 > tmpdiff2:
            mid2 = i
            diff2 = tmpdiff2
            r = tmpr
            s = tmps
        else:
            break

    tmpdiff = max(p, q, r, s) - min(p, q, r, s)
    if diff > tmpdiff:
        diff = tmpdiff

print(diff)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

global csA
MAXINT = 2 ** 63 - 1

def getsumanddiff(i, j, k):
    p = csA[j+1] - csA[i]
    q = csA[k+1] - csA[j+1]
    return p, q, abs(p - q)

def getfinaldiff(p, q, r, s):
    return max(p, q, r, s) - min(p, q, r, s)

# N = int(input())
# A = np.array(list(map(int, input().split())))
N = 100000000
A = np.arange(N, dtype=int)
csA = np.concatenate([[0], np.cumsum(A)]) # Cumulative sum

# init
mid0 = 0
mid2 = 2

p, q, r, s = [0]*4
diff = MAXINT

for mid1 in range(1, N - 2):
    diff0 = MAXINT
    diff2 = MAXINT

    # mid0 search
    for i in range(mid0, mid1):
        tmpp, tmpq, tmpdiff0 = getsumanddiff(0, i, mid1)
        if diff0 > tmpdiff0:
            mid0 = i
            diff0 = tmpdiff0
            p = tmpp
            q = tmpq
        else:
            break

    # mid2 search
    start = mid1 if mid2 < mid1 else mid2
    for i in range(start, N - 1):
        if mid1 >= i:
            continue
        tmpr, tmps, tmpdiff2 = getsumanddiff(mid1+1, i, N - 1)
        if diff2 > tmpdiff2:
            mid2 = i
            diff2 = tmpdiff2
            r = tmpr
            s = tmps
        else:
            break

    tmpdiff = getfinaldiff(p, q, r, s)
    if diff > tmpdiff:
        diff = tmpdiff

print(diff)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

global csA

def getsumanddiff(i, j, k):
    p = csA[j+1] - csA[i]
    q = csA[k+1] - csA[j+1]
    return p, q, abs(p - q)

def getfinaldiff(p, q, r, s):
    return max(p, q, r, s) - min(p, q, r, s)

N = int(input())
A = np.array(list(map(int, input().split())))
csA = np.concatenate([[0], np.cumsum(A)]) # Cumulative sum

# init
mid0 = 0
mid2 = 2

p, q, r, s = [0]*4
diff = 2 ** 63

for mid1 in range(1, N - 2):
    diff0 = 2 ** 63
    diff2 = 2 ** 63

    # mid0 search
    for i in range(mid0, mid1):
        tmpp, tmpq, tmpdiff0 = getsumanddiff(0, i, mid1)
        if diff0 > tmpdiff0:
            mid0 = i
            diff0 = tmpdiff0
            p = tmpp
            q = tmpq
        else:
            break

    # mid2 search
    for i in range(mid2, N - 1):
        if mid1 >= i:
            continue
        tmpr, tmps, tmpdiff2 = getsumanddiff(mid1+1, i, N - 1)
        if diff2 > tmpdiff2:
            mid2 = i
            diff2 = tmpdiff2
            r = tmpr
            s = tmps
        else:
            break

    tmpdiff = getfinaldiff(p, q, r, s)
    if diff > tmpdiff:
        diff = tmpdiff

print(diff)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

readInt = lambda : [int(i) for i in input().split()];
n = readInt()[0]
A = readInt()

B = list(itertools.accumulate(A))

cand = []
for i in range(2, len(A)-1):
  B0 = B[0:i]
  B1 = [x - B[i-1] for x in B[i:len(A)]]
  s = B0[-1] // 2
  for j in range(1, len(B0)):
    if (B0[j] > s):
      c0 = abs(2 * B0[j-1] - B0[-1])
      c1 = abs(2 * B0[j] - B0[-1])
      j0 = j-1 if c0 < c1 else j
      break

  s = B1[-1] // 2
  for j in range(1, len(B1)):
    if (B1[j] > s):
      c0 = abs(2 * B1[j-1] - B1[-1])
      c1 = abs(2 * B1[j] - B1[-1])
      j1 = j-1 if c0 < c1 else j
      break

  c = [B0[j0], B0[-1] - B0[j0], B1[j1], B1[-1] - B1[j1]]
  cand.append(max(c) - min(c))

ans = min(cand)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

readInt = lambda : [int(i) for i in input().split()];
n = readInt()[0]
A = readInt()

B = list(itertools.accumulate(A))

cand = []
for i in range(2, len(A)-1):
  B0 = B[0:i]
  B1 = [x - B[i-1] for x in B[i:len(A)]]
  D0 = [abs(2 * x - B0[-1]) for x in B0]
  D1 = [abs(2 * x - B1[-1]) for x in B1]
  j0 = D0.index(min(D0))
  j1 = D1.index(min(D1))
  c = [B0[j0], B0[-1] - B0[j0], B1[j1], B1[-1] - B1[j1]]
  cand.append(max(c) - min(c))

ans = min(cand)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

def binsearch(a, start, end):
    low = start
    high = end

    mindiff = 2**63
    minpos = 0
    minleftsum = 0
    minrightsum = 0
    premid = -2
    mid = -1

    # print('--start--')
    while low <= high:
        premid = mid
        mid = (low + high) // 2
        leftsum = a[start:mid].sum()
        rightsum = a[mid:end].sum()
        diff = np.abs(leftsum - rightsum)
        if diff < mindiff:
            mindiff = diff
            minpos = mid
            minleftsum = leftsum
            minrightsum = rightsum

        # print(low, high, mid, leftsum, rightsum, diff, minpos)
        if leftsum < rightsum:
            low = mid + 1
        elif leftsum > rightsum:
            high = mid - 1
        else:
            return mid, leftsum, rightsum

    return minpos, minleftsum, minrightsum

def calcfinaldiff(p, q, r, s):
    return max((p, q, r, s)) - min((p, q, r, s))

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

mid0 = binsearch(A, 0, N)[0]
mid1, p, q = binsearch(A, 0, mid0)
mid2, r, s = binsearch(A, mid0, N)

diff = calcfinaldiff(p, q, r, s)

for mid in range(1, N - 1):
    mid1, p, q = binsearch(A, 0, mid)
    mid2, r, s = binsearch(A, mid, N)
    tmpdiff = calcfinaldiff(p, q, r, s)
    if diff > tmpdiff:
        diff = tmpdiff

print(diff)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
N = int(input())
A = list(map(int, input().split()))
S1 = [A[0]]*N
S2 = [A[-1]]*N
def cut(S):
    s = S[-1]/2
    i = bisect_left(S, s)
    if abs(S[i]-s) < abs(S[i-1]-s):
        return (S[i], S[-1]-S[i])
    else: return (S[i-1], S[-1]-S[i-1])
for i in range(1, N):
    S1[i] = S1[i-1]+A[i]
    S2[i] = S2[i-1]+A[N-i-1]
ans = S1[-1]
for i in range(2, N-1):
    P, Q = cut(S1[:i])
    R, S = cut(S2[:N-i])
    res = max(P, Q, R, S)-min(P, Q, R, S)
    ans = min(ans, res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect


def bs(a):
    x = (a[0] + a[-1]) // 2
    j = bisect.bisect_right(a, x)
    if x - a[j-1] < a[j] - x:
        j = j - 1
    return j


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

    s = [0] * (n + 1)
    s[0] = 0
    for i in range(n):
        s[i+1] = s[i] + a[i]

    p = [0] + [s[bs(s[:i+2])] for i in range(1, n)]
    r = [0] + [s[i + 1 + bs(s[i+1:])] for i in range(1, n-1)]

    ans = 10 ** 20
    for i in range(1, n-2):
        pp = p[i]
        qq = s[i+1] - p[i]
        rr = r[i] - s[i+1]
        ss = s[n] - r[i]
        ans = min(ans, max(pp, qq, rr, ss) - min(pp, qq, rr, ss))
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
N=int(input())
A=list(map(int,input().split()))
B=[A[0]]
for i in range(1,N):
    B.append(A[i]+B[i-1])
#print(B)

ans=10**20
for x in range(2,N-1):
    #print(x)
    Q=[]
    q1=B[bisect.bisect_left(B,B[x-1]/2)]
    q2=B[x-1]-q1
    q3=B[bisect.bisect_left(B,B[x-1]/2)-1]
    q4=B[x-1]-q3
    if abs(q1-q2)<abs(q3-q4):
        Q.append(q1)
        Q.append(q2)
    else:
        Q.append(q3)
        Q.append(q4)
    q5=B[bisect.bisect_left(B,(B[N-1]+B[x-1])/2)]-B[x-1]
    q6=B[N-1]-q5-B[x-1]
    q7=B[bisect.bisect_left(B,(B[N-1]+B[x-1])/2)-1]-B[x-1]
    q8=B[N-1]-q7-B[x-1]
    
    if abs(q5-q6)<abs(q7-q8):
        Q.append(q5)
        Q.append(q6)
    else:
        Q.append(q7)
        Q.append(q8)
    if (max(Q)-min(Q))<ans:
        ans=(max(Q)-min(Q))
    #print(Q)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
a = list(map(int,raw_input().split()))
b = []
ANS = []
x = 0
for i in range(N):
  x += a[i]
  b.append(x)
for j in range(1,N-1):
  A = b[j]
  bnew = list(map(lambda x: abs(2*x-A),b))
  c = bnew.index(min(bnew))
  B = b[N-1]-b[j]
  bnew2 = list(map(lambda x: abs(2*x-2*A-B),b))
  d = bnew2.index(min(bnew2))
  kire = [b[c],b[j]-b[c],b[d]-b[j],b[N-1]-b[d]]
  ans = max(kire)-min(kire)
  ANS.append(ans)
print min(ANS)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect

n = int(input())
a = list(map(int, input().split()))
b = [a[0]]
for i in range(1, n):
	b.append(b[-1] + a[i])
#print(b)

ans = float("inf")
for i in range(2, n - 1):
	former_cut = bisect(b[:i], b[i-1] / 2)
	if former_cut == 0 or b[former_cut-1] < b[i-1] - b[former_cut]:
		p, q = b[former_cut], b[i-1] - b[former_cut]
	else:
		p, q = b[former_cut-1], b[i-1] - b[former_cut-1]

	latter_cut = bisect(b[i:], (b[-1] + b[i-1]) / 2) + i
	#print(latter_cut)
	if b[latter_cut-1] - b[i-1] >= b[-1] - b[latter_cut]:
		r, s = b[latter_cut-1] - b[i-1], b[-1] - b[latter_cut-1]
	else:
		r, s = b[latter_cut] - b[i-1], b[-1] - b[latter_cut]
	#print(p, q, r, s)
	ans = min(ans, max(p, q, r, s) - min(p, q, r, s))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect

n = int(input())
a = list(map(int, input().split()))
b = [a[0]]
for i in range(1, n):
	b.append(b[-1] + a[i])
#print(b)

ans = float("inf")
for i in range(2, n - 1):
	former_cut = bisect(b[:i], b[i-1] / 2)
	if former_cut == 0 or b[former_cut-1] < b[i-1] - b[former_cut]:
		p, q = b[former_cut], b[i-1] - b[former_cut]
	else:
		p, q = b[former_cut-1], b[i-1] - b[former_cut-1]

	latter_cut = bisect(b, (b[-1] + b[i-1]) / 2)
	#print(latter_cut)
	if b[latter_cut-1] - b[i-1] >= b[-1] - b[latter_cut]:
		r, s = b[latter_cut-1] - b[i-1], b[-1] - b[latter_cut-1]
	else:
		r, s = b[latter_cut] - b[i-1], b[-1] - b[latter_cut]
	#print(p, q, r, s)
	ans = min(ans, max(p, q, r, s) - min(p, q, r, s))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

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


def search(s, e, val):
    s_org = s
    base = sum_A[s_org]
    while e - s > 1:
        p = (s+e) // 2
        if sum_A[p] - base < val:
            s = p
        elif sum_A[p] - base > val:
            e = p
        else:
            return p
    if abs(sum_A[s] - base - val) < abs(sum_A[e] - base - val):
        return s
    else:
        return e

ans = sum_A[N]
for i in range(N+1):
    sum_first_half = sum_A[i]
    sum_last_half = sum_A[N] - sum_A[i]
    a = search(0, i, sum_first_half/2)
    b = search(i, N, sum_last_half/2)
    P = sum_A[a]
    Q = sum_first_half - P
    R = sum_A[b] - sum_first_half
    S = sum_last_half - R
    l = [P,Q,R,S]
    ans = min(ans, max(l) - min(l))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

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


def search(s, e, val):
    s_org = s
    while e - s > 1:
        p = (s+e) // 2
        if sum_A[p] - sum_A[s_org] < val:
            s = p
        elif sum_A[p] - sum_A[s_org] > val:
            e = p
        else:
            return p
    if abs(sum_A[s] - sum_A[s_org] - val) < abs(sum_A[e] - sum_A[s_org] - val):
        return s
    else:
        return e

ans = sum_A[N]
for i in range(N+1):
    sum_first_half = sum_A[i]
    sum_last_half = sum_A[N] - sum_A[i]
    a = search(0, i, sum_first_half/2)
    b = search(i, N, sum_last_half/2)
    P = sum_A[a]
    Q = sum_A[i] - sum_A[a]
    R = sum_A[b] - sum_A[i]
    S = sum_A[N] - sum_A[b]
    l = [P,Q,R,S]
    ans = min(ans, max(l) - min(l))
print(ans)

Submission status: Time Limit Exceeded

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

result = []
for i in range(2, n-1):
    a1, a2 = list[0], list[i-1]
    i1, i2 = 1, i-1
    while i1 < i2:
        if a1 < a2:
            a1 += list[i1]
            i1 += 1
        else:
            a2 += list[i2 - 1]
            i2 -= 1
    b1, b2 = list[i], list[n-1]
    i1, i2 = i + 1, n - 1
    while i1 < i2:
        if b1 < b2:
            b1 += list[i1]
            i1 += 1
        else:
            b2 += list[i2 - 1]
            i2 -= 1
    result.append(max(a1,a2,b1,b2)-min(a1,a2,b1,b2))
print(min(result))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
a = np.array([int(item) for item in input().split()], dtype=int)

cum = np.cumsum(a)
total = np.sum(a)
def find(b, total):
    assert sum(b)==total
#     print("b: ", b)
    thre = total/2.0
    b = np.cumsum(b)
    out = np.argmin(np.abs(b-thre))
#     print("out:", out)
    return out
#     return np.min(np.where(b>thre)[0])

best = total
for i in range(1,N-2):
    left = cum[i]
    right = total - left
    ileft = find(a[:(i+1)], left)
    iright = find(a[(i+1):], right) + i + 1
    z1 = np.sum(a[:(ileft+1)])
    z2 = left - z1
    z3 = np.sum(a[(i+1):(iright+1)])
    z4 = np.sum(a[(iright+1):])  # right - z3
    M = max([z1,z2,z3,z4])
    m = min([z1,z2,z3,z4])
    best = min(best, M-m)
#     print([z1,z2,z3,z4])
print(best)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
A = list(map(int, input().split()))
accum = [0 for i in range(N + 1)]
for i in range(N):
    accum[i + 1] = accum[i] + A[i]
#accum[i + 1] = A[0] + A[1] + ... + A[i]
#sum(A[i:j]) = A[i] + A[i+1] + ... + A[j-1] = accum[j] - accum[i]
ans = float('inf')
for i in range(2, N - 1, 1): #2番目の区切りを A[i-1]とA[i]の間に入れる
    zenhan = accum[i] #(= sum(A[:i]))
    kouhan = accum[N] - accum[i]#(= sum(A[i:N]))
    index1l = bisect.bisect(accum, zenhan // 2, lo = 2, hi = i) - 1
    index1r = min(index1l + 1, i - 1)
    index3l = bisect.bisect(accum, zenhan + (kouhan // 2), lo = i + 2, hi = N) - 1
    index3r = min(index3l + 1, N - 1)
    for index1 in (index1l, index1r):
        for index3 in (index3l, index3r):
            B, C, D, E = accum[index1], accum[i] - accum[index1], accum[index3] - accum[i], accum[N] - accum[index3]
            M = max(B, C, D, E)
            m = min(B, C, D, E)
            ans = min(ans, M - m)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
A = list(map(int, input().split()))
accum = [0 for i in range(N + 1)]
for i in range(N):
    accum[i + 1] = accum[i] + A[i]
#accum[i + 1] = A[0] + A[1] + ... + A[i]
#sum(A[i:j]) = A[i] + A[i+1] + ... + A[j-1] = accum[j] - accum[i]
ans = float('inf')
for i in range(2, N - 1, 1): #2番目の区切りを A[i-1]とA[i]の間に入れる
    zenhan = accum[i] #(= sum(A[:i]))
    kouhan = accum[N] - accum[i]#(= sum(A[i:N]))
    index1l = bisect.bisect_left(accum, zenhan // 2, lo = 2, hi = i) - 1
    index1r = min(index1l + 1, i - 1)
    index3l = bisect.bisect_left(accum, zenhan + (kouhan // 2), lo = i + 2, hi = N) - 1
    index3r = min(index3l + 1, N - 1)
    for index1 in (index1l, index1r):
        for index3 in (index3l, index3r):
            B, C, D, E = accum[index1], accum[i] - accum[index1], accum[index3] - accum[i], accum[N] - accum[index3]
            M = max(B, C, D, E)
            m = min(B, C, D, E)
            ans = min(ans, M - m)
print(ans)

Submission status: Time Limit Exceeded

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


def bsearch(l, lsum, rsum):
    n = int(len(l)/2)
    if n == 0:
        return [max(rsum, lsum) , min(rsum, lsum) + l[0]]
    ll = l[:n]
    rl = l[n:]
    llsum = sum(ll)
    rrsum = sum(rl)
    lsum += llsum
    rsum += rrsum
    if lsum > rsum:
        return bsearch(ll, lsum-llsum, rsum)
    else:
        return bsearch(rl, lsum, rsum-rrsum)

for i in range(N-3):
    cs = bsearch(As[:i+2], 0, 0) + bsearch(As[i+2:], 0, 0)
    if i == 0:
        result = max(cs) - min(cs)
    else:
        if max(cs) - min(cs) < result:
            result = max(cs) - min(cs)
print(result)

Submission status: Time Limit Exceeded

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

import numpy as np


ans = float("inf")
if N == 4:
    ans = min(ans, (max(A) - min(A)))
else:
    for i in range(2, N - 2):
        left_cs = list(np.cumsum(A[:i]))
        right_cs = list(np.cumsum(A[i:]))
        for l, v in enumerate(left_cs):
            if v + left_cs[l + 1] >= left_cs[-1]:
                P = left_cs[l]
                Q = left_cs[-1] - P
                break
        for r, v in enumerate(right_cs):
            if v + right_cs[r + 1] >= right_cs[-1]:
                R = right_cs[r]
                S = right_cs[-1] - R
                break
        ans = min(ans, (max(P, Q, R, S) - min(P, Q, R, S)))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
a=i2()
c=[0 for i in range(n)]
b=sum(a)

for i in range(n):
 if i: c[i]+=c[i-1]
 c[i]+=a[i]
f=float("inf")
import bisect
e=[]
b=a[0]
d=c[n-1]-c[0]
for i in range(1,n-2):
 b+=a[i]
 d-=a[i]
 x=bisect.bisect_left(c[:i+1],b/2)
 
 if abs(c[i]-2*c[x])>abs(c[i]-2*c[x-1]) and x>0:
   e.append(c[i]-c[x-1])
   e.append(c[x-1])
 else:
   e.append(c[i]-c[x])
   e.append(c[x])
 y=bisect.bisect_left(c[i+1:],d/2+c[i])+i+1
 if abs(c[n-1]-c[y]-(c[y]-c[i]))>abs(c[n-1]-c[y-1]-(c[y-1]-c[i])) and y>0:
   e.append(c[n-1]-c[y-1])
   e.append(c[y-1]-c[i])
 else:
   e.append(c[n-1]-c[y])
   e.append(c[y]-c[i])

 f=min(f,max(e)-min(e))
 e=[]
print(f)

Submission status: Time Limit Exceeded

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

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

def half(i, j):
    if i + 2 == j:
        return i + 1
    l, r = i, j
    while l + 1 != r:
        md = (l + r) // 2
        if (get(i, md) < get(md, j)):
            l = md
        else:
            r = md
    a0 = abs(get(i, l) - get(l, j))
    a1 = abs(get(i, l + 1) - get(l + 1, j))
    if a0 < a1:
        md = l
    else:
        md = l + 1
    return md

def get(L, R):
    if L == R:
        return 0
    ret =  cumulative[R - 1]
    if L > 0:
        ret -= cumulative[L - 1]
    return ret

ans = pow(10, 9) * 2 * pow(10, 5)
for b in range(2, N - 1):
    l, m = get(0, b), get(b, N)
    l, m = max(l, m), min(l, m)
    if (l + 1)//2 - m > ans:
        continue
    a = half(0, b)
    c = half(b, N)
    B = get(0, a)
    C = get(a, b)
    D = get(b, c)
    E = get(c, N)
    x = max(B, C, D, E) - min(B, C, D, E)
    if x < ans:
        ans = x
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
for i in range(len(a)-1):
    a[i+1] += a[i]

ans = float('inf')
for i in range(1,n-2):
    #L
    c,d,e,f = 0,0,0,0
    diff = float('inf')
    for j in range(i):
        tmpc,tmpd = a[j],a[i]-a[j]
        if abs(tmpc-tmpd) < diff:
            diff = abs(tmpc-tmpd)
            c,d = tmpc,tmpd
    #R
    diff = float('inf')
    for j in range(i+1,n-1):
        tmpe,tmpf = a[j]-a[i],a[n-1]-a[j]
        if abs(tmpe-tmpf) < diff:
            diff = abs(tmpe-tmpf)
            e, f = tmpe, tmpf
    tmpans = max(c,d,e,f) - min(c,d,e,f)
    ans = min(ans, tmpans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
from itertools import accumulate
from bisect import bisect_left


N = int(input())
A = np.array(list(map(int, input().split())))
CumA = list(accumulate(A))
res = 10 ** 16

for i in range(1, N-2):
    leftidx = bisect_left(CumA, CumA[i] / 2) 
    P, Q = CumA[leftidx], CumA[i] - CumA[leftidx]
    if np.abs(P - Q) > np.abs(P - Q - 2 * A[leftidx]):
        P, Q = P - A[leftidx], Q + A[leftidx]

    rightidx = bisect_left(CumA, (CumA[-1] + CumA[i]) / 2)
    R, S = CumA[rightidx] - CumA[i], CumA[-1] - CumA[rightidx]
    if np.abs(R - S) > np.abs(R - S - 2 * A[rightidx]):
        R, S = R - A[rightidx], S + A[rightidx]

    res = min(res, max([P, Q, R, S] - min([P, Q, R, S])))

print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math


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

for i in range(1, N-1):
    leftidx = CumA.searchsorted(CumA[i] / 2) 
    P, Q = CumA[leftidx], CumA[i] - CumA[leftidx]
    if np.abs(P - Q) > np.abs(P - Q - 2 * A[leftidx]):
        P, Q = P - A[leftidx], Q + A[leftidx]

    rightidx = CumA.searchsorted((CumA[-1] + CumA[i]) / 2)
    R, S = CumA[rightidx] - CumA[i], CumA[-1] - CumA[rightidx]
    if np.abs(R - S) > np.abs(R - S - 2 * A[rightidx]):
        R, S = R - A[rightidx], S + A[rightidx]

    res = min(res, max([P, Q, R, S] - min([P, Q, R, S])))

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]
def dou(i,j):
    ma=j
    mi=i
    while ma-mi>1:
        mid = (ma + mi)//2
        a=A[j]-A[mid]
        b=A[mid-1]-A[i]
        if a>b:
            mi=mid
        else:
            ma=mid
        #print(ma,mi)
    return [A[mi]-A[i],A[j]-A[mi]]
num=10**14
for i in range(2,N-1):
    ans=[]
    ans+=dou(0,i)
    ans+=dou(i,N)
    #print(ans)
    t=max(ans)-min(ans)
    num=min(num,t)
print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]
def dou(X):
    n=len(X)
    ma=len(X)-1
    mi=0
    while ma-mi>1:
        mid = (ma + mi)//2
        a=X[n-1]-X[mid]
        b=X[mid-1]-X[0]
        if a>b:
            mi=mid
        else:
            ma=mid
        #print(ma,mi)
    return [X[mi]-X[0],X[n-1]-X[mi]]
num=10**14
K=A[:2]
L=deque(A[2:])
for i in range(2,N-1):
    a=L.popleft()
    L.appendleft(a)
    K.append(a)
    #print(K,L)
    ans=[]
    ans=ans+dou(K)+dou(L)
    #print(ans)
    #print(abs(max(ans)-min(ans)))
    num=min(num,abs(max(ans)-min(ans)))
    L.popleft()
print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]
def dou(X):
    n=len(X)
    ma=len(X)-1
    mi=0
    while ma-mi>1:
        mid = (ma + mi)//2
        a=X[n-1]-X[mid]
        b=X[mid-1]-X[0]
        if a>b:
            mi=mid
        else:
            ma=mid
        #print(ma,mi)
    return [X[mi]-X[0],X[n-1]-X[mi]]
num=10**14
K=A[:2]
L=deque(A[2:])
for i in range(2,N-1):
    a=L[0]
    K.append(a)
    #print(K,L)
    ans=[]
    ans=ans+dou(K)+dou(L)
    #print(ans)
    #print(abs(max(ans)-min(ans)))
    num=min(num,abs(max(ans)-min(ans)))
    L.popleft()
print(num)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]
def dou(X):
    n=len(X)
    ma=len(X)-1
    mi=0
    while ma-mi>1:
        mid = (ma + mi)//2
        a=X[n-1]-X[mid]
        b=X[mid-1]-X[0]
        if a>b:
            mi=mid
        else:
            ma=mid
        #print(ma,mi)
    return [X[mi]-X[0],X[n-1]-X[mi]]
num=10**14
for i in range(2,N-1):
    K=A[:i+1]
    L=A[i:]
    #print(K,L)
    ans=[]
    ans=ans+dou(K)+dou(L)
    #print(ans)
    num=min(num,abs(max(ans)-min(ans)))
print(num)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N=int(input())
A=input().split(" ")
for i in range(N):
	A[i]=int(A[i])
A=np.array(A)

"""
def divide1(S):
	length=len(S)
	mean=np.sum(S)/2
	P=[]
	Q=[]
	for i in range(length):
		P.append(S[i])
		if sum(P)>mean:
			Q=S[i+1::]
			break
	QQ=np.append(Q,P[-1])
	PP=np.delete(P,-1)
	if sum(P)-sum(Q)>sum(PP)-sum(QQ):
		P=PP
		Q=QQ
	if len(Q)==0:
		Q=np.append(Q,P[-1])
		del P[-1]
	if len(P)==1:
		P.append(Q[0])
		del Q[0]
	return P,Q

def divide2(S):
	length=len(S)
	mean=np.sum(S)/2
	P=[]
	Q=[]
	for i in range(length):
		P.append(S[i])
		if sum(P)>mean:
			Q=S[i+1::]
			break
	QQ=np.append(Q,P[-1])
	PP=np.delete(P,-1)
	if sum(P)-sum(Q)>sum(PP)-sum(QQ):
		P=PP
		Q=QQ
	if len(Q)==0:
		Q=np.append(Q,P[-1])
		del P[-1]
	return P,Q
"""

def divide(S):
	length=len(S)
	mean=np.sum(S)/2
	P=[]
	Q=[]
	for i in range(length):
		P.append(S[i])
		if sum(P)>mean:
			Q=S[i+1::]
			break
	QQ=np.append(P[-1],Q)
	PP=P[:-1:]
	if np.abs(sum(P)-sum(Q))>np.abs(sum(PP)-sum(QQ)):
		P=PP
		Q=QQ
	return P,Q

ans=10000
P,Q=divide(A)
p,q=divide(P)
r,s=divide(Q)
sump=sum(p)
sumq=sum(q)
sumr=sum(r)
sums=sum(s)
a=[sump,sumq,sumr,sums]
ans=max(a)-min(a)

QQ=np.append(P[-1],Q)
PP=np.delete(P,-1)
if len(PP)>1 and len(QQ)>1:
	p,q=divide(PP)
	r,s=divide(QQ)
	sump=sum(p)
	sumq=sum(q)
	sumr=sum(r)
	sums=sum(s)
	a=[sump,sumq,sumr,sums]
	if ans>max(a)-min(a):
		ans=max(a)-min(a)

PP=np.append(P,Q[0])
QQ=np.delete(Q,0)
if len(PP)>1 and len(QQ)>1:
	p,q=divide(PP)
	r,s=divide(QQ)
	sump=sum(p)
	sumq=sum(q)
	sumr=sum(r)
	sums=sum(s)
	a=[sump,sumq,sumr,sums]
	if ans>max(a)-min(a):
		ans=max(a)-min(a)

print(int(ans))