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: Accepted

Solution code:
# -*- coding: utf-8 -*-
def two_pointers(ary, l, r, split, ary_func, comb_func, comp_func):
    '''
    This function is supposed to be repeatedly called so that 'split' keeps
    renewing, under an assumption that 'split' increases monotonously.
    ('l' and 'r' just specify the region to be searched in 'ary')
    '''

    left = ary_func(ary, l, split)
    right = ary_func(ary, split, r)
    val = comb_func(left, right)

    for i in range(split + 1, r):
        tmp_left = ary_func(ary, l, i)
        tmp_right = ary_func(ary, i, r)
        tmp_val = comb_func(tmp_left, tmp_right)

        if comp_func(val, tmp_val):
            return i - 1, val, left, right
        else:
            left = tmp_left
            right = tmp_right
            val = tmp_val

    else:
        return r - 1, val, left, right


if __name__ == '__main__':
    from operator import add
    from itertools import accumulate

    n = int(input())
    a = [int(_) for _ in input().split()]
    cul_ary = [0] + list(accumulate(a, add))

    l_split = 1
    r_split = 3
    griefs = []
    for i in range(2, n - 1):
        # left
        l_split, l_diff, p, q = two_pointers(cul_ary,
                                             0,
                                             i,
                                             l_split,
                                             lambda ary, l, r: ary[r] - ary[l],
                                             lambda left, right: abs(left - right),
                                             lambda val1, val2: True if val1 < val2 else False)

        # right
        r_split, r_diff, r, s = two_pointers(cul_ary,
                                             i,
                                             n,
                                             r_split,
                                             lambda ary, l, r: ary[r] - ary[l],
                                             lambda left, right: abs(left - right),
                                             lambda val1, val2: True if val1 < val2 else False)

        griefs.append(max(p, q, r, s) - min(p, q, r, s))

    print(min(griefs))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def two_pointers(ary, l, r, split, ary_func, comb_func, comp_func):
    '''
    This function is supposed to be repeatedly called so that 'split' keeps
    renewing, under an assumption that 'split' increases monotonously.
    ('l' and 'r' just specify the region to be searched in 'ary')
    '''

    left = ary_func(ary, l, split)
    right = ary_func(ary, split, r)
    val = comb_func(left, right)

    for i in range(split + 1, r):
        tmp_left = ary_func(ary, l, i)
        tmp_right = ary_func(ary, i, r)
        tmp_val = comb_func(tmp_left, tmp_right)

        if comp_func(val, tmp_val):
            return i - 1, val, left, right
        else:
            left = tmp_left
            right = tmp_right
            val = tmp_val

    else:
        return r - 1, val, left, right


if __name__ == '__main__':
    '''
    an example of using this function
    At-Coder ABC 102 - D
    '''

    from operator import add
    from itertools import accumulate

    n = int(input())
    a = [int(_) for _ in input().split()]
    cul_ary = [0] + list(accumulate(a, add))

    l_split = 1
    r_split = 3
    griefs = []
    for i in range(2, n - 1):
        # left
        l_split, l_diff, p, q = two_pointers(cul_ary,
                                             0,
                                             i,
                                             l_split,
                                             lambda ary, l, r: ary[r] - ary[l],
                                             lambda left, right: abs(left - right),
                                             lambda val1, val2: True if val1 < val2 else False)

        # right
        r_split, r_diff, r, s = two_pointers(cul_ary,
                                             i,
                                             n,
                                             r_split,
                                             lambda ary, l, r: ary[r] - ary[l],
                                             lambda left, right: abs(left - right),
                                             lambda val1, val2: True if val1 < val2 else False)

        griefs.append(max(p, q, r, s) - min(p, q, r, s))

    print(min(griefs))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import accumulate


