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:
#!/usr/bin/env python3
import bisect

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

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

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

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

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

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

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

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


    print(min_d)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

    for i2 in range(i2_lo, i2_hi + 1):
        i1 = bisect.bisect_right(B, B[i2 - 1] / 2, lo = 1, hi = i2)
        i3 = bisect.bisect_right(B, B[N - 1] / 2 + B[i2 - 1] / 2, lo = i2 + 1)
        i1_lo = i1_hi = i1
        i3_lo = i3_hi = i3
        if B[i1 - 1] * 2 != B[i2 - 1] and i1 + 1 < i2:
            i1_hi += 1
        if B[i3 - 1] * 2 != B[N - 1] + B[i2 - 1] and i3 + 1 < N:
            i3_hi += 1

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


    print(min_d)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import itertools
sp_l = list(itertools.combinations(range(N-1), 3))

calc_l = []

for i,j,k in sp_l:
    
    P = sum(A_l[:i+1])
    Q = sum(A_l[i+1:j+1])
    R = sum(A_l[j+1:k+1])
    S = sum(A_l[k+1:])

    calc_l.append(abs(max(P,Q,R,S) - min(P,Q,R,S)))

print(min(calc_l))

Submission status: Time Limit Exceeded

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

ruiseki = [0]
sum_a = 0
for a in a_list:
    ruiseki.append(ruiseki[-1]+a)
ruiseki = ruiseki[1:]
#4つに切るので間は３つまず真ん中から決める
all_pos = []
min_diff_BCDE = float("inf")
for middle in range(1,n-2):

    #左側がどこか決める
    min_left = 0
    min_diff_BC = float("inf")
    for left in range(middle):
        diff_BC = abs(ruiseki[middle] - 2*ruiseki[left])
        if diff_BC < min_diff_BC:
            min_left = left
            min_diff_BC = diff_BC
        else:
            break
        
    #右側がどこか決める
    min_right = 0
    min_diff_DE = float("inf")
    for right in range(middle,n-1):
        diff_DE = abs(ruiseki[-1]-2*ruiseki[right]+ruiseki[middle])
        if diff_DE < min_diff_DE:
            min_right = right
            min_diff_DE = diff_DE
        else:
            break

    group = []
    diff_BCDE = abs(max(ruiseki[min_left],ruiseki[middle] - ruiseki[min_left],ruiseki[min_right] - ruiseki[middle],ruiseki[-1]-ruiseki[min_right])-min(ruiseki[min_left],ruiseki[middle] - ruiseki[min_left],ruiseki[min_right] - ruiseki[middle],ruiseki[-1]-ruiseki[min_right]))
    if diff_BCDE < min_diff_BCDE:
        min_diff_BCDE = diff_BCDE
print(min_diff_BCDE)

Submission status: Time Limit Exceeded

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

ruiseki = [0]
sum_a = 0
for a in a_list:
    ruiseki.append(ruiseki[-1]+a)
ruiseki = ruiseki[1:]

all_pos = []
min_diff_BCDE = float("inf")
for middle in range(1,n-2):


    min_left = 0
    min_diff_BC = float("inf")
    for left in range(middle):
        diff_BC = abs(ruiseki[middle] - 2*ruiseki[left])
        if diff_BC < min_diff_BC:
            min_left = left
            min_diff_BC = diff_BC
        

    min_right = 0
    min_diff_DE = float("inf")
    for right in range(middle,n-1):
        diff_DE = abs(ruiseki[-1]-2*ruiseki[right]+ruiseki[middle])
        if diff_DE < min_diff_DE:
            min_right = right
            min_diff_DE = diff_DE
    group = []
    diff_BCDE = abs(max(ruiseki[min_left],ruiseki[middle] - ruiseki[min_left],ruiseki[min_right] - ruiseki[middle],ruiseki[-1]-ruiseki[min_right])-min(ruiseki[min_left],ruiseki[middle] - ruiseki[min_left],ruiseki[min_right] - ruiseki[middle],ruiseki[-1]-ruiseki[min_right]))
    if diff_BCDE < min_diff_BCDE:
        min_diff_BCDE = diff_BCDE
print(min_diff_BCDE)

Submission status: Time Limit Exceeded

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

ruiseki = []
sum_a = 0
for a in a_list:
    sum_a += a 
    ruiseki.append(sum_a)

