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

SUM=[0]
for a in A:
    SUM.append(SUM[-1]+a)
    
i=1
j=2
k=3
P=SUM[i]
Q=SUM[j]-SUM[i]
R=SUM[k]-SUM[j]
S=SUM[N]-SUM[k]
ANS=10**10
check=1

while j<N-1:
    check=1
    while check==1:
        check=0
        if i<j-1:
            if abs(P-Q)>abs(P+A[i]-Q+A[i]):
                P+=A[i]
                Q-=A[i]
                i+=1
                check=1
        if k<N-1:

            if abs(R-S)>abs(R+A[k]-S+A[k]):
                R+=A[k]
                S-=A[k]
                k+=1
                check=1

    #print(P,Q,R,S,i,j,k)
    
    if ANS>max([P,Q,R,S])-min([P,Q,R,S]):
        ANS=max([P,Q,R,S])-min([P,Q,R,S])

    
    Q+=A[j]
    R-=A[j]
    j+=1

print(ANS)

Submission status: Accepted

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

accSum = list(accumulate(A))
ans = float('inf')
for m in range(1, N):
    # 左
    Lm = accSum[m] // 2
    Lx = bisect_left(accSum, Lm)
    if abs(accSum[Lx] - Lm) > abs(accSum[Lx - 1] - Lm):
        Lx -= 1

    # 右
    Rm = (accSum[m] + accSum[-1]) // 2
    Rx = bisect_left(accSum, Rm)
    if abs(accSum[Rx] - Rm) > abs(accSum[Rx - 1] - Rm):
        Rx -= 1

    P, Q, R, S = accSum[Lx], accSum[m] - accSum[Lx], accSum[Rx] - accSum[m], accSum[-1] - accSum[Rx]
    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))

print(ans)

Submission status: Accepted

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

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

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

print(num)

Submission status: Accepted

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

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


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


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

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


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


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

    cum_a = np.cumsum(a_array)
    left_cut_points = (cum_a[1:-2] + 1) // 2
    left_mid_points = np.searchsorted(cum_a, left_cut_points)
    right_cut_points = (cum_a[-1] + cum_a[1:-2] + 1) // 2
    right_mid_points = np.searchsorted(cum_a, right_cut_points)
    
    ans = float('inf')
    for i in range(2):
        for j in range(2):
            P = cum_a[left_mid_points-i]
            Q = cum_a[1:-2] - P
            R = cum_a[right_mid_points-j] - cum_a[1:-2]
            S = cum_a[-1] - cum_a[right_mid_points-j]
            MAX = np.maximum(np.maximum(P, Q), np.maximum(R, S))
            MIN = np.minimum(np.minimum(P, Q), np.minimum(R, S))
            ans = min(ans, (MAX - MIN).min())

    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
Asum = [0]
for i in range(N):
    Asum.append(Asum[i] + A[i])

left, right = 0, 2
Ans = float("inf")
for i in range(1, N-2):
    B = Asum[left+1]-Asum[0]
    C = Asum[i+1] - Asum[left+1]
    while left < i-1:
        if abs(C-B) > abs(C-B-2*A[left+1]):
            left += 1
            B += A[left]
            C -= A[left]
        else:
            break
    if i == right:
        right = i+1
    D = Asum[right+1] - Asum[i+1]
    E = Asum[N] - Asum[right+1]
    while right < N-2:
        if abs(E-D) > abs(E-D-2*A[right+1]):
            right += 1
            D += A[right]
            E -= A[right]
        else:
            break
    Ans = min(Ans, max(B, C, D, E) - min(B, C, D, E))
print(Ans)

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
ruiseki=[0]
for i in range(n):
    ruiseki.append(ruiseki[i] + A[i])