def two_pointers(ary, l, r, split, ary_func, comb_func, comp_func):

    left = ary_func(ary, l, split)
    right = ary_func(ary, split, r)
    val = comb_func(left, right)

    for i in range(split + 1, r):
        tmp_left = ary_func(ary, l, i)
        tmp_right = ary_func(ary, i, r)
        tmp_val = comb_func(tmp_left, tmp_right)

        if comp_func(val, tmp_val):
            return i - 1, val, left, right
        else:
            left = tmp_left
            right = tmp_right
            val = tmp_val

    else:
        return r - 1, val, left, right


if __name__ == '__main__':
    n = int(input())
    a = [int(_) for _ in input().split()]
    cul_ary = [0] + list(accumulate(a))

    l_split = 1
    r_split = 3
    griefs = []

    for i in range(2, n - 1):
        l_split, l_diff, p, q = two_pointers(
            cul_ary, 0, i, l_split, lambda ary, l, r: ary[r] - ary[l],
            lambda left, right: abs(left - right),
            lambda val1, val2: True if val1 < val2 else False)

        r_split, r_diff, r, s = two_pointers(
            cul_ary, i, n, r_split, lambda ary, l, r: ary[r] - ary[l],
            lambda left, right: abs(left - right),
            lambda val1, val2: True if val1 < val2 else False)

        griefs.append(max(p, q, r, s) - min(p, q, r, s))

    print(min(griefs))

