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 = [int(i) for i in input().split()]

sum_list = [0]
for i in range(N):
    sum_list.append(A[i] + sum_list[i])

def my_sum(array, begin, end):
    if begin+1 == end:
        summary = array[begin]
    else:
        summary = sum_list[end] - sum_list[begin]

    return summary

diff_list = []

for c2 in range(2, N-1):
    
    tmp_diff = None
    
    for c1 in range(1, c2):
        P = my_sum(A, 0, c1)
        Q = my_sum(A, c1, c2)
        
        diff = abs(P - Q)
        if tmp_diff == None or diff < tmp_diff:
            tmp_diff = diff
            tmp_P = P
            tmp_Q = Q
    
    tmp_diff = None
    
    for c3 in range(c2+1, N):
        R = my_sum(A, c2, c3)
        S = my_sum(A, c3, N)
        
        diff = abs(R - S)
        if tmp_diff == None or diff < tmp_diff:
            tmp_diff = diff
            tmp_R = R
            tmp_S = S
            
    max_sum = max(tmp_P, tmp_Q, tmp_R, tmp_S)
    min_sum = min(tmp_P, tmp_Q, tmp_R, tmp_S)
            
    diff_list.append(max_sum - min_sum)
            
print(min(diff_list))

Submission status: Time Limit Exceeded

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

sum_list = [0]
for i in range(N):
    sum_list.append(A[i] + sum_list[i])

def my_sum(array, begin, end):
    if begin+1 == end:
        summary = array[begin]
    else:
        summary = sum_list[end] - sum_list[begin]

    return summary

diff_list = []

for c2 in range(2, N-1):
    for c1 in range(1, c2):
        P = my_sum(A, 0, c1)
        Q = my_sum(A, c1, c2)
        
        for c3 in range(c2+1, N):
            R = my_sum(A, c2, c3)
            S = my_sum(A, c3, N)
            
            max_sum = max(P, Q, R, S)
            min_sum = min(P, Q, R, S)
            
            diff_list.append(max_sum - min_sum)
            
print(min(diff_list))

Submission status: Time Limit Exceeded

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

from numpy import cumsum, insert
sum_list = cumsum(A)
sum_list = insert(sum_list, 0, 0)

def my_sum(array, begin, end):
    if begin+1 == end:
        summary = array[begin]
    else:
        summary = sum_list[end] - sum_list[begin]

    return summary

diff_list = []

for c2 in range(2, N-1):
    for c1 in range(1, c2):
        P = my_sum(A, 0, c1)
        Q = my_sum(A, c1, c2)
        
        for c3 in range(c2+1, N):
            R = my_sum(A, c2, c3)
            S = my_sum(A, c3, N)
            
            max_sum = max(P, Q, R, S)
            min_sum = min(P, Q, R, S)
            
            diff_list.append(max_sum - min_sum)
            
print(min(diff_list))

Submission status: Time Limit Exceeded

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

cache = {}

def my_sum(array, begin, end):
    index = (begin, end)
    
    if index in cache:
        summary = cache[index]
    else:
        summary = sum(array[begin:end])
        cache[index] = summary
    
    return summary

diff_list = []

for c2 in range(2, N-1):
    for c1 in range(1, c2):
        P = my_sum(A, 0, c1)
        Q = my_sum(A, c1, c2)
        
        for c3 in range(c2+1, N):
            R = my_sum(A, c2, c3)
            S = my_sum(A, c3, N)
            
            max_sum = max(P, Q, R, S)
            min_sum = min(P, Q, R, S)
            
            diff_list.append(max_sum - min_sum)
            
print(min(diff_list))

Submission status: Time Limit Exceeded

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

diff_list = []

for c2 in range(2, N-1):
    for c1 in range(1, c2):
        P = sum(A[0:c1])
        Q = sum(A[c1:c2])
        
        for c3 in range(c2+1, N):
            R = sum(A[c2:c3])
            S = sum(A[c3:N])
            
            max_sum = max(P, Q, R, S)
            min_sum = min(P, Q, R, S)
            
            diff_list.append(max_sum - min_sum)
            
