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:
N = int(input())
A = list(map(int, input().split()))
S = [0]

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

res = 10**18

for i in range(2, N - 1):
    hi = i
    lo = 0
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if S[mid] - S[0] >= S[i] - S[mid]:
            hi = mid
        else:
            lo = mid
    p = S[hi] - S[0]
    q = S[i] - S[hi]
    if p - q > abs((p - A[hi - 1]) - (q + A[hi - 1])):
        p -= A[hi - 1]
        q += A[hi - 1]

    hi = N
    lo = i
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if S[mid] - S[i] >= S[N] - S[mid]:
            hi = mid
        else:
            lo = mid
    s = S[hi] - S[i]
    t = S[N] - S[hi]
    if s - t > abs((s - A[hi - 1]) - (t + A[hi - 1])):
        s -= A[hi - 1]
        t += A[hi - 1]

    res = min(res, max(p, q, s, t) - min(p, q, s, t))

print(res)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
A = getList()
fore = copy.deepcopy(A)
back = copy.deepcopy(A)

for i in range(N - 1):
    fore[i + 1] += fore[i]
    back[N - i - 2] += back[N - i - 1]

left = 0
total = A[0]

fore_list = []
for right in range(1, N - 2):
    while abs((fore[right] / 2) - (total + A[left + 1])) < abs((fore[right] / 2) - total):
        left += 1
        total += A[left]
    fore_list.append([right, total, fore[right] - total])

right = N - 1
total = A[-1]

back_list = []
for left in range(N - 2, 1, -1):
    while abs((back[left] / 2) - (total + A[right - 1])) < abs((back[left] / 2) - total):
        right -= 1
        total += A[right]
    back_list.append([left, total, back[left] - total])
back_list.sort()