Submission status: Accepted

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 = 1
c = 3
ans = S[N]
for b in range(2,N-1):
        while abs(S[b]-S[a]-S[a]) > abs(S[b]-S[a+1]-S[a+1]):
                a += 1
        while abs((S[N]-S[c]) - (S[c]-S[b])) > abs((S[N]-S[c+1]) - (S[c+1]-S[b])):
                c += 1
        ans = min(ans,(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(ans)

Submission status: Accepted

Solution code:
from itertools import *
input()
s=list(accumulate(map(int,input().split())))
l,r,t=0,2,s[-1];a=t
for m in s[1:-2]:
    while abs(t-2*s[r]+m)>abs(t-2*s[r+1]+m):r+=1
    while abs(m-2*s[l])>abs(m-2*s[l+1]):l+=1
    x=sorted([s[l],m-s[l],s[r]-m,t-s[r]])
    a=min(a,x[3]-x[0])
print(a)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
for i in range(1,n):
    a[i] += a[i-1]
l,r = 0,0
ans = float("inf")
# data = []
for c in range(1,n-2):
    while l < c-1:
        if 2 * a[l+1] > a[c]:
            if a[l+1] + a[l] < a[c]:
                l += 1
            break
        l += 1
    while r < n-2:
        if 2 * (a[r+1]-a[c]) > a[n-1] - a[c]:
            if a[r+1] + a[r] < a[n-1] + a[c]:
                r += 1
            break
        r += 1
    pqrs = [a[l],a[c]-a[l],a[r]-a[c],a[n-1]-a[r]]
    if ans > max(pqrs)-min(pqrs):
        ans = max(pqrs)-min(pqrs)
        # data = [l,c,r]
print(ans)
# print(data)

Submission status: Accepted

Solution code:
MAX = 10 ** 10
def m():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(1,n):
        a[i] += a[i-1]
    ans = MAX
    left_i = 0
    right_i = 2
    for mid in range(1,n-2):
        while left_i < mid and abs(a[left_i+1] - (a[mid]-a[left_i+1])) < abs(a[left_i] - (a[mid]-a[left_i])):
            left_i += 1

        if right_i <= mid:
            right_i = mid+1

        while right_i < n-1 and abs((a[right_i+1] - a[mid]) - (a[n-1] - a[right_i+1])) < abs((a[right_i] - a[mid]) - (a[n-1] - a[right_i])):
            right_i += 1
        p = a[left_i]
        q = a[mid] - a[left_i]
        r = a[right_i] - a[mid]
        s = a[n-1] - a[right_i]
        ans = min(ans, max(p,q,r,s) - min(p,q,r,s))
    return ans

print(m())

Submission status: Accepted

Solution code:
from bisect import bisect_right


def main():
    """
    4 <= N <= 2 * 10^5
    1 <= Ai <= 10^9
    """
    N = int(input())
    *A, = map(int, input().split())

    ans = f(N, A)
    # ans = TLE(N, A)

    print(ans)


def test_ans():
    NA_ans = [
        (5, [3, 2, 4, 1, 2], 2),
        (10, [10, 71, 84, 33, 6, 47, 23, 25, 52, 64], 36),
        (7, [1, 2, 3, 1000000000, 4, 5, 6], 999999994),
    ]

    for N, A, ans in NA_ans:
        assert TLE(N, A) == ans
        assert f(N, A) == ans


def f(N, A):
    ans = float("inf")
    S = A[::]
    for i in range(1, N):
        S[i] += S[i-1]

    for mid in range(2, N-1):
        # 均等
        x = S[mid-1] / 2
        left = bisect_right(S, x)
        if abs(S[left-1] - x) < abs(S[left] - x):
            left -= 1

        y = (S[-1] + S[mid-1]) / 2
        right = bisect_right(S, y)
        if abs(S[right-1] - y) < abs(S[right] - y):
            right -= 1

        p = S[left]
        q = S[mid-1] - S[left]
        r = S[right] - S[mid-1]
        s = S[-1] - S[right]
        sums = (p, q, r, s)
        ans = min(ans, max(sums) - min(sums))

    return ans


def TLE(N, A):
    ans = float("inf")
    for b in range(1, N-2):
        for c in range(b+1, N-1):
            for d in range(c+1, N):
                B = A[:b]
                C = A[b:c]
                D = A[c:d]
                E = A[d:]
                print(B, C, D, E)

                *sums, = map(sum, [B, C, D, E])
                x = abs(max(sums) - min(sums))
                ans = min(ans, x)

    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
input()
a=[int(i) for i in input().split()]
b=list(accumulate(a))
lp=0
rp=2
ans=float("INF")
for i in range(1,len(a)-2):
    while True:
        p=b[lp]
        q=b[i]-b[lp]
        r=b[rp]-b[i]
        s=b[len(a)-1]-b[rp]
        if abs(p-q)>abs(b[lp+1]-(b[i]-b[lp+1])) and lp+1!=i:
            lp+=1
        elif abs(r-s)>abs(b[rp+1]-b[i]-(b[len(a)-1]-b[rp+1])) and rp!=len(a)-1:
            rp+=1
        else:
            break
    ans=min(ans,abs(max(p,q,r,s)-min(p,q,r,s)))
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n = int(input())
a = list(map(int, input().split()))
b = list(accumulate(a))
ll, rr = 0, 2
ans = float("INF")

for i in range(1, n-2):
  while True:
    p = b[ll]
    q = b[i]-b[ll]
    r = b[rr]-b[i]
    s = b[n-1]-b[rr]
    lt = abs(p-q)
    rt = abs(r-s)
    if abs(b[ll+1]-(b[i]-b[ll+1]))<lt:
      ll+=1
    elif abs((b[rr+1]-b[i])-(b[n-1]-b[rr+1]))<rt:
      rr+=1
    else:
      break
  ans = min(ans, abs(max(p, q, r, s)-min(p, q, r, s)))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def two_pointers(ary, l, r, split, ary_func, comb_func, comp_func):
    left = ary_func(ary, l, split)
    right = ary_func(ary, split, r)
    val = comb_func(left, right)

    for i in range(split + 1, r):
        tmp_left = ary_func(ary, l, i)
        tmp_right = ary_func(ary, i, r)
        tmp_val = comb_func(tmp_left, tmp_right)

        if comp_func(val, tmp_val):
            return i - 1, val, left, right
        else:
            left = tmp_left
            right = tmp_right
            val = tmp_val

    else:
        return r - 1, val, left, right


if __name__ == '__main__':
    # At-Coder ABC 102 - D
    from operator import add, lt
    from itertools import accumulate

    n = int(input())
    a = [int(_) for _ in input().split()]
    cul_ary = [0] + list(accumulate(a, add))

    ary_func = lambda ary, l, r: ary[r] - ary[l]
    comb_func = lambda left, right: abs(left - right)
    comp_func = lt
    l_split = 1
    r_split = 3
    griefs = []
    for i in range(2, n - 1):
        # left
        l_split, l_diff, p, q = two_pointers(cul_ary, 0, i, l_split, ary_func,
                                             comb_func, comp_func)
        # right
        r_split, r_diff, r, s = two_pointers(cul_ary, i, n, r_split, ary_func,
                                             comb_func, comp_func)

        griefs.append(max(p, q, r, s) - min(p, q, r, s))

    print(min(griefs))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = [int(_) for _ in input().split()]

# my initial attempt below ############################
# from itertools import combinations
# INF = 10 ** 15
# combs = combinations(range(1, n), 3)
# grief = INF
# for comb in combs:
#     p = sum(a[:comb[0]])
#     q = sum(a[comb[0]:comb[1]])
#     r = sum(a[comb[1]:comb[2]])
#     s = sum(a[comb[2]:])

#     tmp = max(p, q, r, s) - min(p, q, r, s)
#     if tmp < grief:
#         grief = tmp

# print(grief)  # running time limit error

# solution below ######################################
cumul_sum = [0]
for i, ai in enumerate(a):
    cumul_sum.append(ai + cumul_sum[i])


def cal_sum(left, right):
    return cumul_sum[right] - cumul_sum[left]


def two_pointers(l, r, split):
    left_sum = cal_sum(l, split)
    right_sum = cal_sum(split, r)
    diff = abs(left_sum - right_sum)

    for i in range(split, r):
        tmp_left_sum = cal_sum(l, i)
        tmp_right_sum = cal_sum(i, r)
        tmp_diff = abs(tmp_left_sum - tmp_right_sum)

        if diff >= tmp_diff:
            left_sum = tmp_left_sum
            right_sum = tmp_right_sum
            diff = tmp_diff
        else:
            return i - 1, diff, left_sum, right_sum

    else:
        return r - 1, tmp_diff, tmp_left_sum, tmp_right_sum


l_split = 1
r_split = 3
griefs = []
for i in range(2, n - 1):
    # left
    l_split, l_diff, p, q = two_pointers(0, i, l_split)
    # right
    r_split, r_diff, r, s = two_pointers(i, n, r_split)

    griefs.append(max(p, q, r, s) - min(p, q, r, s))

print(min(griefs))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    # ans = 0
    ans = sys.maxsize

    S = [0] * (N+1)
    for i in range(0, N):
        S[i+1] = A[i] + S[i]
    
    lj = 1
    left_diffs = {}
    for i in range(2, N-1):
        left_diff = (sys.maxsize, 0, 0)
        for j in range(lj, i):
            a = S[j]-S[0]
            b = S[i]-S[j]
            # print(j, A[0:j], A[j:i], a, b, abs(a-b))
            if left_diff[0] > abs(a-b):
                left_diff = (abs(a-b), a, b)
            else:
                break
        lj = j-1 if j-1 > 0 else 1
        left_diffs[i] = left_diff

    right_diffs = {}
    rj = N-1
    for i in range(N-1-1, 2-1, -1):
        right_diff = (sys.maxsize, 0, 0)
        # for j in range(i+1, N):
        for j in range(rj, i, -1):
            c = S[j]-S[i]
            d = S[-1]-S[j]
            # print(j, A[i:j], A[j:], c, d, abs(c-d))
            if right_diff[0] > abs(c-d):
                right_diff = (abs(c-d), c, d)    
            else:
                break
        rj = j+1 if j+1 < N else N-1
        right_diffs[i] = right_diff
    
    for i in range(2, N-1): 
        _, a, b = left_diffs[i]
        _, c, d = right_diffs[i]
        # print(a, b, c, d)
        ans = min(ans, (max(a, b, c, d) - min(a, b, c, d)))
    return ans
     

def main():
    N = read_int()
    A = read_int_n() 

    # N = int(2.0e+5)
    # A = [random.randint(1, int(1e+9)) for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int, input().split())
S = [0]*(N+1)
for i in range(N):
    S[i+1] = S[i] + A[i]
INF = 10**30
ans = INF
def check(x, y, z):
    if 0 < y < x < z < N:
        B = (S[y], S[x]-S[y], S[z]-S[x], S[N]-S[z])
        return max(B)-min(B)
    return INF
y = z = 1
for x in range(2, N-1):
    s = S[x]
    while y < x and S[y+1]*2 <= s:
        y += 1
    t = S[N]-s
    while z < N and (S[z+1]-s)*2 <= t:
        z += 1
    for p in [0, 1]:
        for q in [0, 1]:
            ans = min(ans, check(x, y+p, z+q))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
for i in range(1,n): a[i]+=a[i-1]
l,r,ans = 1,3,float("inf")
for i in range(2,n-1):
	num,num2 = abs(2*a[l-1]-a[i-1]),abs(2*a[r-1]-a[i-1]-a[n-1])
	while num>abs(2*a[l]-a[i-1]) and l<i-1: l,num = l+1,abs(2*a[l]-a[i-1])
	while num2>abs(2*a[r]-a[i-1]-a[-1]) and r<n-1: r,num2 = r+1,abs(2*a[r]-a[i-1]-a[-1])
	ans = min(ans,max(a[l-1],a[i-1]-a[l-1],a[r-1]-a[i-1],a[-1]-a[r-1])-min(a[l-1],a[i-1]-a[l-1],a[r-1]-a[i-1],a[-1]-a[r-1]))
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

def Sdiff(s, m, e):
    # Sdiff(s, m, e) = [A_s, A_s+1 ..., A_m] [A_m+1 .... A_e]
    #    L = cl[m]-cl[s-1], R = cl[e] - cl[m]
    # diff(L,R) = abs(cl[m] - cl[s-1] - cl[e] + cl[m]) = abs(2*cl[m] - cl[s-1] - cl[e])

    x = 0 if s == 0 else cl[s-1]
    return abs(2*cl[m] - x - cl[e])

def partial(start, end, last):
    #print("partial: {}-{} last:{}".format(start,end, last))
    odiff = Sdiff(start, last, end)

    for c in range(last, end):
        diff = Sdiff(start, c, end)
        #print("partial loop: c:{}, diff:{} -> {}".format(c, odiff, diff))
        if odiff < diff:
            return c-1
        odiff = diff
    return c

if __name__ == '__main__':
    # read input
    N = int(input())
    l = list(map(int, input().split()))
    # create cumlative list first
    cl = list(accumulate(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 = 9 * 10e9
    c1 = 0
    c3 = 2
    for i in range(1, N-2):
        #print("LEFT:RIGHT {}/={}=/{}".format(l[0:i+1], i, l[i+1: N]))
        # LEFT
        c1 = partial(0, i, c1)
        # RIGHT
        c3 = partial(i+1, N-1, c3)

        # evaluate
        mb = cl[c1]
        mc = cl[i] - mb
        md = cl[c3] - cl[i]
        me = cl[N-1] - cl[c3]
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        #print("\t\t{}/{}/{}: [{} {} {} {}]".format(c1, i, c3, mb, mc, md, me))
        #print("\t\tdiff={}".format(diff))
        if diff < result:
            result = diff

    print(result)

Submission status: Accepted

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

cut_1=1
cut_2=2
cut_3=3
A_0=A[:cut_1]
S_0=sum(A_0)

A_1=A[cut_1:cut_2]
S_1=sum(A_1)

A_2=A[cut_2:cut_3]
S_2=sum(A_2)

A_3=A[cut_3:]
S_3=sum(A_3)


def irekae(S,T,i):
    if abs(S-T)>abs((S-A[i-1])-(T+A[i-1])):
        
        S=S-A[i-1]
        T=T+A[i-1]
        i=i-1
        
    elif abs(T-S)>abs((T-A[i])-(S+A[i])):
        #print(T,S,T-S,i)
        S=S+A[i]
        T=T-A[i]
        i=i+1
        #print(T,S,T-S,i)

    return (S,T,i)

MIN=[]
cut_1b=0
cut_3b=0
for cut_2 in range(2,N-1):
    cut_1b=0
    cut_3b=0
    while cut_1b != cut_1:
        cut_1b=cut_1
        S_0,S_1,cut_1=irekae(S_0,S_1,cut_1)
        #print(cut_1)

    while cut_3b != cut_3:
        cut_3b=cut_3
        S_2,S_3,cut_3=irekae(S_2,S_3,cut_3)

    MIN+=[max([S_0,S_1,S_2,S_3])-min([S_0,S_1,S_2,S_3])]
    #print(cut_1,cut_2,cut_3,S_0,S_1,S_2,S_3)

    S_1+=A[cut_2]
    S_2-=A[cut_2]

print(min(MIN))

Submission status: Accepted

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
ans=10e9
l = 0
r = 2

# midとmid+1の間が中間の切断
for mid in range(1,N-2):

	# l,rは、単調増加であるため、全ての中間点を求めるループの間、クリアの必要がないらしい

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while l < mid and abs((SumA[mid] - SumA[l+1])-SumA[l+1]) < abs((SumA[mid] - SumA[l])-SumA[l]):
		l += 1

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while r < N-1 and abs((SumA[N-1]-SumA[r+1])-(SumA[r+1]-SumA[mid])) < abs((SumA[N-1] - SumA[r])-(SumA[r] - SumA[mid])):
		r += 1

	#print("{},{}".format(mid,l))

	P=SumA[l]
	Q=SumA[mid]-SumA[l]
	R=SumA[r]-SumA[mid]
	S=SumA[N-1]-SumA[r]

	#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: Accepted

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
ans=10e9
l = 0
r = 2

# midとmid+1の間が中間の切断
for mid in range(1,N-2):

	# l,rは、単調増加であるため、全ての中間点を求めるループの間、クリアの必要がないらしい

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while l < mid and abs(SumA[l+1]-(SumA[mid] - SumA[l+1])) < abs(SumA[l]-(SumA[mid] - SumA[l])):
		l += 1

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while r <= mid or (r < N and abs((SumA[r+1]-SumA[mid]) - (SumA[N-1]-SumA[r+1])) < abs((SumA[r] - SumA[mid]) - (SumA[N-1] - SumA[r]))):
		r += 1

	#print("{},{}".format(mid,l))

	P=SumA[l]
	Q=SumA[mid]-SumA[l]
	R=SumA[r]-SumA[mid]
	S=SumA[N-1]-SumA[r]

	#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: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = [int(_) for _ in input().split()]

# my initial trial below ##############################
# from itertools import combinations
# INF = 10 ** 15
# combs = combinations(range(1, n), 3)
# grief = INF
# for comb in combs:
#     p = sum(a[:comb[0]])
#     q = sum(a[comb[0]:comb[1]])
#     r = sum(a[comb[1]:comb[2]])
#     s = sum(a[comb[2]:])

#     tmp = max(p, q, r, s) - min(p, q, r, s)
#     if tmp < grief:
#         grief = tmp

# print(grief)  # running time limit error

# solution below ######################################
INF = 10**15
cumul_sum = [0]
for i, ai in enumerate(a):
    cumul_sum.append(ai + cumul_sum[i])


def cal_sum(left, right):
    return cumul_sum[right] - cumul_sum[left]


def two_pointers(l, r, split, diff):
    left_sum = cal_sum(l, split)
    right_sum = cal_sum(split, r)
    diff = abs(left_sum - right_sum)

    for i in range(split, r):
        tmp_left_sum = cal_sum(l, i)
        tmp_right_sum = cal_sum(i, r)
        tmp_diff = abs(tmp_left_sum - tmp_right_sum)

        if diff >= tmp_diff:
            left_sum = tmp_left_sum
            right_sum = tmp_right_sum
            diff = tmp_diff
        else:
            return i - 1, diff, left_sum, right_sum
    else:
        return r - 1, tmp_diff, tmp_left_sum, tmp_right_sum


l_split = 1
r_split = 3
griefs = []
for i in range(2, n - 1):
    # left
    l_split, l_diff, p, q = two_pointers(0, i, l_split, INF)
    # right
    r_split, r_diff, r, s = two_pointers(i, n, r_split, INF)
    griefs.append(max(p, q, r, s) - min(p, q, r, s))

print(min(griefs))

Submission status: Accepted

Solution code:
from itertools import accumulate
N=int(input())
s=list(accumulate(map(int,input().split())))
def f(N,s):
    ans=s[-1]
    p=0
    q=2
    for i in range(2,N-1):
        while abs(s[i-1]-2*s[p])>abs(s[i-1]-2*s[p+1]):
            p+=1
        while abs(s[q]*2-s[i-1]-s[-1])>abs(s[q+1]*2-s[i-1]-s[-1]):
            q+=1
        t=[s[i-1]-s[p],s[p],s[q]-s[i-1],s[-1]-s[q]]
        ans=min(ans,max(t)-min(t))
    print(ans)
    return 
f(N,s)

Submission status: Accepted

Solution code:
from itertools import accumulate
N=int(input())
s=list(accumulate(map(int,input().split())))
ans=s[-1]
p=0
q=2
for i in range(2,N-1):
    while abs(s[i-1]-2*s[p])>abs(s[i-1]-2*s[p+1]):
        p+=1
    while abs(s[q]*2-s[i-1]-s[-1])>abs(s[q+1]*2-s[i-1]-s[-1]):
        q+=1
    t=[s[i-1]-s[p],s[p],s[q]-s[i-1],s[-1]-s[q]]
    ans=min(ans,max(t)-min(t))
print(ans)

Submission status: Accepted

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 = 1
c = 3
ans = S[N]

for b in range(2,N-1):
        while abs(S[b]-S[a]-S[a]) > abs(S[b]-S[a+1]-S[a+1]):
                a += 1

        while abs((S[N]-S[c]) - (S[c]-S[b])) > abs((S[N]-S[c+1]) - (S[c+1]-S[b])):
                c += 1

        ans = min(ans,(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(ans)

Submission status: Accepted

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 = 1
c = 3
ans_tmp = []
for b in range(2,N-1):
        while abs(S[b]-S[a]-S[a]) > abs(S[b]-S[a+1]-S[a+1]):
                a += 1

        while abs((S[N]-S[c]) - (S[c]-S[b])) > abs((S[N]-S[c+1]) - (S[c+1]-S[b])):
                c += 1

        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: Accepted

Solution code:
from itertools import accumulate
N=int(input())
s=list(accumulate(map(int,input().split())))
ans=10**9
p=0
q=2
for i in range(2,N-1):
    while p<i-1 and abs(s[i-1]-2*s[p+1])<abs(s[i-1]-2*s[p]):
        p+=1
    if q<i:
        q+=1
    while q<N and abs(s[i-1]-2*s[q+1]+s[-1])<abs(s[i-1]-2*s[q]+s[-1]):   
        q+=1
    t=[s[q]-s[i-1],s[-1]-s[q],s[p],s[i-1]-s[p]]
    w=max(t)-min(t)
    ans=min(ans,w) 
print(ans)

Submission status: Accepted

Solution code:
import statistics
import math

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


ureshimi = []
k = 0
l = 2

B = 0
C = 0
D = 0
E = 0

sumBC = sum(A[0:2])
sumDE = sum(A) - sumBC

for i in range(2, N - 1):
    for j in range(k, i):
        if j == i - 1:
            k = j
            C = sumBC - B
            break
        elif B + A[j] >= sumBC / 2:
            if sumBC / 2 - B  > A[j] / 2:
                B += A[j]
                k = j + 1
                C = sumBC - B
                break
            else:
                k = j
                C = sumBC - B
                break
        B += A[j]
    for j in range(l, N):
        if j == N - 1:
            l = j
            E = sumDE - D
            break
        elif D + A[j] >= sumDE / 2:
            if sumDE / 2 - D > A[j] / 2:
                D += A[j]
                l = j + 1
                E = sumDE - D
                break
            else:
                l = j
                E = sumDE - D
                break
        D += A[j]
    ureshimi.append(max([B, C, D, E]) - min([B, C, D, E]))
    sumBC += A[i]
    sumDE -= A[i]
    D -= A[i]
        

print(min(ureshimi))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = [int(_) for _ in input().split()]

# my initial trial below ##############################
# from itertools import combinations
# combs = combinations(range(1, n), 3)
# grief = 10**10
# for comb in combs:
#     p = sum(a[:comb[0]])
#     q = sum(a[comb[0]:comb[1]])
#     r = sum(a[comb[1]:comb[2]])
#     s = sum(a[comb[2]:])

#     tmp = max(p, q, r, s) - min(p, q, r, s)
#     if tmp < grief:
#         grief = tmp

# print(grief)  # running time limit error

# solution below ######################################

cumul_sum = [0]
for i, ai in enumerate(a):
    cumul_sum.append(ai + cumul_sum[i])


def cal_sum(left, right):
    return cumul_sum[right] - cumul_sum[left]


def two_pointers(l, r, split, diff):
    for i in range(split, r):
        tmp_diff = abs(cal_sum(l, i) - cal_sum(i, r))
        if diff >= tmp_diff:
            diff = tmp_diff
        else:
            return i - 1, diff
    else:
        return r - 1, diff


l_split = 1
r_split = 3
griefs = []
for i in range(2, n - 1):
    # left
    l_split, l_diff = two_pointers(0, i, l_split, 10**12)
    # right
    r_split, r_diff = two_pointers(i, n, r_split, 10**12)

    p, q, r, s = cal_sum(0, l_split), cal_sum(l_split,
                                              i), cal_sum(i, r_split), cal_sum(
                                                  r_split, n)
    griefs.append(max(p, q, r, s) - min(p, q, r, s))


print(min(griefs))

Submission status: Accepted

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

# The 'acc' stands for accumulation.
acc = []
acc.append(a[0])
for i in range(n - 1):
    acc.append(acc[i] + a[i + 1])

# b: border, s: sum
s = [0, 0, 0, 0]
b0 = 0
b2 = 2
score = []
for b1 in range(1, n - 2):
    for i in range(b1 - b0 - 1):
        b0 = b0 + 1
        if (abs(acc[b1] - acc[b0] * 2) > abs(acc[b1] - acc[b0 - 1] * 2)):
            b0 = b0 - 1
            break
    s[0] = acc[b0]
    s[1] = acc[b1] - acc[b0]

    for i in range(n - b2 - 2):
        b2 = b2 + 1
        if (abs(acc[n - 1] - acc[b2] * 2 + acc[b1]) > abs(acc[n - 1] - acc[b2 - 1] * 2 + acc[b1])):
            b2 = b2 - 1
            break
    s[2] = acc[b2] - acc[b1]
    s[3] = acc[n - 1] - acc[b2]

    score.append(max(s) - min(s))

print(min(score))