print(min(diff_list))

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:
    A_cs = list(np.cumsum(A))
    for i in range(2, N - 1):
        left_cs = A_cs[:i]
        right_cs = A_cs[i:] - left_cs[-1]
        left_mean_index = np.searchsorted(left_cs, left_cs[-1] / 2)
        right_mean_index = np.searchsorted(right_cs, right_cs[-1] / 2)
        for l in range(2):
            for k in range(2):
                P = left_cs[left_mean_index - l]
                Q = left_cs[-1] - P
                R = right_cs[right_mean_index - k]
                S = right_cs[-1] - R
                ans = min(ans, (max(P, Q, R, S) - min(P, Q, R, S)))


print(ans)

Submission status: Time Limit Exceeded

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

import numpy as np
ans = float("inf")
if N == 4:
    ans = min(ans, (max(A) - min(A)))
else:
    for i in range(2, N - 1):
        left_cs = list(np.cumsum(A[:i]))
        right_cs = list(np.cumsum(A[i:]))
        left_mean_index = np.searchsorted(left_cs, left_cs[-1] / 2)
        right_mean_index = np.searchsorted(right_cs, right_cs[-1] / 2)
        for l in range(2):
            for k in range(2):
                P = left_cs[left_mean_index - l]
                Q = left_cs[-1] - P
                R = right_cs[right_mean_index - k]
                S = right_cs[-1] - R
                ans = min(ans, (max(P, Q, R, S) - min(P, Q, R, S)))
               

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
B,C,D,E = [],[],[],[]
b,c,d,e =0,0,0,0
ans = 10**10
for i in range(0,N-3):
    for j in range(i+1,N-2):
        for k in range(j+1,N-1):
            B = A[0:i+1]
            C = A[i+1:j+1]
            D = A[j+1:k+1]
            E = A[k+1:N]
            b =sum(B)
            c =sum(C)
            d =sum(D)
            e =sum(E)
            if ans > abs(max(b,c,d,e)-min(b,c,d,e)):
                ans = abs(max(b,c,d,e)-min(b,c,d,e))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
li = input().rstrip().split()


le = [0]*N
for i in range(0,N):
    le[i]=int(li[i])

#愚直に解く
array = [0]*4
conbi = []