l=1
r=3
ans=[]
for sikiri in range(2,n-1):
    while( ruiseki[sikiri] > 2*ruiseki[l] ):
        l+=1
    if(ruiseki[sikiri] - 2*ruiseki[l-1] <abs(ruiseki[sikiri] - 2*ruiseki[l])):
        l-=1
    r_sum=ruiseki[-1] - ruiseki[sikiri]
    while( r_sum > 2*(ruiseki[r] - ruiseki[sikiri])):
        r+=1
    if( r_sum- 2*(ruiseki[r-1] - ruiseki[sikiri]) <= 2*(ruiseki[r] - ruiseki[sikiri]) - r_sum ):
        r-=1

    if(l<sikiri and sikiri < r):
        tmp=[ruiseki[l],ruiseki[sikiri]-ruiseki[l],ruiseki[r]-ruiseki[sikiri],ruiseki[-1]-ruiseki[r]]
        ans.append(max(tmp) - min(tmp))

print(min(ans))

Submission status: Accepted

Solution code:
from itertools import accumulate

N = int( input())
A = list( map( int, input().split()))
a, b = 0, 2
ans = 10**9 + 1
S = list(accumulate(A))
for i in range(1,N-2):
    while S[a] < S[i] - S[a+1]:
        a += 1
    b = max(b,i+1)
    while S[b] - S[i] < S[-1] - S[b+1]:
        b += 1
    ans = min( ans, max(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]) - min(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
H = [int(i) for i in input().split()]
S = [0 for i in range(N)]
S[0] = H[0]
for i in range(1,N):
    S[i] = H[i] + S[i-1]
left = 0
right = 2
D = S[N-1]
for center in range(1,N-2):
    while  abs(S[center]/2-S[left+1]) <= abs(S[center]/2-S[left]) :
        if left+1 == center:
            break
        else:
            left += 1
    if center == right:
        right += 1
    while  abs(S[N-1]+S[center]-2*S[right+1]) <= abs(S[N-1]+S[center]-2*S[right]) :
        if right == N-2:
            break
        else:
            right += 1 
    D = min(
            max(S[left],S[center]-S[left],S[right]-S[center],S[N-1]-S[right])-
            min(S[left],S[center]-S[left],S[right]-S[center],S[N-1]-S[right])
            ,D)
print(D)

Submission status: Accepted

Solution code:
N=int(input())
A = list(map(int,input().split()))
sum_=[A[0]]
ans =float('inf')
for i in range(1,N):
    sum_.append(sum_[i-1]+A[i])

midL=0
midR=2
for i in range(1,N-2):
    minL=float('inf')
    minR=float('inf')
    for j in range(midL,i):
        if abs(sum_[i]-2*sum_[j]) > minL:
            break
        else:
            midL=j
            minL=abs(sum_[i]-2*sum_[j])
        
    for k in range(midR,N-1):
        if abs(sum_[-1]-2*sum_[k]+sum_[i]) > minR:
            break
        else:
            midR=k
            minR=abs(sum_[-1]-2*sum_[k]+sum_[i])
    tmp =  max(sum_[midL],sum_[i]-sum_[midL],sum_[midR]-sum_[i],sum_[-1]-sum_[midR]) -min(sum_[midL],sum_[i]-sum_[midL],sum_[midR]-sum_[i],sum_[-1]-sum_[midR])
    if ans >tmp:
        ans =tmp
print(ans)

Submission status: Accepted

Solution code:
import sys
 
n = int(input())
a = list(map(int, input().split()))
aa = [0]
for i in range(n):
    aa.append(aa[i] + a[i])
 
ans = sys.maxsize
 
def getdiff(left, center, right):
    return abs((aa[center] - aa[left]) - (aa[right] - aa[center]))
 
L = 1
R = 3
 
for C in range(2, n):
    while L + 1 < C and getdiff(0, L, C) > getdiff(0, L + 1, C):
        L += 1
    while R + 1 < n and getdiff(C, R, n) > getdiff(C, R + 1, n):
        R += 1
    pqrs = [aa[L], aa[C] - aa[L], aa[R] - aa[C], aa[n] - aa[R]]
    pqrs.sort()
    ans = min(ans, pqrs[3] - pqrs[0])
 
print(ans)

Submission status: Accepted

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

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

# sum(A[i:j]) == Asum[j] - Asum[i]
Asum = [0]
tmp = 0
for Ai in A:
    tmp += Ai
    Asum.append(tmp)

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

b1, b3 = (1, 3)
parts = [A[0], A[1], A[2], Asum[N] - Asum[3]]
ans = max(parts) - min(parts)
for b2 in range(2, N - 1):
    parts[1] -= A[b2]
    parts[2] += A[b2]
    if b3 == b2: b3 = b2 + 1
    # b1
    for btmp in range(b1, b2):
        bfr = math.fabs((Asum[b2] - Asum[btmp]) - (Asum[btmp] - Asum[0]))
        aft = math.fabs((Asum[b2] - Asum[btmp + 1]) - (Asum[btmp + 1] - Asum[0]))
        if aft < bfr: continue
        else: break
    b1 = btmp
    # b3
    for btmp in range(b3, N):
        bfr = math.fabs((Asum[N] - Asum[btmp]) - (Asum[btmp] - Asum[b2]))
        aft = math.fabs((Asum[N] - Asum[btmp + 1]) - (Asum[btmp + 1] - Asum[b2]))
        if aft < bfr: continue
        else: break
    b3 = btmp
    # update
    parts = [Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[N] - Asum[b3]]
    if ans > max(parts) - min(parts): ans = max(parts) - min(parts)

print(ans)

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

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

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

Submission status: Accepted

Solution code:
import sys

n = int(input())
a = list(map(int, input().split()))
aa = [0]
for i in range(n):
    aa.append(aa[i] + a[i])

ans = sys.maxsize

def getdiff(left, center, right):
    return abs((aa[center] - aa[left]) - (aa[right] - aa[center]))

L = 1
R = 3

for C in range(2, n):
    while L + 1 < C and getdiff(0, L, C) > getdiff(0, L + 1, C):
        L += 1
    while R + 1 < n and getdiff(C, R, n) > getdiff(C, R + 1, n):
        R += 1
    pqrs = [aa[L], aa[C] - aa[L], aa[R] - aa[C], aa[n] - aa[R]]
    pqrs.sort()
    ans = min(ans, pqrs[3] - pqrs[0])

print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

INF = float('inf')


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


N = int(input())

A = inpl()
B = A[:]

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

ans = INF
mid_l = 0
mid_r = 2
t = B[-1]
for mid in range(1, N - 1):
    while B[mid] > B[mid_l] + B[mid_l + 1]:
        mid_l += 1
    while t > B[mid_r] + B[mid_r + 1] - B[mid]:
        mid_r += 1

    p = B[mid_l]
    q = B[mid] - p
    r = B[mid_r] - p - q
    s = t - r - p - q

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

print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

INF = float('inf')


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


N = int(input())

A = inpl()
B = A[:]

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

ans = INF
mid_l = 0
mid_r = 2
t = B[-1]
for mid in range(1, N - 1):
    while mid_l < mid and abs(2 * B[mid_l] - B[mid]) >= abs(2 * B[mid_l + 1] - B[mid]):
        mid_l += 1
    while mid_r < N - 1 and abs(2 * B[mid_r] - B[mid] - t) >= abs(2 * B[mid_r + 1] - B[mid] - t):
        mid_r += 1

    p = B[mid_l]
    q = B[mid] - p
    r = B[mid_r] - p - q
    s = t - r - p - q

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

print(ans)

Submission status: Accepted

Solution code:
# 累積和, 尺取り法
from itertools import accumulate
_ = int(input())
*a, = accumulate(map(int,input().split()))
l,r,e,ans = 0, 2, a[-1], a[-1]
for m in a[1:-2]:
    # 右部分列を極力等しくしたい
    while a[r] - m < e - a[r+1]:
        r += 1
    # 左部分列を極力等しくしたい
    while a[l] < m - a[l+1]:
        l += 1
    tmp = sorted([ a[l], m-a[l], a[r]-m, e-a[r] ])
    ans = min(ans, tmp[-1]-tmp[0] )
print(ans)

Submission status: Accepted

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

C = [0]
for i in range(1, N + 1):
    C.append(C[-1] + A[i - 1])


def c_sum(right, left):
    return C[right] - C[left]


ans = float('inf')
l = 1
r = 2
for m in range(1, N):
    while abs(c_sum(m, l) - c_sum(l, 0)) > abs(c_sum(m, l + 1) - c_sum(l + 1, 0)):
        l += 1

    while abs(c_sum(N, r) - c_sum(r, m)) > abs(c_sum(N, r + 1) - c_sum(r + 1, m)):
        r += 1

    P = c_sum(l, 0)
    Q = c_sum(m, l)
    R = c_sum(r, m)
    S = c_sum(N, r)
    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Asum = [0]
for i in range(N):
  Asum.append(Asum[i] + A[i])
Diff = Asum[N]
m = 0; n = 2
for i in range(N-3):
  flag = True
  P = Asum[m]; Q = Asum[i+2] - Asum[m]
  while flag:
    m += 1
    if abs(Asum[i+2]-Asum[m]*2) < abs(P-Q):
      P = Asum[m]; Q = Asum[i+2] - Asum[m]
    else:
      flag = False
      m -= 1
  flag = True
  R = Asum[n] - Asum[i+2]; S = Asum[N] - Asum[n]
  while flag:
    n += 1
    if abs(Asum[N]-Asum[n]*2+Asum[i+2]) < abs(R-S):
      R = Asum[n] - Asum[i+2]; S = Asum[N] - Asum[n]
    else:
      flag = False
      n -= 1
  if max(P,Q,R,S)-min(P,Q,R,S) < Diff:
    Diff = max(P,Q,R,S)-min(P,Q,R,S)
print(Diff)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = []
b.append(a[0])
for mid in range(1, len(a)):
  b.append(b[mid - 1] + a[mid])
ans = 10**9

# 累積和から閉区間の合計を求める
def g_sum(l, r):
  if r < l:
    return 0
  res = b[r]
  if l != 0:
    res -= b[l-1]
  return res

lef = 1
rit = 2
for mid in range(2, n - 1):
  # 左
  while abs(g_sum(0, lef - 1) - g_sum(lef, mid - 1)) > abs(g_sum(0, lef) - g_sum(lef + 1, mid - 1)):
    lef += 1
  # 右
  while abs(g_sum(mid, rit - 1) - g_sum(rit, n - 1)) > abs(g_sum(mid, rit) - g_sum(rit + 1, n - 1)):
    rit += 1
  # 各区間の計算
  P = g_sum(0,lef - 1)
  Q = g_sum(lef, mid - 1)
  R = g_sum(mid, rit - 1)
  S = g_sum(rit, n - 1)
  # 最小値算出
  ans = min(ans, max(P,Q,R,S) - min(P,Q,R,S))
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

for i in range(N-1):
	A[i+1]+=A[i]


def nibutan(l,h):
	if l==0:
		t=(A[h]+1)/2
	else:
		t=(A[h]-A[l]+1)/2+A[l]

	for j in range(30):
		m=(h+l)/2
		if A[m]<t:
			l=m
		else:
			h=m
	if abs(A[h]-t)<abs(t-A[l]):
		return h
	else:
		return l

ans=float("inf")
for i in range(1,N-2): 
	m1=nibutan(0,i)
	x1=A[m1]
	x2=A[i]-A[m1]

	m2=nibutan(i,N-1)
	x3=A[m2]-A[i]
	x4=A[-1]-A[m2]

	x_min=min(x1,x2,x3,x4)
	x_max=max(x1,x2,x3,x4)

	ans=min(ans, x_max-x_min)


print ans

Submission status: Accepted

Solution code:
from itertools import accumulate

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

cumA = list(accumulate(A))

l_index = 0
r_index = 2
cumA_max = cumA[-1]

diff = cumA_max

for i in range(1, len(A)-2):
  while abs(cumA[i] - cumA[l_index] - cumA[l_index]) > abs(cumA[i] - cumA[l_index + 1] - cumA[l_index + 1]):
    l_index += 1

  while abs(cumA_max - cumA[r_index] - (cumA[r_index] - cumA[i])) > abs(cumA_max - cumA[r_index + 1] - (cumA[r_index + 1] - cumA[i])):
    r_index += 1
        
  left = cumA[l_index]
  center = cumA[i] - cumA[l_index]
  right = cumA[r_index] - cumA[i]
  last = cumA_max - cumA[r_index]

  diff = min(diff, max(left, center, right, last) - min(left, center, right, last))

print(diff)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

cumA = list(accumulate(A))

l_index = 0
r_index = 2
cumA_max = cumA[-1]

diff = cumA_max

for i in range(1, len(A)-2):
  # iで切った左の部分列において、l_iで切った時、左より右の方が大きいときは1ずらせる
  while cumA[l_index] < cumA[i] - cumA[l_index + 1]:
    l_index += 1

  # iで切った右の部分列において、r_iで切った時、左より右の方が大きいときは1ずらせる
  while cumA[r_index] - cumA[i] < cumA_max - cumA[r_index + 1]:
    r_index += 1
        
  left = cumA[l_index]
  center = cumA[i] - cumA[l_index]
  right = cumA[r_index] - cumA[i]
  last = cumA_max - cumA[r_index]

  diff = min(diff, max(left, center, right, last) - min(left, center, right, last))

print(diff)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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

N = int(input())
aa = inpl()
SUM = sum(aa)
SUMaa_L = [0]
SUMaa_R = [SUM]

tmp = 0
for a in aa:
	tmp += a
	SUMaa_L.append(tmp)
	SUMaa_R.append(SUM-tmp)

cutL = []
l = 1
SUML = SUMaa_L[l]
for cutM in range(2,N-1):
	SUM = SUMaa_L[cutM]
	while SUML < SUM/2:
		l += 1
		SUML = SUMaa_L[l]
	l1,l2 = SUMaa_L[l-1], SUMaa_L[l]
	r1,r2 = SUM-l1, SUM-l2
	if abs(l1-r1) > abs(l2-r2):
		cutL.append([l2,r2])
	else:
		cutL.append([l1,r1])

cutR = []
r = N-1
SUMR = SUMaa_R[r]
for cutM in reversed(range(2,N-1)):
	SUM = SUMaa_R[cutM]
	while SUMR < SUM/2:
		r -= 1
		SUMR = SUMaa_R[r]
	l1,l2 = SUMaa_R[r+1], SUMaa_R[r]
	r1,r2 = SUM-l1, SUM-l2
	if abs(l1-r1) > abs(l2-r2):
		cutR.append([l2,r2])
	else:
		cutR.append([l1,r1])

ans = INF
for i in range(N-3):
	a,b = cutL[i]
	c,d = cutR[N-4-i]
	ans = min(ans,max(a,b,c,d)-min(a,b,c,d))

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
S=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=S[i]+A[i]
B=A[::-1]
T=[0 for i in range(N+1)]
for i in range(N):
    T[i+1]=T[i]+B[i]
F=[0 for i in range(N)]
G=[0 for i in range(N)]
for i in range(N):
    LS=S[i+1]
    k=0
    if i!=0:
        k=F[i-1]
    if k!=0:
        k-=1
    tmp=LS
    for j in range(k,i+1):
        L=S[j]
        R=LS-S[j]
        if abs(R-L)<=tmp:
            F[i]=j
        else:
            break
        tmp=abs(R-L)
    if F[i]<=0:
        F[i]=0
for i in range(N):
    RS=T[i+1]
    k=0
    if i!=0:
        k=G[i-1]
    if k!=0:
        k-=1
    tmp=LS
    for j in range(k,i+1):
        L=T[j]
        R=RS-T[j]
        if abs(R-L)<=tmp:
            G[i]=j
        else:
            break
        tmp=abs(R-L)
    if G[i]<=0:
        G[i]=0
ans=S[N]
for i in range(N):
    A=[0 for i in range(4)]
    k=0
    if i!=0:
        k=F[i-1]
    A[0]=S[k]
    A[1]=S[i]-S[k]
    A[2]=T[N-i]-T[G[N-i-1]]
    A[3]=T[G[N-i-1]]
    score=max(A)-min(A)
    if ans>score:
        ans=score
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

from itertools import accumulate

def getAccumulate(A):
    return list(accumulate(A))

def solve(A):
    accum = getAccumulate(A)
    l_index = 0
    r_index = 2
    accum_max = accum[-1]

    diff = accum_max
    for i in range(1, len(A)-2):
        while accum[i] > accum[l_index] + accum[l_index + 1]:
            l_index += 1
        while accum_max + accum[i] > accum[r_index] + accum[r_index + 1]:
            r_index += 1
        
        left = accum[l_index]
        center = accum[i] - accum[l_index]
        right = accum[r_index] - accum[i]
        last = accum_max - accum[r_index]
        diff = min(diff, max(left, center, right, last) - min(left, center, right, last))
        
    return diff

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    print(solve(A))

Submission status: Accepted

Solution code:
from itertools import accumulate

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

sum_a = list(accumulate(A))
lft = 0
rgt = 2
t = sum_a[-1]
ans = t
for i in range(1,N-2):
    while sum_a[i] - sum_a[lft+1] > sum_a[lft]:
        lft += 1

    while t - sum_a[rgt+1] > sum_a[rgt] - sum_a[i]:
        rgt += 1
    p = sum_a[lft]
    q = sum_a[i] - p
    r = sum_a[rgt] - q - p
    s = t - r - q - p

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

print(ans)

Submission status: Accepted

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

lsum=A[0]+A[1] #真ん中の仕切りの左側の総和
rsum=0 #真ん中の仕切りの右側の総和
for i in range(2,n):
    rsum+=A[i]

res=lsum+rsum
le=0
ri=2
sum1=0
sum2=lsum
sum3=0
sum4=rsum

for mid in range(2,n-1): #真ん中の仕切り
    while le<mid and (abs((sum1+A[le])-(sum2-A[le]))<abs(sum1-sum2)) :
        sum1+=A[le]
        sum2-=A[le]
        le+=1
    while ri<n and (abs((sum3+A[ri])-(sum4-A[ri]))<abs(sum3-sum4)) :
        sum3+=A[ri]
        sum4-=A[ri]
        ri+=1


    #print(str(sum1)+" "+str(sum2)+" "+str(sum3)+" "+str(sum4))

    res=min(res,max(sum1,sum2,sum3,sum4)-min(sum1,sum2,sum3,sum4))

    sum2+=A[mid]
    sum3-=A[mid]


print(res)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

sum_a = list(accumulate(A))
lft = 0
rgt = 2
t = sum_a[-1]
ans = t

for i in range(1,N-2):
    # P<=Q となるように左側の仕切りを動かす
    while sum_a[i] > sum_a[lft] + sum_a[lft+1]:
        lft += 1
        
    while t + sum_a[i] > sum_a[rgt] + sum_a[rgt+1]:
        rgt += 1
        
    p = sum_a[lft]
    q = sum_a[i] - p
    r = sum_a[rgt] - q - p
    s = t - r - q - p
    
    ans = min(ans, max(p,q,r,s) - min(p,q,r,s))
    
print(ans)

Submission status: Accepted

Solution code:
def getsum(data, start, end):
    if start == 0:
        return data[end - 1]
    else:
        return data[end - 1] - data[start - 1]

def getdiff(data, start_point, second_point, end_point):
    return abs(getsum(data, second_point, end_point) - getsum(data, start_point, second_point))

n = int(input())
input_data = list(map(int,input().split()))
summed_data = []
summed_data.append(input_data[0])

for i in range(1, n):
    summed_data.append(summed_data[i-1]+input_data[i])

first_separator = 1
third_separator = 3
minimized_diff = 2 * pow(10, 5) * pow(10, 9)

for second_separator in range(2, (n - 1)):
    if second_separator >= third_separator:
        third_separator = second_separator + 1

    while first_separator < (second_separator - 1) and getdiff(summed_data, 0, (first_separator + 1), second_separator) < getdiff(summed_data, 0, first_separator, second_separator):
        first_separator = first_separator + 1

    while third_separator < (n - 1) and getdiff(summed_data, second_separator, (third_separator + 1), n) < getdiff(summed_data, second_separator, third_separator, n):
        third_separator = third_separator + 1

    sum_list = [getsum(summed_data, 0, first_separator), getsum(summed_data, first_separator, second_separator), getsum(summed_data, second_separator, third_separator), getsum(summed_data, third_separator, n)]
    diff = max(sum_list) - min(sum_list)
    if diff < minimized_diff:
        minimized_diff = diff

print(minimized_diff)

Submission status: Accepted

Solution code:
INF = 2 * 10**5 * 10**9
n = int(input())
a = map(int,input().split())
s = [0]
for x in a:
    s.append(s[-1]+x)
ans = INF
p1 = 1
p = 1
p2 = 3
while True:
    p += 1
    if p + 1 >= n:
        break
    while p1 < p and abs(s[p1] - s[p] + s[p1]) > abs(s[p1+1] - s[p] + s[p1 + 1]):
        p1 += 1
    while p2 < n and abs(s[p2] - s[p]  - s[n] + s[p2]) > abs(s[p2+1] - s[p]  - s[n] + s[p2+1]):
        p2 += 1
    ans = min(ans , max(s[p1],s[p]-s[p1],s[p2]-s[p],s[n]-s[p2]) -  min(s[p1],s[p]-s[p1],s[p2]-s[p],s[n]-s[p2]) )
print(ans)

Submission status: Accepted

Solution code:
INF = 2 * 10**5 * 10**9
n = int(input())
a = map(int,input().split())
s = [0]
for x in a:
    s.append(s[-1]+x)
ans = INF
p1 = 1
p = 2
p2 = 3
def update():
    global ans
    if p1 < p and p2 < n:
        ans = min(ans , max(s[p1],s[p]-s[p1],s[p2]-s[p],s[n]-s[p2]) -  min(s[p1],s[p]-s[p1],s[p2]-s[p],s[n]-s[p2]) )
    if p2 < n and p1 - 1 >= 1:
        ans = min(ans , max(s[p1-1],s[p]-s[p1-1],s[p2]-s[p],s[n]-s[p2]) -  min(s[p1-1],s[p]-s[p1-1],s[p2]-s[p],s[n]-s[p2]) )
    if p1 < p and p2-1 >= p:
        ans = min(ans , max(s[p1],s[p]-s[p1],s[p2-1]-s[p],s[n]-s[p2-1]) -  min(s[p1],s[p]-s[p1],s[p2-1]-s[p],s[n]-s[p2-1]) )
    if p1-1 >= 1 and p2-1 >= p:
        ans = min(ans , max(s[p1-1],s[p]-s[p1-1],s[p2-1]-s[p],s[n]-s[p2-1]) -  min(s[p1-1],s[p]-s[p1-1],s[p2-1]-s[p],s[n]-s[p2-1]) ) 
while p2 < n and s[p2] - s[p] < s[n] - s[p2]:
    p2 += 1
update()
while True:
    p += 1
    if p + 1 >= n:
        break
    while p1 < p and s[p1] < s[p] - s[p1]:
        p1 += 1
    while p2 < n and s[p2] - s[p] < s[n] - s[p2]:
        p2 += 1
    update()
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

Submission status: Accepted

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

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

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

min_dif = sum_a(0, n)

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

    u = sum_a(j, n) // 2
    while sum_a(j, k) < u:
        k = k + 1
    if abs(sum_a(j, k-1)-sum_a(k-1, n)) < abs(sum_a(j, k) - sum_a(k, n)): 
        k = k - 1
    r = sum_a(j, k)
    s = sum_a(k, n)

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

print(min_dif)

Submission status: Accepted

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

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

ans = 10**20
l = 0
r = 2
for c in range(1, n-2):
    r = max(r, c+1)

    while l+1 < c and abs(a[c]-2*a[l]) >= abs(a[c]-2*a[l+1]):
        l += 1
    while r+1 < n and abs(a[-1]-2*a[r]+a[c]) >= abs(a[-1]-2*a[r+1]+a[c]):
        r += 1

    x = [a[l], a[c]-a[l], a[r]-a[c], a[-1]-a[r]]
    x.sort()
    ans = min(ans, x[3]-x[0])

print(ans)

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
    funcs = (lambda ary, l, r: ary[r] - ary[l],
             lambda left, right: abs(left - right),
             lambda val1, val2: True if val1 < val2 else False)
    griefs = []
    for i in range(2, n - 1):
        # left
        l_split, l_diff, p, q = two_pointers(cul_ary, 0, i, l_split, *funcs)

        # right
        r_split, r_diff, r, s = two_pointers(cul_ary, i, n, r_split, *funcs)

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

    print(min(griefs))