#4つに切るので間は３つまず真ん中から決める
all_pos = []
min_diff_BCDE = float("inf")
for middle in range(1,n-2):

    #左側がどこか決める
    min_left = 0
    min_diff_BC = float("inf")
    for left in range(middle):
        B = ruiseki[left]
        C = ruiseki[middle] - ruiseki[left]
        diff_BC =abs(C-B) 
        if diff_BC < min_diff_BC:
            min_left = left
            min_diff_BC = diff_BC
        
    #右側がどこか決める
    min_right = 0
    min_diff_DE = float("inf")
    for right in range(middle,n-1):
        D = ruiseki[right] - ruiseki[middle]
        E = ruiseki[n-1]-ruiseki[right]
        diff_DE = abs(D-E)
        if diff_DE < min_diff_DE:
            min_right = right
            min_diff_DE = diff_DE
    group = [ruiseki[min_left],ruiseki[middle] - ruiseki[min_left],ruiseki[min_right] - ruiseki[middle],ruiseki[n-1]-ruiseki[min_right]]
    diff_BCDE = abs(max(group)-min(group))
    if diff_BCDE < min_diff_BCDE:
        min_diff_BCDE = diff_BCDE
print(min_diff_BCDE)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from bisect import bisect_left
N = int(input())
A = list(map(int, input().split()))
A = list(accumulate(A))

ans = float('inf')
# 切る位置を全探索
for mid in range(2, N - 1):
    L, R = A[:mid], A[mid:]
    L_target, R_target = L[-1] / 2, (L[-1] + R[-1]) / 2
    L_index, R_index = bisect_left(L, L_target), bisect_left(R, R_target)

    if abs(L[L_index - 1] - L_target) < abs(L[L_index] - L_target):
        L_index -= 1
    if abs(R[R_index - 1] - R_target) < abs(R[R_index] - R_target):
        R_index -= 1

    P, Q, R, S = L[L_index], L[-1]-L[L_index], R[R_index]-L[-1], R[-1]-R[R_index]
    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()))
cums = [0]
for a in A:
    cums.append(cums[-1] + a)