minmin = 10**10
s = 0
for i in range(1,N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            conbi.append([i,j,k])


for i in range(0,len(conbi)):
    array[0]=sum(le[0:conbi[i][0]])
    array[1]=sum(le[conbi[i][0]:conbi[i][1]])
    array[2]=sum(le[conbi[i][1]:conbi[i][2]])
    array[3]=sum(le[conbi[i][2]:])
    mx = max(array)
    mn = min(array)
    u = mx-mn
    if minmin > u:
        minmin = u

print(minmin)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
li = input().rstrip().split()

le = [0]*N
for i in range(0,N):
    le[i]=int(li[i])

#愚直に解く
# n = comb(N-1, 3, exact=True)
array = [0]*4

minmin = 10**10
for i in range(1,N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            array[0]=sum(le[0:i])
            array[1]=sum(le[i:j])
            array[2]=sum(le[j:k])
            array[3]=sum(le[k:])
            mx = max(array)
            mn = min(array)
            u = mx-mn
            # print(u)
            # print(array)
            if minmin > u:
                minmin = u


print(minmin)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
B,C,D,E = [],[],[],[]
b,c,d,e =0,0,0,0
ans =[]
for i in range(0,N-3):
    for j in range(i+1,N-2):
        for k in range(j+1,N-1):
            B = A[0:i+1]
            C = A[i+1:j+1]
            D = A[j+1:k+1]
            E = A[k+1:N]
            b =sum(B)
            c =sum(C)
            d =sum(D)
            e =sum(E)
            ans.append(abs(max(b,c,d,e)-min(b,c,d,e)))
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
m_list = []
m_list.append(A_list[0])
for a in A_list[1:]:
    m_list.append(m_list[-1] + a)
min_t = pow(10,10)
length = len(A_list)
for k1 in range(1, length - 2):
    for k2 in range(k1, length - 1):
        for k3 in range(k2, length):
                if k1 != k2 and k2 != k3:
                    P = m_list[k1 - 1]
                    Q = m_list[k2 - 1] - P
                    R = m_list[k3 - 1] - P - Q
                    S = m_list[-1] - P - Q - R
                    t = max(P,Q,R,S) - min(P,Q,R,S)
                    min_t = min(t, min_t)
print(min_t)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
m_list = []
m_list.append(A_list[0])
for a in A_list[1:]:
    m_list.append(m_list[-1] + a)
min_t = pow(10,10)
length = len(A_list)
for k1 in range(1, length):
    for k2 in range(k1, length):
        for k3 in range(k2, length):
                if k1 != k2 and k2 != k3:
                    P = m_list[k1 - 1]
                    Q = m_list[k2 - 1] - P
                    R = m_list[k3 - 1] - P - Q
                    S = m_list[-1] - P - Q - R
                    t = max(P,Q,R,S) - min(P,Q,R,S)
                    min_t = min(t, min_t)
print(min_t)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
m_list = []
m_list.append(A_list[0])
for a in A_list[1:]:
    m_list.append(m_list[-1] + a)
min_t = pow(10,10)
for k1 in range(1, len(A_list)):
    for k2 in range(k1, len(A_list)):
        for k3 in range(k2, len(A_list)):
                if k1 != k2 and k2 != k3:
                    P = m_list[k1 - 1]
                    Q = m_list[k2 - 1] - P
                    R = m_list[k3 - 1] - P - Q
                    S = m_list[-1] - P - Q - R
                    t = max(P,Q,R,S) - min(P,Q,R,S)
                    min_t = min(t, min_t)
print(min_t)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
min_t = pow(10,10)
for k1 in range(1, len(A_list)):
    for k2 in range(k1, len(A_list)):
        for k3 in range(k2, len(A_list)):
                if k1 != k2 and k2 != k3:
                    P = sum(A_list[:k1])
                    Q = sum(A_list[k1:k2])
                    R = sum(A_list[k2:k3])
                    S = sum(A_list[k3:])
                    t = max(P,Q,R,S) - min(P,Q,R,S)
                    min_t = min(t, min_t)
print(min_t)

Submission status: Time Limit Exceeded

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

N = int(input())
A = list(map(int, input().split(" ")))
Acc = []
a = 0
for i in range(N):
    a += A[i]
    Acc.append(a)
# print(A)
# print(Acc)

def centerPoint(L):
    diff = 10000000000
    p = 0
    for i in range(len(L)):
        if abs(L[i] - (L[-1] - L[i])) < diff:
            diff = abs(L[i] - (L[-1] - L[i]))
            p = i
    return p
ret = 10000000000
for i in range(2, len(A)-1):
    p1 = centerPoint(Acc[:i])
    temp = list(map(lambda x: x - Acc[i-1], Acc[i:]))
    p2 = centerPoint(temp)
    # print(Acc[:i],temp)
    s1 = Acc[p1]
    s2 = Acc[i-1] - Acc[p1]
    s3 = Acc[p2+i] - Acc[i-1]
    s4 = Acc[-1] - Acc[p2+i]
    # print(s1,s2,s3,s4)
    # print(max(s1,s2,s3,s4) - min(s1,s2,s3,s4))
    if max(s1,s2,s3,s4) - min(s1,s2,s3,s4) < ret:
        ret = max(s1,s2,s3,s4) - min(s1,s2,s3,s4)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

_N = int(input())
_As = np.asarray(list(map(int, input().split())), dtype=np.int)
_AAs = np.add.accumulate(_As)

def _calculate_PQRS(_AAs, _index):
    (_i1, _i2, _i3) = _index
    return (_AAs[_i1 - 1],
            _AAs[_i2 - 1] - _AAs[_i1 - 1],
            _AAs[_i3 - 1] - _AAs[_i2 - 1],
            _AAs[-1] - _AAs[_i3 - 1])

def _evaluate(_AAs, _index):
    _PQRS = _calculate_PQRS(_AAs, _index)
    return np.abs(np.max(_PQRS) - np.min(_PQRS))


def _status(_As, _AAs, _index):
    print(_index)
    (_P, _Q, _R, _S) = _calculate_PQRS(_AAs, _index)
    print('P =', _P, _As[:_index[0]])
    print('Q =', _Q, _As[_index[0]:_index[1]])
    print('R =', _R, _As[_index[1]:_index[2]])
    print('S =', _S, _As[_index[2]:])
    print('Score =', _evaluate(_AAs, _index))

def _make_index(_N):
    _index_list = []
    for _i1 in range(_N - 2):
        for _i2 in range(_i1, _N - 1):
            for _i3 in range(_i2, _N):
                _index_list.append((_i1, _i2, _i3))
    return _index_list

_index_list = _make_index(_N)
_score = _AAs[-1]
for _il in _index_list:
    _new_score = _evaluate(_AAs, _il)
    if _new_score < _score:
        _score = _new_score

print(_score)

Submission status: Time Limit Exceeded

Solution code:
#  整数列の長さ N と整数列 listA を標準入力
N = int(input())
listA = list(map(int,input().split()))

def printData():
    print("max: " + str(max(p, q, r, s)) + " min: " + str(min(p, q, r, s)) + " p,q,r,s: " + str(p) + " " + str(q) + " "  + str(r) + " "  + str(sum(listA[right:])))
    print("left: " + str(left) + " center: " + str(center) + " right: " + str(right))
    print("minDiff_1: " + str(minDiff))

def calculation():
    p = sum(listA[0:left])
    q = sum(listA[left:center])
    r = sum(listA[center:right])
    s = sum(listA[right:])
    
    
    

left = 1
center = 2
right = 3

minDiff = 10**20

for center in range(2, N - 1):
    p = sum(listA[0:left])
    q = sum(listA[left:center])
    r = sum(listA[center:right])
    s = sum(listA[right:])
    
    minDiff = min(max(p, q, r, s) - min(p, q, r, s), minDiff)
             
    for right in range(center + 1, N):
        p = sum(listA[0:left])
        q = sum(listA[left:center])
        r = sum(listA[center:right])
        s = sum(listA[right:])
        
        minDiff = min(max(p, q, r, s) - min(p, q, r, s), minDiff)
             
        for left in range(1, center):
            p = sum(listA[0:left])
            q = sum(listA[left:center])
            r = sum(listA[center:right])
            s = sum(listA[right:])
            
            minDiff = min(max(p, q, r, s) - min(p, q, r, s), minDiff)

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

print(minDiff)

Submission status: Time Limit Exceeded

Solution code:
def calc_score(b, c, d, e):
    p = sum(b)
    q = sum(c)
    r = sum(d)
    s = sum(e)

    max_sum = max([p, q, r, s])
    min_sum = min([p, q, r, s])
    return abs(max_sum - min_sum)

def split_med(num_list, offset):
    cum_list = [sum(num_list[:i]) for i in range(len(num_list)+1)]
    med_ind = 0
    e = pow(10, 10)
    med = cum_list[len(cum_list)-1] // 2
    for i in range(len(cum_list)):
        if abs(med - cum_list[i]) < e:
            med_ind = i
            e = abs(med - cum_list[i])
    if med_ind + offset <= 0:
        return num_list[:1], num_list[1:]
    elif med_ind + offset >= len(num_list):
        return num_list[:len(num_list)-1], num_list[len(num_list)-1:]
    return num_list[:med_ind+offset], num_list[med_ind+offset:]

def split_and_calc_scores(num_list):
    offsets = [-2, -1, 0, 1, 2]
    scores = []
    for offset_1 in offsets:
        a_1, a_2 = split_med(num_list, offset_1)
        for offset_2 in offsets:
            b, c = split_med(a_1, offset_2)
            for offset_3 in offsets:
                d, e = split_med(a_2, offset_3)
                scores.append(calc_score(b, c, d, e))
    return scores

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

scores = split_and_calc_scores(a_list)

print(min(scores))

Submission status: Time Limit Exceeded

Solution code:
def cumlative_sum(l):
    sum = 0
    for i in l:
        yield sum + i
        sum += i

def F(l, base):
    m = min([(i, abs(l[-1] - 2*x + base)) for i, x in enumerate(l[:-1])], key=lambda x: x[1])[0]
    return (l[m] - base, l[-1] - l[m])

def FF(a, n):
    for i in range(2, N-1):
        Fp, Fq = F(CS_A[0:i], 0)
        Fr, Fs = F(CS_A[i:N], CS_A[i-1])
        yield max(Fp, Fq, Fr, Fs) - min(Fp, Fq, Fr, Fs)

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

CS_A = list(cumlative_sum(A))

print(min(FF(CS_A, N)))

Submission status: Time Limit Exceeded

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


# 累積
acc = [0]
for i in range(N):
    acc.append(acc[i] + A[i])


def dev_sec(start, end, previous_best):
    # check left
    dif_min = 10 ** 9
    best_p = -1
    best_q = -1
    best_sep= previous_best
    for p_end in range(previous_best, end):
        sum_of_p = acc[p_end + 1] - acc[start]
        sum_of_q = acc[end + 1] - acc[p_end + 1]
        # sumの最小
        dif = abs(sum_of_p - sum_of_q)
        if dif_min > dif:
            dif_min = dif
            best_p = sum_of_p
            best_q = sum_of_q
            best_sep = p_end
    return best_p, best_q , best_sep



dif_min = 10 ** 9
previous_best_left = 0
previous_best_right = 2
for left_end in range(1, N-2):

    p, q, previous_best_left = dev_sec(0, left_end, previous_best_left)
    r, s, previous_best_right = dev_sec(left_end + 1, N - 1, previous_best_right)

    dif = max(p, q, r, s) - min(p, q, r, s)
    if dif_min > dif:
        dif_min = dif
print(dif_min)

Submission status: Time Limit Exceeded

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


# 累積
acc = [0]
for i in range(N):
    acc.append(acc[i] + A[i])


def dev_sec(start, end):
    # check left
    dif_min = 10 ** 9
    best_p = -1
    best_q = -1
    for p_end in range(start, end):
        sum_of_p = acc[p_end + 1] - acc[start]
        sum_of_q = acc[end + 1] - acc[p_end + 1]
        # sumの最小
        dif = abs(sum_of_p - sum_of_q)
        if dif_min > dif:
            dif_min = dif
            best_p = sum_of_p
            best_q = sum_of_q
    return best_p, best_q



dif_min = 10 ** 9
for left_end in range(1, N-2):

    p, q = dev_sec(0, left_end)
    r, s = dev_sec(left_end + 1, N - 1)

    dif = max(p, q, r, s) - min(p, q, r, s)
    if dif_min > dif:
        dif_min = dif
print(dif_min)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

def S(a, b):
    return cl[b] - (0 if a == 0 else cl[a-1])

def partial(start, end, last):
    odiff = None
    for c in range(start, end+1):
        p = S(start,c)
        q = S(c+1,end)
        diff = abs(p-q)
        if odiff is None:
            odiff = diff
        if odiff < diff:
            return c, mp, mq
        odiff = diff
        mp = p
        mq = q

if __name__ == '__main__':
    # read input
    n = int(input())
    l = list(map(int, input().split()))
    # create cumlative list first
    cl = list(accumulate(l))
    clen = len(l)

    #  0  F(i)      i i+1 G(i)      len-1
    #  |------|------|-------|-------|
    #         c0    c1       c2
    #  <-----L------> <------R------->
    # pick up a c1 (i:i+1) and evaluate
    result = None
    c1 = 1
    c3 = 3
    for i in range(1,clen-2):
        # LEFT
        (c1, mb, mc) = partial(0, i, c1)
        # RIGHT
        c3, md, me = partial(i+1, clen-1, c3)

        # evaluate
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        if result is None:
            result = diff
        else:
            if result > diff:
                result = diff

    print(result)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

def S(a, b):
    return cl[b] - (0 if a == 0 else cl[a-1])

if __name__ == '__main__':
    # read input
    n = int(input())
    l = list(map(int, input().split()))
    # create cumlative list first
    cl = list(accumulate(l))
    clen = len(l)

    #  0  F(i)      i i+1 G(i)      len-1
    #  |------|------|-------|-------|
    #         c0    c1       c2
    #  <-----L------> <------R------->
    # pick up a c1 (i:i+1) and evaluate
    r = list()
    result = None
    for i in range(1,clen-2):
        #print("i={}\tL{}, R{}".format(i, l[0:i+1], l[i+1:]))

        # find C0 for each i
        odiff = None
        for c in range(i):
            B = S(0,c)
            C = S(c+1,i)
            diff = abs(B-C)
            if odiff is None:
                odiff = diff
            if odiff < diff:
                break
            odiff = diff
            mb = B
            mc = C

        # find C2 for each i
        odiff = None
        for c in range(i+1,clen-1):
            D = S(i+1, c)
            E = S(c+1, clen-1)
            diff = abs(E-D)
            if odiff is None:
                odiff = diff
            if odiff < diff:
                break
            odiff = diff
            md = D
            me = E

        # evaluate
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        if result is None:
            result = diff
        else:
            if result > diff:
                result = diff

    print(result)

Submission status: Time Limit Exceeded

Solution code:
def cumulative_sum_list(l):
    cl = list()
    cs = 0
    for i in range(len(l)):
        cs += l[i]
        cl.append(cs)
    return cl

def cumsum(l, a, b):
    return l[b] - (0 if a == 0 else l[a-1])

if __name__ == '__main__':
    # read input
    n = int(input())
    l = list(map(int, input().split()))
    # create cumlative list first
    cl = cumulative_sum_list(l)
    total = cl[-1]
    clen = len(l)

    #  0  F(i)      i i+1 G(i)      len-1
    #  |------|------|-------|-------|
    #         c0    c1       c2
    #  <-----L------> <------R------->
    # pick up a c1 (i:i+1) and evaluate
    r = list()
    result = None
    for i in range(1,clen-2):
        #print("i={}\tL{}, R{}".format(i, l[0:i+1], l[i+1:]))

        # find C0 for each i
        c0 = None
        for c in range(i):
            B = cumsum(cl,0,c)
            C = cumsum(cl,c+1,i)
            diff = abs(B-C)
            if c0 is None:
                c0 = c
                mb = B
                mc = C
            else:
                if odiff > diff:
                    c0 = c
                    mb = B
                    mc = C
            odiff = diff
            #print("\t\tc0={}, [{}, {}] diff={}".format(c0, B, C, diff))

        # find C2 for each i
        c2 = None
        for c in range(i+1,clen-1):
            D = cumsum(cl, i+1, c)
            E = cumsum(cl, c+1, clen-1)
            diff = abs(E-D)
            if c2 is None:
                c2 = c
                md = D
                me = E
            else:
                if odiff > diff:
                    c2 = c
                    md = D
                    me = E
            odiff = diff
            #print("\t\tc2={}, [{}, {}] diff={}".format(c0, D, E, diff))

        # evaluate
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        if result is None:
            result = diff
        else:
            if result > diff:
                result = diff

    print(result)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(n) for n in input().split()]
anser_list = []
for i in range(1, N - 2):
    for j in range(i, N - 1):
        for k in range(j, N):
            divide_list = [sum(A[:i]), sum(A[i:j]), sum(A[j:k]), sum(A[k:])]
            anser_list.append(max(divide_list) - min(divide_list))
print(min(anser_list))

Submission status: Time Limit Exceeded

Solution code:
def cumulative_sum_list(l):
    cl = list()
    cs = 0
    for i in range(len(l)):
        cs += l[i]
        cl.append(cs)
    return cl

def cumsum(l, a, b):
    return l[b] - (0 if a == 0 else l[a-1])

def evaluate(cl, c0, c1, c2):
    b = cumsum(cl, 0, c0)
    c = cumsum(cl, c0+1, c1)
    d = cumsum(cl, c1+1, c2)
    e = cumsum(cl, c2+1, len(cl)-1)
    return (abs(max(b,c,d,e) - min(b,c,d,e)))

if __name__ == '__main__':
    # read input
    n = int(input())
    l = list(map(int, input().split()))
    # create cumlative list first
    cl = cumulative_sum_list(l)
    total = cl[-1]
    clen = len(l)

    #  0  F(i)      i i+1 G(i)      len-1
    #  |------|------|-------|-------|
    #         c0    c1       c2
    #  <-----L------> <------R------->
    # pick up a c1 (i:i+1) and evaluate
    f0 = dict()
    g0 = dict()
    for i in range(1,clen-2):
        #print("i={}\tL{}, R{}".format(i, l[0:i+1], l[i+1:]))
        # find C0 for each i
        best_c0 = None
        for c0 in range(i):
            B = cumsum(cl,0,c0)
            C = cumsum(cl,c0+1,i)
            diff = abs(B-C)
            if best_c0 is None:
                best_c0 = c0
            else:
                if odiff > diff:
                    best_c0 = c0
            odiff = diff
            #print("\t\tc0={}, [{}, {}] diff={}".format(c0, B, C, diff))
        f0[i] = best_c0

        # find C2 for each i
        best_c2 = None
        for c2 in range(i+1,clen-1):
            D = cumsum(cl, i+1, c2)
            E = cumsum(cl, c2+1, clen-1)
            diff = abs(E-D)
            if best_c2 is None:
                best_c2 = c2
            else:
                if odiff > diff:
                    best_c2 = c2
            odiff = diff
            #print("\t\tc2={}, [{}, {}] diff={}".format(c0, D, E, diff))
        g0[i] = best_c2

    #print('best C0:{} C2:{}'.format(f0, g0))

    r = list()
    for i in range(1,clen-2):
        #print("cut: {}/{}/{}".format(f0[i], i, g0[i]))
        #print("{} - {} - {} - {}".format(l[0:f0[i]+1], l[f0[i]+1:i+1], l[i+1:g0[i]+1], l[g0[i]+1:]))
        diff = evaluate(cl, f0[i], i, g0[i])
        r.append(diff)

    print(min(r))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
N=int(input())
t=[]
s=list(map(int,input().split()))
for i in range(2,N-1):
    p=10**9
    for j in range(1,len(s[:i])):
        a=sum(s[:i][:j])
        b=sum(s[:i][j:])
        q=abs(a-b)
        if p>q:
            p=q
            (x,y)=(a,b)
    p=10**9        
    for j in range(1,len(s[i:])):
        a=sum(s[i:][:j])
        b=sum(s[i:][j:])
        q=abs(a-b)
        if p>q:
            p=q
            (x1,y1)=(a,b)
    l=(x,y,x1,y1)
    t.append(max(l)-min(l))
print(min(t))

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

a_before = 1
c_before = 3
ans_tmp = []
for b in range(2,N-1):
        a_tmp = []
        if S[a_before] > S[b] - S[a_before]:
                a_tmp.append(a_before)
        else:
                for i in range(a_before,b):
                        if S[i] > S[b] - S[i]:
                                a_tmp.append(i)
                                a_tmp.append(i-1)
                                a_before = i-1
                                break
                else:
                        a_tmp.append(b-1)
                        a_before = b-1

        c_tmp = []
        if S[c_before] - S[b] > S[N] - S[c_before]:
                c_tmp.append(c_before)
        else:
                for i in range(c_before,N):
                        if S[i] - S[b] > S[N] - S[i]:
                                c_tmp.append(i)
                                c_tmp.append(i-1)
                                c_before = i-1
                                break
                else:
                        c_tmp.append(N-1)
                        c_before = N-1

        for a in a_tmp:
                for c in c_tmp:
                        ans_tmp.append(max(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])-min(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0]))