ans = float('inf')
for i in range(len(back_list)):
    ind1, a, b = fore_list[i]
    ind2, c, d = back_list[i]
    opt = max(a, b, c, d) - min(a, b, c, d)
    ans = min(ans, opt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
def solve(n, a):
    b, c, d, e = a[0], a[1], a[2], sum(a[3:])
    bc = b + c
    de = d + e
    bci = 1
    dei = 3
    ans = max(b, c, d, e) - min(b, c, d, e)
    for i in range(2, n - 1):
        while i - bci > 1 and (min(b, c) < min(b + a[bci], c - a[bci])):
            b += a[bci]
            c -= a[bci]
            bci += 1
        while dei < n - 1 and (max(d, e) > max(d + a[dei], e - a[dei])):
            d += a[dei]
            e -= a[dei]
            dei += 1
        ans = min(ans, max(b, c, d, e) - min(b, c, d, e))
        bc += a[i]
        de -= a[i]
        c += a[i]
        d -= a[i]
        if i + 1 >= dei:
            d += a[dei]
            e -= a[dei]
            dei += 1
    return ans

print(min(solve(n, a), solve(n, list(a))))

Submission status: Accepted

Solution code:
# D - Equal Cut
import bisect

N = int(input())
A = list(int(a) for a in input().split())

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

ans = 10**18
for i in range(2, N-1):
    B = bisect.bisect_left(Acum, Acum[i]//2) - 1
    if abs(Acum[B] * 2 - Acum[i]) > abs(Acum[B+1] * 2 - Acum[i]):
        B += 1
    if B == i:
        B -= 1
    elif B == 0:
        B += 1
    P = Acum[B]
    Q = Acum[i] - Acum[B]
    D = bisect.bisect_left(Acum, Acum[i] + (Acum[-1]-Acum[i])//2) - 1
    if abs(Acum[D] * 2 - Acum[i] - Acum[-1]) > abs(Acum[D+1] * 2 - Acum[i] - Acum[-1]):
        D += 1
    if D == N:
        D -= 1
    elif D == i:
        D += 1
    R = Acum[D] - Acum[i]
    S = Acum[-1] - Acum[D]
    mi = min(P, Q, R, S)
    ma = max(P, Q, R, S)
    ans = min(ans, abs(ma - mi))
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
n = int(input())
a = [int(x) for x in input().split()]

cum = [0]
for x in a:
  cum.append(cum[-1]+x)

ans = 10**30
for z in range(4):
  for i in range(2,n-1):
    b = cum[bisect_right(cum, cum[i]//2)-1+(z&1)]
    c = cum[i]-b
    d = cum[bisect_right(cum, (cum[n]-cum[i])//2+cum[i])-1+(z>>1&1)] - cum[i]
    e = cum[n] - (b+c+d)
    ans = min(ans, max(b,c,d,e) - min(b,c,d,e))
  
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
n = int(input())
a = [int(x) for x in input().split()]

cum = [0]
for x in a:
  cum.append(cum[-1]+x)

ans = 10**30
for i in range(2,n-1):
  for z in range(4):
    b = cum[bisect_right(cum, cum[i]//2)-1+(z&1)]
    c = cum[i]-b
    d = cum[bisect_right(cum, (cum[n]-cum[i])//2+cum[i])-1+(z>>1&1)] - cum[i]
    e = cum[n] - (b+c+d)
    ans = min(ans, max(b,c,d,e) - min(b,c,d,e))
  
print(ans)

Submission status: Accepted

Solution code:
import bisect

n=int(input())
arr=list(map(int,input().split()))
acum=[0]
for i in range(n):
  acum.append(acum[-1]+arr[i])
ans=10**18
for i in range(2,n-1):
  suma=acum[i]
  sumb=acum[n]-suma
  posa=bisect.bisect_right(acum,suma//2)
  diffa=10**18
  if posa>=2:
    mina=min(acum[posa-1],acum[i]-acum[posa-1])
    maxa=max(acum[posa-1],acum[i]-acum[posa-1])
    diffa=maxa-mina
  if posa!=i:
    tmina=min(acum[posa],acum[i]-acum[posa])
    tmaxa=max(acum[posa],acum[i]-acum[posa])
    tdiffa=tmaxa-tmina
    if tdiffa<diffa:
      diffa=tdiffa
      mina=tmina
      maxa=tmaxa
  posb=bisect.bisect_right(acum,suma+sumb//2)
  diffb=10**18
  if posb>=i+2:
    minb=min(acum[posb-1]-acum[i],acum[n]-acum[posb-1])
    maxb=max(acum[posb-1]-acum[i],acum[n]-acum[posb-1])
    diffb=maxb-minb
  if posa!=n+1:
    tminb=min(acum[posb]-acum[i],acum[n]-acum[posb])
    tmaxb=max(acum[posb]-acum[i],acum[n]-acum[posb])
    tdiffb=tmaxb-tminb
    if tdiffb<diffb:
      diffb=tdiffb
      minb=tminb
      maxb=tmaxb
  ans=min(ans,max(maxa,maxb)-min(mina,minb))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
tmp=0
ca=[0]
for ai in a:
  tmp+=ai
  ca.append(tmp)
from bisect import bisect_right,bisect_left
ans=float('inf')

# 数列をまず半分に区切る。左i個と右n-i個 2<=i,n-i
f,g=1,3
for i in range(2,n-1):
  while abs(ca[i]-ca[f]-ca[f])>abs(ca[i]-ca[f+1]-ca[f+1]):
    f+=1
  while abs((ca[-1]-ca[g])-(ca[g]-ca[i]))>abs((ca[-1]-ca[g+1])-(ca[g+1]-ca[i])):
    g+=1
  l=(ca[f],ca[i]-ca[f],ca[-1]-ca[g],ca[g]-ca[i])
  ans=min(ans,max(l)-min(l))
  #print(l)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    """
    まず２分して左右をさらにそれぞれ２分するときこれらはなるべく差が小さい方がよさそう
    """
    # m = 1で切った時で初期化
    s = sum(A[2:])
    partial_s = 0
    init_r = N - 2
    for r in range(2, N - 1):
        partial_s += A[r]
        if partial_s * 2 > s:
            init_r = r
            break
    l = 0
    r = init_r
    sums = [A[0], A[1], partial_s, s - partial_s]
    ans = max(sums) - min(sums)
    temp = [sums[0], sums[1], sums[2] - A[r], sums[3] + A[r]]
    ans = min(ans, max(temp) - min(temp))
    #print("l={}, m=1, r={}, sums={}, ans={}".format(l, r, sums, ans))


    # m >= 2で動かしたとき
    for m in range(2, N - 2):
        # lの移動
        sums[1] += A[m]
        while sums[0] <= sums[1] and l < m - 1:
            l += 1
            sums[0] += A[l]
            sums[1] -= A[l]
        # rの移動
        sums[2] -= A[m]
        while sums[2] <= sums[3] and r < N - 2:
            r += 1
            sums[2] += A[r]
            sums[3] -= A[r]
        # ansの更新
        ans = min(ans, max(sums) - min(sums))
        temp = [sums[0] - A[l], sums[1] + A[l], sums[2], sums[3]]
        ans = min(ans, max(temp) - min(temp))
        temp = [sums[0], sums[1], sums[2] - A[r], sums[3] + A[r]]
        ans = min(ans, max(temp) - min(temp))
        temp = [sums[0] - A[l], sums[1] + A[l], sums[2] - A[r], sums[3] + A[r]]
        ans = min(ans, max(temp) - min(temp))
        #print("l={}, m={}, r={}, sums={}, ans={}".format(l, m, r, sums, ans))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
accuml=[0]*n
accumr=[0]*n
accuml[0]=a[0]
accumr[0]=a[n-1]
for i in range(n-1):
    accuml[i+1]+=a[i+1]+accuml[i]
    accumr[i+1]+=a[n-i-2]+accumr[i]
ll=0
rr=n-3
ans=10**18
for i in range(1,n-2):
    sl=accuml[i]
    sr=accumr[n-2-i]
    while abs(accuml[ll+1]-sl/2)<abs(accuml[ll]-sl/2):
        ll+=1
    while abs(accumr[rr-1]-sr/2)<abs(accumr[rr]-sr/2):
        rr-=1
    maxi=max(sl-accuml[ll],accuml[ll],sr-accumr[rr],accumr[rr])
    mini=min(sl-accuml[ll],accuml[ll],sr-accumr[rr],accumr[rr])
    ans=min(ans,maxi-mini)
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import accumulate
    n = int(readline())
    a = list(map(int, readline().split()))
    cum = list(accumulate(a))

    left_lim = 1
    right_lim = n - 2
    first = 0
    second = 1
    third = 2
    ans = INF

    for second in range(left_lim, right_lim + 1):
        if third == second:
            third += 1

        p = cum[first]
        q = cum[second] - cum[first]
        r = cum[third] - cum[second]
        s = cum[n - 1] - cum[third]

        while first < second:
            if abs(p - q) > abs((p + a[first + 1]) - (q - a[first + 1])):
                first += 1
                p += a[first]
                q -= a[first]
            else:
                break

        while third < n - 1:
            if abs(r - s) > abs((r + a[third + 1]) - (s - a[third + 1])):
                third += 1
                r += a[third]
                s -= a[third]
            else:
                break

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
#import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect

n=int(input())
a=list(map(int,input().split()))
r=[0]*(n+1)
s=sum(a)
q=0
s=2
ans=10**9
for i in range(n):
    r[i+1]=r[i]+a[i]
for l in range(2,n-1):
    for i in range(q,l):
        if a[i]>r[l]-2*r[i]:
            q=i
            break
    for i in range(s,n):
        if a[i]>(r[-1]-r[l])-2*(r[i]-r[l]):
            s=i
            break
    M=max(r[q],r[l]-r[q],r[-1]-r[l]-(r[-1]-r[s]),r[-1]-r[s])
    m=min(r[q],r[l]-r[q],r[-1]-r[l]-(r[-1]-r[s]),r[-1]-r[s])
   
    ans=min(ans,(M-m))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
from itertools import accumulate
P = list(accumulate(A))
l,right = 0,2
diff = float('inf')
for c in range(1,N-1):
    p = P[l]
    q = P[c]-P[l]
    while True:
        if abs(p+2*A[l+1]-q)>=abs(p-q):
            break
        p = P[l+1]
        q = P[c]-P[l+1]
        l += 1
    r = P[right]-P[c]
    s = P[-1]-P[right]
    while True:
        if abs(r+2*A[right+1]-s)>=abs(r-s):
            break
        r = P[right+1]-P[c]
        s = P[-1]-P[right+1]
        right += 1
    diff = min(diff,max(p,q,r,s)-min(p,q,r,s))
print(diff)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]"):
    s = sum(A)
    cums = [0]
    for v in A:
        cums.append(cums[-1] + v)

    ret = float('inf')
    i, j, k = 1, 2, 3
    while j < N - 1:
        lm = cums[j]
        while i < j - 1 and cums[i] < lm // 2:
            i += 1
        if i > 2 and abs(lm - 2 * cums[i]) > abs(lm - 2 * cums[i - 1]):
            i -= 1

        rm = cums[N] - cums[j]
        while k < N - 1 and cums[k] - cums[j] < rm // 2:
            k += 1
        if k > j + 1 and abs(rm - 2 * (cums[k] - cums[j])) > abs(rm - 2 * (cums[k - 1] - cums[j])):
            k -= 1

        a, b, c, d = cums[i], cums[j] - cums[i], cums[k] - cums[j], cums[N] - cums[k]
        tmp = max(a, b, c, d) - min(a, b, c, d)
        #print(tmp, i, j, k, ':', a, b, c, d, '\n')
        ret = min(ret, tmp)
        j += 1
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
Acum = list(accumulate(A))
slice1 = 0; slice3 = 2
answer = 10 ** 15
for i in range(1, N-2):
    # iが2つめの部分列の右端のindex
    slice2 = i
    if slice3 <= slice2:
        slice3 = slice2 + 1
    p = Acum[slice1]; q = Acum[slice2] - p
    r = Acum[slice3] - Acum[slice2]; s = Acum[-1] - Acum[slice3]
    while slice1 < i-1:
        p2 = Acum[slice1+1]
        q2 = Acum[slice2] - p2
        if abs(p2-q2) < abs(p-q):
            slice1 += 1
            p = p2; q = q2
        else:
            break
    while slice3 < N-2:
        r2 = Acum[slice3+1] - Acum[slice2]
        s2 = Acum[-1] - Acum[slice3+1]
        if abs(r2-s2) < abs(r-s):
            slice3 += 1
            r = r2; s = s2
        else:
            break
    ma = max(p, q, r, s); mi = min(p, q, r, s)
    temp = ma - mi
    if temp < answer:
        answer = temp
    
print(answer)
# 47

Submission status: Accepted

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

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

mindiff = CA[-1]
left = 0
right = 2
for c in range(1,N-1):
    # left side
    p = CA[left]
    q = CA[c] - CA[left]
    while True:
        pi = CA[left+1]
        qi = CA[c] - CA[left+1]
        if abs(pi- qi) >= abs(p - q):
            break
        p = pi; q = qi
        left += 1

    # right side
    r = CA[right] - CA[c]
    s = CA[-1] - CA[right]
    while True:
        ri = CA[right+1] - CA[c]
        si = CA[-1] - CA[right+1]
        if abs(ri- si) >= abs(r - s):
            break
        r = ri; s = si
        right += 1

    mindiff = min(mindiff, max(p, q, r, s) - min(p, q, r, s))
print(mindiff)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    X = [0 for _ in range(N + 1)]  # cum sum
    for i in range(N):
        X[i + 1] = X[i] + A[i]
    # split to 2 parts (X_0, ..., X_i), (X_(i+1), ..., X_N)
    ans = 10**10
    left = 0
    right = 2
    for i in range(1, N):
        while left < i:
            d = abs(X[left] - (X[i] - X[left]))
            d_next = abs(X[left + 1] - (X[i] - X[left + 1]))
            if d_next > d:
                break
            left += 1
        while right < N:
            d = abs((X[N] - X[right]) - (X[right] - X[i]))
            d_next = abs((X[N] - X[right + 1]) - (X[right + 1] - X[i]))
            if d_next > d:
                break
            right += 1
        p, q, r, s = X[left], X[i] - X[left], X[right] - X[i], X[N] - X[right]
        ans = min([ans, max([p, q, r, s]) - min([p, q, r, s])])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
n = int(input())
A = [int(i) for i in input().split()]
A_sum = [0]+list(itertools.accumulate(A))
"""累積和は単調増加
4パートに分ければいいので別ける箇所3点left,mid,rightを探す．
全探索はTLEなのでmidに関するループ探索を行うと，条件式からl,rは決まる．
今回の問題では差をなくすことが目的なので，0~l,l~iとi~r,r~nの差が小さい時がベスト
この条件のもと，lとrを決める．for文で書く場合break入れないとTLE

"""
ans = 10**9
P,Q,R,S = 0,0,0,0
l = 0
r = 2
for i in range(1,n):
    while(l<i and abs(A_sum[l]-(A_sum[i]-A_sum[l])) >= abs(A_sum[l+1]-(A_sum[i]-A_sum[l+1]))):
        #単調増加だから超えるような時はp,qの差が大きくなる時だよね
        l += 1
    while(r<n and abs((A_sum[n]-A_sum[r]) -(A_sum[r]-A_sum[i])) >= abs((A_sum[n]-A_sum[r+1])-(A_sum[r+1]-A_sum[i]))):
        r += 1
    P = A_sum[l]
    Q = A_sum[i]-P
    R = A_sum[r]-A_sum[i]
    S = A_sum[n]-A_sum[r]
    ans =min(ans,abs(max(P,Q,R,S)-min(P,Q,R,S)))
    

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a_list = [int(x) for x in input().split()]

temp_list = [0] * (n + 1)
for i in range(1, n + 1):
    temp_list[i] = a_list[i - 1] + temp_list[i - 1]
 
l = 1
r = 3
ans = temp_list[-1]
for m in range(2, n - 1):
    gap_min = abs((temp_list[m] - temp_list[l]) - (temp_list[l] - temp_list[0]))
    while l < m:
        l += 1
        gap = abs((temp_list[m] - temp_list[l]) - (temp_list[l] - temp_list[0]))
        if gap < gap_min:
            gap_min = gap
        else:
            l -= 1
            break
    else:
        l -= 1
    
    gap_min = abs((temp_list[n] - temp_list[r]) - (temp_list[r] - temp_list[m]))
    while r < n:
        r += 1
        gap = abs((temp_list[n] - temp_list[r]) - (temp_list[r] - temp_list[m]))
        if gap < gap_min:
            gap_min = gap
        else:
            r -= 1
            break
    else:
        r -= 1
    
    num_list = sorted([temp_list[l] - temp_list[0], temp_list[m] - temp_list[l], temp_list[r] - temp_list[m], temp_list[n] - temp_list[r]])
    ans_temp = num_list[3] - num_list[0]
    if ans_temp < ans:
        ans = ans_temp
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

print(ans)

Submission status: Accepted

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

def main():
    N = int(input())
    A = list(map(int,input().split()))
    cumsum = list(accumulate([0] + A))
    ans = INF
    l = 0
    r = 2
    fl = lambda i,l:abs(cumsum[i + 1] - 2*cumsum[l + 1])
    fr = lambda i,r:abs(cumsum[-1] - cumsum[i + 1] - 2*(cumsum[r + 1] - cumsum[i + 1]))

    for i in range(1,N - 2):
        while fl(i,l + 1) < fl(i,l):
            l += 1
        while fr(i,r + 1) < fr(i,r):
            r += 1
        a = cumsum[l + 1]
        b = cumsum[i + 1] - a
        c = cumsum[r + 1] - a - b
        d = cumsum[-1] - a - b - c
        ans = min(ans,max(a,b,c,d) - min(a,b,c,d))
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import *
n = int(input())
a = list(map(int, input().split()))

a = [0]+list(accumulate(a))
#print(a)
ans = 10**18
for i in range(2, n):
    b = []
    m = a[i]
    l = bisect_right(a, m/2)
    if abs(a[l]-m/2) <= abs(a[l-1]-m/2):
        b.append(a[l])
        b.append(m-a[l])
    else:
        b.append(a[l-1])
        b.append(m-a[l-1])
    r = bisect_left(a, (a[-1]+m)/2)
    if abs(a[r]-(a[-1]+m)/2) <= abs(a[r-1]-(a[-1]+m)/2):
        b.append(a[r]-m)
        b.append(a[-1]-a[r])
    else:
        b.append(a[r-1]-m)
        b.append(a[-1]-a[r-1])

    #print(b)
    ans = min(ans, max(b)-min(b))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
S=[0] #累積和
cnt=0
for i in range(n):
    cnt+=A[i]
    S.append(cnt)

ans=S[n]
d1=1 #しきり1(i個目の右で切る)
d3=2 #しきり3

for d2 in range(2,n-1): #しきり2を全探索
    L=S[d2]
    R=S[n]-S[d2]
    for i in range(d1,d2): #しきり1を右に動かす
        if S[i]>=L/2:
            break
    if abs(S[i]-L/2)>=abs(S[i-1]-L/2): #しきり1を更新
        d1=i-1
    else:
        d1=i
    for i in range(d3,n): #しきり3を右に動かす
        if S[i]-S[d2]>=R/2:
            break
    if abs(S[i]-S[d2]-R/2)>=abs(S[i-1]-S[d2]-R/2): #しきり3を更新
        d3=i-1
    else:
        d3=i
    s=[S[d1],S[d2]-S[d1],S[d3]-S[d2],S[n]-S[d3]] #4分割の結果
    ans=min(max(s)-min(s),ans) #解答の更新
    #print(d1,d2,d3,s)
print(ans)

Submission status: Accepted

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

cum = [0]
for ai in a:
    cum.append(cum[-1] + ai)

ans = float('inf')

for i in range(2, n-1):
    bc = cum[i]
    de = cum[-1] - cum[i]
    bc_mid = bc / 2
    de_mid = (cum[i] + cum[-1]) / 2

    i_bc = bisect.bisect_left(cum, bc_mid)
    i_de = bisect.bisect_left(cum, de_mid)

    # print(i_bc)
    # print(i_de)

    for cum_b in (cum[i_bc-1], cum[i_bc]):
        for cum_d in (cum[i_de-1], cum[i_de]):
            b = cum_b
            c = bc - b
            d = cum_d - bc
            e = de - d
            bcde = [b, c, d, e]
            bcde.sort()
            ans = min(ans, bcde[-1]-bcde[0])

print(ans)

Submission status: Accepted

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

left = []
now = a[0]
le = 1
s = a[0]
for i in range(1,n):
    s += a[i]
    while le < i and abs(2*now-s) > abs(2*now+2*a[le]-s):
        now += a[le]
        le += 1
    left.append([now,s-now])

right = []
now = a[-1]
ri = 2
s = a[-1]
for i in range(2,n+1):
    s += a[-i]
    
    while ri < i and abs(2*now-s) > abs(2*now+2*a[-ri]-s):
        now += a[-ri]
        ri += 1
    right.append([now,s-now])

ans = float("INF")
for i in range(n-3):
    a,b = left[i]
    c,d = right[n-4-i]
    ans = min(ans,max(a,b,c,d)-min(a,b,c,d))
print(ans)

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())

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

ans = 10 ** 9 + 7
l = 0
r = 2
for m in range(1, N):
    # Left
    while l < m:
        s1 = abs((d[m] - d[l]) - d[l])
        s2 = abs((d[m] - d[l + 1]) - d[l + 1])
        if s1 > s2:
            l += 1
        else:
            break

    # Right
    while m <= r < N:
        s1 = abs((d[N] - d[r]) - (d[r] - d[m]))
        s2 = abs((d[N] - d[r + 1]) - (d[r + 1] - d[m]))
        if s1 > s2 or m == r:
            r += 1
        else:
            break

    m1 = min(d[l], d[m] - d[l], d[r] - d[m], d[N] - d[r])
    m2 = max(d[l], d[m] - d[l], d[r] - d[m], d[N] - d[r])
    ans = min(ans, m2 - m1)

print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=ruiseki(a)
ans=float('inf')

kirekomi=[1,3]

for i in range(2,n-1):
    while 1:
        if abs(lst[kirekomi[0]]-(lst[i]-lst[kirekomi[0]]))>abs(lst[kirekomi[0]+1]-(lst[i]-lst[kirekomi[0]+1])):
            kirekomi[0]+=1
        else:
            break
    
    while 1:
        if abs((lst[n]-lst[kirekomi[1]])-(lst[kirekomi[1]]-lst[i]))>abs((lst[n]-lst[kirekomi[1]+1])-(lst[kirekomi[1]+1]-lst[i])):
            kirekomi[1]+=1
        else:
            break
    
    # print(kirekomi)
    p=lst[kirekomi[0]]
    q=lst[i]-lst[kirekomi[0]]
    r=lst[kirekomi[1]]-lst[i]
    s=lst[n]-lst[kirekomi[1]]
    anslst=[p,q,r,s]
    ans=min(ans,max(anslst)-min(anslst))
    # print(anslst)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate

nim = int(input())
array = list(accumulate([int(i) for i in input().split()]))
l, r = 0, 1
ans = float("inf")
for i in range(1, nim-2):
    while abs(array[i] - 2 * array[l+1]) < abs(array[i] - 2 * array[l]) and l < i - 1: l += 1
    while abs(array[-1] - 2 * array[r+1] + array[i]) < abs(array[-1] - 2 * array[r] + array[i]) and r < nim - 2: r += 1
    t = [array[l], array[i] - array[l], array[r] - array[i], array[-1] - array[r]]
    ans = min(ans, max(t) - min(t))
print(ans)

Submission status: Accepted

Solution code:
# 2つの部分列に分ける
def eqcut(start, end, prev):
    prev_diff = abs(2 * cumA[prev] - cumA[start - 1] - cumA[end])
    for i in range(prev + 1, end + 1):
        diff = abs(2 * cumA[i] - cumA[start - 1] - cumA[end])
        if diff > prev_diff: break
        prev_diff = diff
    return i - 1

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

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

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

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

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

print(ans)

Submission status: Accepted

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

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

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

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

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

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