ans = 10**18
for i in range(2,N-1):
    lsum, rsum = cums[i], cums[-1]-cums[i]
    li = bisect(cums[:i], lsum//2)
    ri = bisect(cums[i:], lsum + rsum//2) + i
    for a in range(li-1,li+2):
        if not 0 < a < i: continue
        p,q = cums[a], lsum-cums[a]
        for b in range(ri-1,ri+2):
            if not i < b < N: continue
            r = cums[b]-lsum
            s = rsum - r
            mx,mn = max(p,q,r,s), min(p,q,r,s)
            ans = min(ans, mx-mn)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = [0 for _ in range(N+1)]
for i in range(1,N+1):
    S[i] = S[i-1]+A[i-1] #strictly increasing
def binSearch(L,R):
    """
    L,R should be 1..N
    and L < R
    search for min(n) s.t. S[n]-S[L-1] >= half
    """
    total = S[R]-S[L-1]
    half = total/2 #it's float
    ok = R
    ng = L-1
    while ok >= ng+2:
        mid = (ok+ng)//2
        if S[mid]-S[L-1] >= half:
            ok = mid
        else:
            ng = mid
    deltaNG = abs(S[ng]-S[L-1]-half)
    deltaOK = abs(S[ok]-S[L-1]-half)
    if deltaNG < deltaOK:
        x = S[ng]-S[L-1]
        y = S[R] - S[ng]
    else:
        x = S[ok]-S[L-1]
        y = S[R] - S[ok]
    return(max(x,y),min(x,y))
def calcForMid(M):
    a,b = binSearch(1,M)
    c,d = binSearch(M+1,N)
    l = sorted([a,b,c,d])
    return(l[3]-l[0])
ans = S[N]
for m in range(2,N-1):
    ans = min(ans,calcForMid(m))
print(ans)

Submission status: Time Limit Exceeded

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

num = float("inf")
a = 0
b = 0
for i in range(1, N - 2):
    while S[a] < S[i] - S[a + 1]:
        a += 1
    b = i
    while S[b] - S[i] < S[N - 1] - S[b + 1]:
        b += 1

    P = [S[a], S[i] - S[a], S[b] - S[i], S[N - 1] - S[b]]
    num = min(num, abs(max(P) - min(P)))

print(num)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np

d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


def left_diff(array):
    """
    array: ordered ndarray, len(array) >= 2
    """
    x = (array[-1] + 1) // 2
    mid = np.searchsorted(array, x)
    if abs(array[-1] - array[mid] * 2) < abs(array[-1] - array[mid-1] * 2):
        return array[mid], array[-1] - array[mid]
    else:
        return array[mid-1], array[-1] - array[mid-1]


def right_diff(array, offset):
    """
    array: ordered ndarray, len(array) >= 2
        target array or list

    offset: int
        offset value for right array
    """
    x = (array[-1] - offset + 1) // 2
    mid = np.searchsorted(array, x + offset)
    if abs(array[-1] - array[mid] * 2 + offset)\
            < abs(array[-1] - array[mid-1] * 2 + offset):
        return array[mid] - offset, array[-1] - array[mid]
    else:
        return array[mid-1] - offset, array[-1] - array[mid-1]


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


if __name__ == '__main__':
    N = d_in()
    a_array = np.array(ds_in())

    cum_a = np.cumsum(a_array)

    ans = 10**16
    for i in range(2, N-1):
        p, q = left_diff(cum_a[:i])
        r, s = right_diff(cum_a[i:], cum_a[i-1])
        ans = min(ans, calc_max_diff(p, q, r, s))

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
B = [A[0]]
ans = []
for i in range(N-1):
    B.append(B[i]+A[i+1])
for i in range(1,N-2):
    BC = 10000000000
    ifB = 0
    ifC = 0
    for j in range(i):
        left = B[j]
        right = B[i] - left
        x = abs(right-left)
        if BC > x:
            BC = x
            ifB = left
            ifC = right
    DE = 10000000000
    ifD = 0
    ifE = 0
    for j in range(i+1,N-1):
        left = B[j] - B[i]
        right = B[N-1] - B[j]
        x = abs(right-left)
        if DE > x:
            DE = x
            ifD = left
            ifE = right
    ans.append(max(ifB,ifC,ifD,ifE)-min(ifB,ifC,ifD,ifE))
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from bisect import bisect

def half(T, h):
    b = bisect(T,h)
    if abs(T[b-1]*2 - T[-1] - T[0]) <= abs(T[b]*2 - T[-1] - T[0]):
        return T[b-1] - T[0], T[-1]-T[b-1]
    return T[b] - T[0], T[-1]-T[b]
N = int( input())
A = list( map( int, input().split()))
S = [0] + list( accumulate(A))
ans = 10**9+1
for i in range(2, N-1):
    x, y = half(S[:i+1], S[i]//2)
    z, w = half(S[i:], (S[i] + S[-1])//2)
    m = min(x,y,z,w)
    M = max(x,y,z,w)
    if M-m < ans:
        ans = M-m
print(ans)

Submission status: Time Limit Exceeded

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

ans = float("inf")


def get_diff(left, center, right):
    return abs((cum_sum[center] - cum_sum[left]) - (cum_sum[right] - cum_sum[center]))


l_point = 1
r_point = 3

for C in range(2, N):
    while l_point + 1 < C and get_diff(0, l_point, C) > get_diff(0, l_point + 1, C):
        l_point += 1
    while r_point + 1 < N and get_diff(C, r_point, N) > get_diff(C, r_point + 1, N):
        r_point += 1

    pqrs = [cum_sum[l_point], cum_sum[C] - cum_sum[l_point], cum_sum[r_point] - cum_sum[C], cum_sum[N] - cum_sum[r_point]]
    ans = min(ans, max(pqrs) - min(pqrs))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8
import math
N = int(input())
A = list(map(int, input().split()))

def binsearch(seq, l, r, tar):
    # print("##", l, r, LmR[l:r + 1], tar)
    m = l + (r - l) // 2
    if l >= r: return l
    elif seq[m] < tar: return binsearch(seq, m + 1, r, tar)
    else: return binsearch(seq, l, m, tar)

Asum = [0]
tmp = 0
for Ai in A:
    tmp += Ai
    Asum.append(tmp)

LmR = []
for SAi in Asum[:-1]:
    LmR.append(-Asum[-1] + 2 * SAi)

# find b2 initial position (sub-optimal)
tar = 0
b2 = binsearch(LmR, 2, N - 2, tar)
if tar - LmR[b2 - 1] < LmR[b2] - tar: b2 = max((2, b2 - 1))
# b1
tar = -(Asum[N] - Asum[b2])
b1 = binsearch(LmR, 1, b2 - 1, tar)
if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
# b3
tar = Asum[b2]
b3 = binsearch(LmR, b2 + 1, N - 1, tar)
if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))

parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
ans = max(parts) - min(parts)
b2_init = b2

# sweep b2
for b2 in range(2, N - 1):
    # escape
    if b2 == b2_init: continue
    elif LmR[b2] < -2 * ans: continue
    elif LmR[b2] > 2 * ans: break
    # b1
    tar = -(Asum[N] - Asum[b2])
    b1 = binsearch(LmR, 1, b2 - 1, tar)
    if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
    # escape
    if math.fabs((Asum[b2] - Asum[b1]) - (Asum[b1])) >= ans: continue
    # b3
    tar = Asum[b2]
    b3 = binsearch(LmR, b2 + 1, N - 1, tar)
    if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))
    parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
    if max(parts) - min(parts) < ans: ans = max(parts) - min(parts)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8