print(min(ans_tmp))

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

a_before = 1
c_before = 3
ans_tmp = []
for b in range(2,N-1):
        a_tmp = []
        if S[a_before] > S[b] - S[a_before]:
                a_tmp.append(a_before)
        else:
                for i in range(a_before,b):
                        if S[i] > S[b] - S[i]:
                                a_tmp.append(i)
                                a_tmp.append(i-1)
                                a_before = i-1
                                break
                else:
                        a_tmp.append(b-1)
                        a_before = b-1

        c_tmp = []
        if S[c_before] - S[b] > S[N] - S[c_before]:
                c_tmp.append(c_before)
        else:
                for i in range(b+1,N):
                        if S[i] - S[b] > S[N] - S[i]:
                                c_tmp.append(i)
                                c_tmp.append(i-1)
                                c_before = i-1
                                break
                else:
                        c_tmp.append(N-1)
                        c_before = N-1

        for a in a_tmp:
                for c in c_tmp:
                        ans_tmp.append(max(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])-min(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0]))

print(min(ans_tmp))

Submission status: Time Limit Exceeded

Solution code:
# 整数列A 
# 3箇所で切って、４つに
# それぞれの総和の最大値と最小値の差の絶対値の最小値

# 中央を固定することを考える(結局、その固定を全検索するが)
# 中央固定後、左側について、両方が同じくらいの値になるのが最適と考えて良いらしい

from itertools import accumulate

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

tmpP=tmpQ=tmpR=tmpS=0
P=Q=R=S=0
left = -1
ans=10e9

for mid in range(1,N-1):
	diffL=10e9
	diffR=10e9
	for l in range(mid):
		tmpP=SumA[l]
		tmpQ=SumA[mid] - SumA[l]
		if abs(tmpQ-tmpP) < diffL:
			diffL = abs(tmpQ-tmpP)
			left = l
			P=tmpP
			Q=tmpQ

	for r in range(mid+1,N-1):

		tmpR=SumA[r] - SumA[mid]
		tmpS=SumA[N-1] - SumA[mid] - tmpR
		if abs(tmpS-tmpR) < diffR:
			diffR = abs(tmpS-tmpR)
			right = r
			R=tmpR
			S=tmpS

	# print(P,Q,R,S)
	diff=max(P,Q,R,S)-min(P,Q,R,S)
	diff=abs(diff)
	ans = min(ans,diff)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate, islice
from bisect import bisect_left

n = int(input())
xs = [int(x) for x in input().split()]

ys = list(accumulate(xs))
zs, total = ys[:-1], ys[-1]

res = max(xs) - min(xs)
for i, z in islice(enumerate(zs), 1, n-1):
    j = bisect_left(zs, z//2, hi=i)
    splits = ((zs[j+k], z - zs[j+k]) for k in (-1, 0, 1) if 0 <= j+k <= i)
    a, b = min(splits, key=lambda s:abs(s[0]-s[1]))

    j = bisect_left(zs, (total - z)//2 + z, lo=i)
    splits = ((zs[j+k] - z, total - zs[j+k]) for k in (-1, 0, 1) if i <= j+k <= n-2)
    c, d = min(splits, key=lambda s:abs(s[0]-s[1]))

    minn, _, _, maxx = sorted((a,b,c,d))
    if maxx - minn < res:
        res = maxx - minn

print(res)