import math
N = int(input())
A = list(map(int, input().split()))

def binsearch(seq, l, r, tar):
    # print("##", l, r, LmR[l:r + 1], tar)
    m = l + (r - l) // 2
    if l >= r: return l
    elif seq[m] < tar: return binsearch(seq, m + 1, r, tar)
    else: return binsearch(seq, l, m, tar)

Asum = [0]
tmp = 0
for Ai in A:
    tmp += Ai
    Asum.append(tmp)

LmR = []
for SAi in Asum[:-1]:
    LmR.append(-Asum[-1] + 2 * SAi)

ans = max(A) - min(A)
for b2 in range(2, N - 1):
    # escape
    if LmR[b2] < -2 * ans: continue
    elif 2 * ans < LmR[b2]: break
    # b1
    tar = -(Asum[N] - Asum[b2])
    b1 = binsearch(LmR, 1, b2 - 1, tar)
    if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
    # escape
    if math.fabs((Asum[b2] - Asum[b1]) - (Asum[b1])) >= ans: continue
    # b3
    tar = Asum[b2]
    b3 = binsearch(LmR, b2 + 1, N - 1, tar)
    if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))
    parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
    if max(parts) - min(parts) < ans: ans = max(parts) - min(parts)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8
import math
N = int(input())
A = list(map(int, input().split()))

def binsearch(seq, l, r, tar):
    # print("##", l, r, LmR[l:r + 1], tar)
    m = l + (r - l) // 2
    if l >= r: return l
    elif seq[m] < tar: return binsearch(seq, m + 1, r, tar)
    else: return binsearch(seq, l, m, tar)

Asum = [0]
tmp = 0
for Ai in A:
    tmp += Ai
    Asum.append(tmp)

LmR = []
for SAi in Asum[:-1]:
    LmR.append(-Asum[-1] + 2 * SAi)

ans = max(A) - min(A)
for b2 in range(2, N - 1):
    # b1
    tar = -(Asum[N] - Asum[b2])
    b1 = binsearch(LmR, 1, b2 - 1, tar)
    if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
    # escape
    if math.fabs((Asum[b2] - Asum[b1]) - (Asum[b1])) >= ans: continue
    # b3
    tar = Asum[b2]
    b3 = binsearch(LmR, b2 + 1, N - 1, tar)
    if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))
    parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
    if max(parts) - min(parts) < ans: ans = max(parts) - min(parts)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8
import math
N = int(input())
A = list(map(int, input().split()))

def binsearch(seq, l, r, tar):
    # print("##", l, r, LmR[l:r + 1], tar)
    m = l + (r - l) // 2
    if l >= r: return l
    elif seq[m] < tar: return binsearch(seq, m + 1, r, tar)
    else: return binsearch(seq, l, m, tar)

Asum = [0]
tmp = 0
for Ai in A:
    tmp += Ai
    Asum.append(tmp)

LmR = []
for SAi in Asum[:-1]:
    LmR.append(-Asum[-1] + 2 * SAi)
    
# print("###", LmR)
# # b2
# tar = 0
# for b2, val in enumerate(LmR):
#     if val < tar: break
# if LmR[b2 - 1] < -LmR[b2]: b2 -= 1

ans = max(A) - min(A)
for b2 in range(2, N - 1):
    # b1
    tar = -sum(A[b2:])
    # for b1, val in enumerate(LmR):
    #     if val < tar: break
    b1 = binsearch(LmR, 1, b2 - 1, tar)
    if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
    # escape
    if math.fabs((Asum[b2] - Asum[b1]) - (Asum[b1])) >= ans: continue
    # b3
    tar = sum(A[:b2])
    # for b3, val in enumerate(LmR):
    #     if val < tar: break
    b3 = binsearch(LmR, b2 + 1, N - 1, tar)
    if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))
    # parts = (sum(A[:b1]), sum(A[b1:b2]), sum(A[b2:b3]), sum(A[b3:]))
    parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
    # print("#", A[:b1], A[b1:b2], A[b2:b3], A[b3:], parts)
    if max(parts) - min(parts) < ans: ans = max(parts) - min(parts)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8
N = int(input())
A = list(map(int, input().split()))

def binsearch(seq, l, r, tar):
    # print("##", l, r, LmR[l:r + 1], tar)
    m = l + (r - l) // 2
    if l >= r: return l
    elif seq[m] < tar: return binsearch(seq, m + 1, r, tar)
    else: return binsearch(seq, l, m, tar)

tmp = -sum(A)
LmR = [tmp]
for Ai in A[:-1]:
    tmp += 2 * Ai
    LmR.append(tmp)

# print("###", LmR)
# # b2
# tar = 0
# for b2, val in enumerate(LmR):
#     if val < tar: break
# if LmR[b2 - 1] < -LmR[b2]: b2 -= 1

ans = sum(A)
for b2 in range(2, N - 1):
    # b1
    tar = -sum(A[b2:])
    # for b1, val in enumerate(LmR):
    #     if val < tar: break
    b1 = binsearch(LmR, 1, b2 - 1, tar)
    if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
    # b3
    tar = sum(A[:b2])
    # for b3, val in enumerate(LmR):
    #     if val < tar: break
    b3 = binsearch(LmR, b2 + 1, N - 1, tar)
    if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))

    parts = (sum(A[:b1]), sum(A[b1:b2]), sum(A[b2:b3]), sum(A[b3:]))
    # print("#", A[:b1], A[b1:b2], A[b2:b3], A[b3:], max(parts) - min(parts))
    if max(parts) - min(parts) < ans: ans = max(parts) - min(parts)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

INF = float('inf')


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


def binary_search(A, x):
    low = 0
    high = len(A) - 1
    mid = (low + high) // 2

    while low <= high:
        if A[mid] == x:
            break
        elif A[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
        mid = (low + high) // 2

    if mid < 0:
        return 0
    else:
        return mid


N = int(input())

A = inpl()
B = A[:]

# 累積和
for i in range(1, N):
    B[i] = B[i] + B[i - 1]

ans = INF
for mid in range(2, N - 1):
    L = B[:mid]
    R = B[mid:]
    R = [R[i] - L[-1] for i in range(len(R))]
    # print(L)
    # print(R)

    sum_list = []
    for li in [L, R]:
        if len(li) == 2:  # R, Lの要素数が2の場合の分け方は1通り
            sum_list.append(li[0])
            sum_list.append(li[1] - li[0])
            continue

        # 真ん中の切れ込みが固定されている時のRとLの切れ込みの決定
        mid = binary_search(li, li[-1] // 2)

        diff1 = abs(2 * li[mid] - li[-1])
        diff2 = abs(2 * li[mid + 1] - li[-1])

        if diff1 < diff2:
            sum_list.append(li[mid])
            sum_list.append(li[-1] - li[mid])
        else:
            sum_list.append(li[mid + 1])
            sum_list.append(li[-1] - li[mid + 1])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ans=9999999999
list=[int(x) for x in input().split()]
cums=[]
cums=[list[0]]
dlist=[]
p,q,r,s=0,0,0,0
for i in range(1,n):
    cums.append(cums[i-1]+list[i])
for j in range(0,n-3):
    for k in range(j+1,n-2):
        for l in range(k+1,n-1):
            p=abs(cums[j])
            q=abs(cums[k]-cums[j])
            r=abs(cums[l]-cums[k])
            s=abs(cums[n-1]-cums[l])
            dlist=[p,q,r,s]
            ans=min(ans, max(dlist)-min(dlist))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
DIFFfix = SUM = sum(A)
for i in range(N-3):
  Q = sum(A[:i+2]); S = SUM - Q
  P = R = Pfix = Rfix = 0
  Qfix = Q; Sfix = S
  m = 0
  flag = True
  while flag:
    m += 1
    P += A[m-1]
    Q -= A[m-1]
    if abs(P-Q) < abs(Pfix - Qfix):
      Pfix = P; Qfix = Q
    else:
      flag = False
  m = 0
  flag = True
  while flag:
    m += 1
    R += A[i+m+1]
    S -= A[i+m+1]
    if abs(R-S) < abs(Rfix - Sfix):
      Rfix = R; Sfix = S
    else:
      flag = False
  DIFF = abs(max(Pfix,Qfix,Rfix,Sfix)-min(Pfix,Qfix,Rfix,Sfix))
  if DIFF < DIFFfix:
    DIFFfix = DIFF
print(DIFFfix)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

answer = 10 ** 9

for i in range(N-2):
    l, r = 0, i
    for l in range(0, i):
        if abs(a[i] - 2*a[l+1]) >= abs(a[i] - 2*a[l]):
            break
    for r in range(i, N-1):
        if abs(a[-1] - 2*a[r+1] + a[i]) >= abs(a[-1] - 2*a[r] + a[i]):
            break

    p, q, r, s = a[l], a[i] - a[l], a[r] - a[i], a[-1] - a[r]
    answer = min(answer, max(p, q, r, s)-min(p, q, r, s))

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

answer = 10 ** 9

for i in range(N-2):
    l, r = 0, i
    while abs(a[i] - 2*a[l+1]) < abs(a[i] - 2*a[l]) and l < i-1:
        l += 1
    while abs(a[-1] - 2*a[r+1] + a[i]) < abs(a[-1] - 2*a[r] + a[i]) and r < N-2:
        r += 1

    p, q, r, s = a[l], a[i] - a[l], a[r] - a[i], a[-1] - a[r]
    answer = min(answer, max(p, q, r, s)-min(p, q, r, s))

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

answer = 10 ** 9

def get_dividing_index(l, r): 
    if l+1 == r:
        return l

    right = accumulate_A[r] - accumulate_A[l]
    left = A[l]
    prev = abs(right - left)

    for i in range(l+1, r): 
        left += A[i]
        right -= A[i]
        diff = abs(right - left)
        if diff > prev:
            return i-1 
        prev = diff

    return i


for i in range(2, N-1):
    L = get_dividing_index(0, i-1)
    R = get_dividing_index(i, N-1)

    p = accumulate_A[L]
    q = accumulate_A[i-1] - accumulate_A[L]
    r = accumulate_A[R] - accumulate_A[i-1]
    s = accumulate_A[N-1] - accumulate_A[R]

    answer = min(answer, abs(max(p, q, r, s)-min(p, q, r, s)))

print(answer)

Submission status: Time Limit Exceeded

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

answer = 10 ** 9
for i in range(1, N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            p = sum(A[0:i])
            q = sum(A[i:j])
            r = sum(A[j:k])
            s = sum(A[k:])
            #print(A[0:i], A[i:j], A[j:k], A[k:])

            max_ = max([p, q, r, s])
            min_ = min([p, q, r, s])
            #print('max, min:', max_, min_)

            #print(abs(max_-min_))
            answer = min(answer, abs(max_-min_))

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

def func(n1, n2, n3):
    vals = np.array([np.sum(A[:n1+1]),\
                     np.sum(A[n1+1:n2+1]),\
                     np.sum(A[n2+1:n3+1]),\
                     np.sum(A[n3+1:])])
    return np.max(vals) - np.min(vals)

ind = [0,0,0]
out = float("inf")
for n1 in range(N-3):
    for n2 in range(n1+1, N-2):
        for n3 in range(n2+1, N-1):
            val = func(n1, n2, n3)
            if val < out:
                out = val
                ind = [n1, n2, n3]
print(out)

Submission status: Time Limit Exceeded

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

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

def sum_a(i, j):
    return t[j]-t[i]

min_dif = sum_a(0, n)

for i in range(2, n-1):
    j0 = 0
    j1 = i
    u = sum_a(0, i) // 2
    while j1 - j0 > 1:
        j = (j0+j1) // 2
        if sum_a(0, j) <= u: 
            j0 = j
        else:
            j1 = j
    if abs(sum_a(0, j0)-sum_a(j0, i)) < abs(sum_a(0, j1) - sum_a(j1, i)): 
        p = sum_a(0, j0)
        q = sum_a(j0, i)
    else:
        p = sum_a(0, j1)
        q = sum_a(j1, i)

    j0 = i
    j1 = n
    u = sum_a(i, n) // 2
    while j1 - j0 > 1:
        j = (j0+j1) // 2
        if sum_a(i, j) <= u: 
            j0 = j
        else:
            j1 = j
    if abs(sum_a(i, j0)-sum_a(j0, n)) < abs(sum_a(i, j1) - sum_a(j1, n)): 
        r = sum_a(i, j0)
        s = sum_a(j0, n)
    else:
        r = sum_a(i, j1)
        s = sum_a(j1, n)

    min_dif = min(min_dif, max(p, q, r, s)-min(p, q, r, s))

print(min_dif)

Submission status: Time Limit Exceeded

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

sm = 0
for i in range(0, n):
    sm = sm + a[i]

min_dif = sm

p = 0
for i in range(n-3):
    p = p + a[i]
    if 4*p < sm:
        next
    q = 0
    for j in range(i+1, n-2):
        q = q + a[j]
        if 3*q < sm - p:
            next
        r = 0
        for k in range(j+1, n-1):
            r = r + a[k]
            if 2*r < sm - p - q:
                next
            s = 0
            for l in range(k+1, n):
                s = s + a[l]
            d = max([p, q, r, s])-min([p, q, r, s])
            min_dif = min([d, min_dif])

p = 0
for i in range(n-3):
    p = p + a[i]
    if 4*p <= sm - 3*min_dif or 4*p >= sm + 3*min_dif:
        next
    q = 0
    for j in range(i+1, n-2):
        q = q + a[j]
        if abs(p-q) >= min_dif or 4*q <= sm - 3*min_dif or 4*q >= sm + 3*min_dif:
            next
        r = 0
        for k in range(j+1, n-1):
            r = r + a[k]
            if abs(p-r) >= min_dif or abs(q-r) >= min_dif or 4*r <= sm - 3*min_dif or 4*r >= sm + 3*min_dif:
                next
            s = 0
            for l in range(k+1, n):
                s = s + a[l]
            d = max([p, q, r, s])-min([p, q, r, s])
            min_dif = min([d, min_dif])

print(min_dif)

Submission status: Time Limit Exceeded

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

sm = 0
for i in range(0, n):
    sm = sm + a[i]

min_dif = sm

p = 0
for i in range(n-3):
    p = p + a[i]
    if 4*p < sm:
        next
    q = 0
    for j in range(i+1, n-2):
        q = q + a[j]
        if 3*q < sm - p:
            next
        r = 0
        for k in range(j+1, n-1):
            r = r + a[k]
            if 2*r < sm - p - q:
                next
            s = 0
            for l in range(k+1, n):
                s = s + a[l]
            d = max([p, q, r, s])-min([p, q, r, s])
            min_dif = min([d, min_dif])

p = 0
for i in range(n-3):
    p = p + a[i]
    if 4*p <= sm - 3*min_dif or 4*p >= sm + 3*min_dif:
        next
    q = 0
    for j in range(i+1, n-2):
        q = q + a[j]
        if 4*q <= sm - 3*min_dif or 4*q >= sm + 3*min_dif:
            next
        r = 0
        for k in range(j+1, n-1):
            r = r + a[k]
            if 4*r <= sm - 3*min_dif or 4*r >= sm + 3*min_dif:
                next
            s = 0
            for l in range(k+1, n):
                s = s + a[l]
            d = max([p, q, r, s])-min([p, q, r, s])
            min_dif = min([d, min_dif])

print(min_dif)

Submission status: Time Limit Exceeded

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

sm = 0
for i in range(0, n):
    sm = sm + a[i]

min_dif = sm

p = 0
for i in range(n-3):
    p = p + a[i]
    if 4*p <= sm - 3*min_dif or 4*p >= sm + 3*min_dif:
        next
    q = 0
    for j in range(i+1, n-2):
        q = q + a[j]
        if 4*q <= sm - 3*min_dif or 4*q >= sm + 3*min_dif:
            next
        r = 0
        for k in range(j+1, n-1):
            r = r + a[k]
            if 4*r <= sm - 3*min_dif or 4*r >= sm + 3*min_dif:
                next
            s = 0
            for l in range(k+1, n):
                s = s + a[l]
            d = max([p, q, r, s])-min([p, q, r, s])
            min_dif = min([d, min_dif])

print(min_dif)