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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

def main():
    n = int(input())
    a = list(map(int, input().split()))
    p, q, r, s = a[0], a[1], a[2], sum(a[3:])
    lb, rb = 1, 3
    ans = max(p, q, r, s) - min(p, q, r, s)
    for mb in range(2, n-1):
        if mb > 2:
            q += a[mb-1]
            r -= a[mb-1]
        if mb == rb:
            r = a[rb]
            s -= a[rb]
            rb += 1
        while lb+1 < mb and abs(q-p) >= abs(p+a[lb] - (q-a[lb])):
            p += a[lb]
            q -= a[lb]
            lb += 1
        while rb+1 < n and abs(s-r) >= abs(r+a[rb] - (s-a[rb])):
            r += a[rb]
            s -= a[rb]
            rb += 1
        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 sys
def input():
	return sys.stdin.readline().strip()

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

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

ans = 10**14

one = 0
three = 2
for i in range(1, N - 2):
	if three == i:
		three += 1
	sum_half1 = A_sum[i + 1]
	sum_half2 = A_sum[-1] - A_sum[i + 1]
	while one < i - 1:
		if abs(A_sum[one + 1] - sum_half1/2) > abs(A_sum[one + 2] - sum_half1/2):
			one += 1
		else:
			break
	while three < N - 2:
		if abs(A_sum[three + 1] - A_sum[i + 1] - sum_half2/2) > abs(A_sum[three + 2] - A_sum[i + 1] - sum_half2/2):
			three += 1
		else:
			break

	x = max(A_sum[one + 1], A_sum[i + 1] - A_sum[one + 1], A_sum[three + 1] - A_sum[i + 1], A_sum[-1] - A_sum[three + 1])
	y = min(A_sum[one + 1], A_sum[i + 1] - A_sum[one + 1], A_sum[three + 1] - A_sum[i + 1], A_sum[-1] - A_sum[three + 1])
	ans = min(ans, x - y)
	#print(one, i, three, x - y, ans, sum_half2//2)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N = int(input())
A = list(map(int, input().split()))
S1 = [A[0]]*N
S2 = [A[-1]]*N
for i in range(1, N):
    S1[i] = S1[i-1]+A[i]
    S2[i] = S2[i-1]+A[N-i-1]
ans = S1[-1]
for i in range(1, N-2):
    s1 = S1[i]
    b = bisect_left(S1, s1/2)
    if abs(S1[b]-s1/2)>abs(s1/2-S1[b-1]):
        b-=1
    P, Q = S1[b], s1-S1[b]
    s2 = S2[N-i-2]
    c = bisect_left(S2, s2/2)
    if abs(S2[c]-s2/2)>abs(s2/2-S2[c-1]):
        c-=1
    R, S = S2[c], s2-S2[c]
    res = max(P, Q, R, S)-min(P, Q, R, S)
    ans = min(ans, res)
print(ans)

Submission status: Accepted

Solution code:
def lower_bound(l, r, val):
    while r - l > 1:
        mid = (r + l) // 2
        if sum[mid] <= val:
            l = mid
        else:
            r = mid
    return l


def get_sum(l, r):
    return sum[r] - (0 if l == 0 else sum[l - 1])


def search(l, r):
    mid = lower_bound(l, r + 1, get_sum(l, r) / 2 + (0 if l == 0 else sum[l - 1]))
    for i in range(mid - 2, mid + 3):
        if l <= i and i + 1 <= r:
            yield get_sum(l, i), get_sum(i + 1, r)


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

tmp = 0
sum = [0 for i in range(N)]

for a, b in enumerate(A):
    tmp += b
    sum[a] = tmp

ans = tmp

for ind in range(1, N - 2):
    for l1, r1 in search(0, ind):
        for l2, r2 in search(ind + 1, N - 1):
            t = l1, r1, l2, r2
            ans = min(ans, max(t) - min(t))

print(ans)

Submission status: Accepted

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

tmp = 0
sum = [0 for i in range(N)]

for a, b in enumerate(A):
    tmp += b
    sum[a] = tmp


def search(l, r):
    mid = lower_bound(l, r + 1, get_sum(l, r) / 2 + (0 if l == 0 else sum[l-1]))
    for i in range(mid - 2, mid + 3):
        if l <= i and i + 1 <= r:
            yield get_sum(l, i), get_sum(i + 1, r)


#
# 10
# 10 71 84 33 6 47 23 25 52 64
## 81 84 86 164
## 81 84 134 116
## 81 123 95 116
## (81, 117, 101, 116)

def lower_bound(l, r, val):
    while r-l > 1:
        mid = (r + l) // 2
        if sum[mid] <= val:
            l = mid
        else:
            r = mid
    return l


def get_sum(l, r):
    return sum[r] - (0 if l == 0 else sum[l - 1])


ans = tmp

for ind in range(1, N - 2):
    for l1, r1 in search(0, ind):
        for l2, r2 in search(ind + 1, N - 1):
            # print(ind)
            # print(l1, r1, l2, r2)
            t = l1, r1, l2, r2
            # print(t)
            ans = min(ans, max(t) - min(t))
            # if ans == 36:
            #     print("ans   ", t)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
 
i, k = 0, 2
p, q, r, s = 0, a[0], a[1], sum(a[2:])
ans = sum(a)
for j in range(1, n-2):
    q += a[j]
    while abs((q-a[i]) - (p+a[i])) < abs(q - p):
        p += a[i]
        q -= a[i]
        i += 1
 
    r -= a[j]
    while abs((s-a[k]) - (r+a[k])) < abs(s - r):
        r += a[k]
        s -= a[k]
        k += 1
 
    pqrs = [p, q, r, s]
    ans = min(ans, abs(max(pqrs) - min(pqrs)))
    # print(i, j, k, ans, pqrs)
    
print(ans)

Submission status: Accepted

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

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

i, k = 0, 2
ans = 10**18
for j in range(1, n-2):
    while i < j:
        p = cumsum[i]
        q = cumsum[j] - cumsum[i]
        p_new = cumsum[i+1]
        q_new = cumsum[j] - cumsum[i+1]
        if abs(q_new - p_new) > abs(q - p):
            break
        else:
            i += 1

    while k < n-1:
        r = cumsum[k] - cumsum[j]
        s = cumsum[n-1] - cumsum[k]
        r_new = cumsum[k+1] - cumsum[j]
        s_new = cumsum[n-1] - cumsum[k+1]
        if abs(s_new - r_new) > abs(s - r):
            break
        else:
            k += 1

    pqrs = [p, q, r, s]
    ans = min(ans, abs(max(pqrs) - min(pqrs)))
    # print(i, j, k, ans, pqrs)
    
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
inlis=[int(i) for i in input().split()]
csum=[0]*(N+1)
for i, v in enumerate(inlis, start=1): csum[i] = csum[i-1] + v
i, k = 1, 3
resmin = 9223372036854775807
for j in range(2, N-1):
    while abs((csum[i]-csum[0]) - (csum[j]-csum[i])) > abs((csum[i+1]-csum[0]) - (csum[j]-csum[i+1])): i += 1
    while abs((csum[k]-csum[j]) - (csum[N]-csum[k])) > abs((csum[k+1]-csum[j]) - (csum[N]-csum[k+1])): k += 1
    resmin = min(resmin, max(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k]) - min(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k]))
print(resmin)

Submission status: Accepted

Solution code:
N=int(input())
inlis=[int(i) for i in input().split()]
csum=[0]*(N+1)
for i, v in enumerate(inlis, start=1): csum[i] = csum[i-1] + v

i, k = 1, 3
resmin = 9223372036854775807
# print(csum)
for j in range(2, N-1):
    while abs((csum[i]-csum[0]) - (csum[j]-csum[i])) > abs((csum[i+1]-csum[0]) - (csum[j]-csum[i+1])): i += 1
    while abs((csum[k]-csum[j]) - (csum[N]-csum[k])) > abs((csum[k+1]-csum[j]) - (csum[N]-csum[k+1])): k += 1
    # print("p{} q{} r{} s{}".format(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k]))
    # minkamo = max(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k]) - min(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k])
    # print(i,j,k, minkamo)
    resmin = min(resmin, max(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k]) - min(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k]))

print(resmin)

Submission status: Accepted

Solution code:
import sys,collections as cl
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

n = int(input())

a = l()
aa = [a[0]]

for i in range(n-1):
	aa.append(aa[-1] + a[i+1])

ans = Max
l = 0
r = 2
s = aa[1]
su = aa[-1]-s
for i in range(1,n-1):
	while(l < i and (s >= abs(2*aa[l] - aa[i]))):
		s =  abs(2*aa[l] - aa[i])
		l += 1

	while(r < n and (su >= abs(aa[-1]-aa[r]-(aa[r] - aa[i])))):
		su = abs(aa[-1]-aa[r]-(aa[r] - aa[i]))
		r += 1
	ans = min(ans,(max(aa[l-1],aa[i]-aa[l-1],aa[r-1]-aa[i],aa[-1]-aa[r-1]) - min(aa[l-1],aa[i]-aa[l-1],aa[r-1]-aa[i],aa[-1]-aa[r-1])))
	s = abs(2*aa[l-1] - aa[i+1])
	su = abs(aa[-1]-aa[r-1]-(aa[r-1] - aa[i+1]))


print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=LIST()

cmsm=[0]+list(accumulate(A))
ans=INF
for i in range(2, N-1):
    # 左
    S1=cmsm[i]
    idx1=bisect_left(cmsm, S1/2)
    # 境界の手前と比べて、差が小さい方を取る
    if abs(cmsm[idx1-1]-S1/2)<abs(cmsm[idx1]-S1/2):
        idx1-=1

    # 右
    S2=cmsm[N]-cmsm[i]
    idx2=bisect_left(cmsm, S1+S2/2)
    if abs(cmsm[idx2-1]-(S1+S2/2))<abs(cmsm[idx2]-(S1+S2/2)):
        idx2-=1

    p=cmsm[idx1]-cmsm[0]
    q=cmsm[i]-cmsm[idx1]
    r=cmsm[idx2]-cmsm[i]
    s=cmsm[N]-cmsm[idx2]
    mx=max(p, q, r, s)
    mn=min(p, q, r, s)
    ans=min(ans, mx-mn)
print(ans)

Submission status: Accepted

Solution code:
import bisect
def inpl(): return list(map(int,input().split()))

N = int(input())
A = inpl()

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

mindiff = cum[N-1]
for j in range(2,N-1):
    sum1 = cum[j-1]
    sum2 = cum[N-1]-cum[j-1]
    i = bisect.bisect_left(cum, sum1/2)
    k = bisect.bisect_left(cum, sum1 + sum2/2)
    if i == 0:
        max1 = A[0]
        min1 = cum[j-1]-A[0]
    elif j == 2:
        max1 = A[1]
        min1 = A[0]
    else:
        max1 = min(cum[i],cum[j-1]-cum[i-1])
        min1 = max(cum[i-1],cum[j-1]-cum[i])

    if k == j:
        max2 = A[j]
        min2 = cum[N-1]-cum[j]
    elif j == N-2:
        max2 = A[N-1]
        min2 = A[N-2]
    else:
        max2 = min(cum[k]-cum[j-1],cum[N-1]-cum[k-1])
        min2 = max(cum[k-1]-cum[j-1],cum[N-1]-cum[k])

    max3 = max(max1,max2)
    min3 = min(min1,min2)
    mindiff = min(mindiff, max3-min3)

print(mindiff)

Submission status: Accepted

Solution code:
from bisect import bisect, bisect_left

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

ans = float("inf")
for j in range(2, n-1):
	c = []
	f = bisect(b, b[j]/2)
	f -= 1
	if f == 0 or j == 2:
		c += [b[1]-b[0], b[j]-b[1]]
	elif f == j-1:
		c += [b[j-1]-b[0], b[j]-b[j-1]]
	else:
		if abs(b[f]-b[0] - (b[j]-b[f])) <= abs(b[f+1]-b[0] - (b[j]-b[f+1])):
			c += [b[f]-b[0], b[j]-b[f]]
		else:
			c += [b[f+1]-b[0], b[j]-b[f+1]]

	l = bisect(b, b[j]+((b[n]-b[j])/2))
	l -= 1
	#print(l)
	if l == j or j == n-2:
		c += [b[j+1]-b[j], b[n]-b[j+1]]
	elif l == n-1:
		c += [b[n-1]-b[j], b[n]-b[n-1]]
	else:
		if abs(b[l]-b[j] - (b[n]-b[l])) <= abs(b[l+1]-b[j] - (b[n]-b[l+1])):
			c += [b[l]-b[j], b[n]-b[l]]
		else:
			c += [b[l+1]-b[j], b[n]-b[l+1]]

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

print(ans)

Submission status: Accepted

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

sumai = []
s = 0
for i in ai:
    s += i
    sumai.append(s)
lcut = 0 # l1 = sumai[lcut]
rcut = 2 #  r2 = sumai[N-1]-sumai[rcut]
l1 = sumai[lcut]
r2 = sumai[N-1]-sumai[rcut]
ans = []
for i in range(1,N-2):
    while abs(sumai[lcut]-(sumai[i]-sumai[lcut]))>abs(sumai[lcut+1]-(sumai[i]-sumai[lcut+1])):
        lcut += 1
    while abs((sumai[N-1]-sumai[rcut])-(sumai[rcut]-sumai[i]))>abs((sumai[N-1]-sumai[rcut+1])-(sumai[rcut+1]-sumai[i])):
        rcut += 1
    ans.append(max(sumai[lcut],sumai[i]-sumai[lcut],sumai[N-1]-sumai[rcut],sumai[rcut]-sumai[i])-min(sumai[lcut],sumai[i]-sumai[lcut],sumai[N-1]-sumai[rcut],sumai[rcut]-sumai[i]))
print(min(ans))

Submission status: Accepted

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

ans = float('inf')
iB, iD = 1, 3
(P, Q, R), S = As[:3], sum(As[3:])

# 真ん中の区切りを全通り試す
for iC in range(2, N - 1):
    while P < Q and As[iB] <= Q - P:
        P += As[iB]
        Q -= As[iB]
        iB += 1

    while R < S and As[iD] <= S - R:
        R += As[iD]
        S -= As[iD]
        iD += 1

    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))

    Q += As[iC]
    R -= As[iC]

print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
list = list(map(int, input().split()))
sum = [0] * (n + 1)
for i in range(1, n+1):
    sum[i] = sum[i-1] + list[i-1]
result = []
for i in range(3, n):
    half1 = sum[i-1] // 2
    i1 = bisect.bisect_right(sum, half1)
    if (half1 - sum[i1 - 1]) < sum[i1] - half1:
        a1 = sum[i1 - 1]
        a2 = sum[i-1] - sum[i1 - 1]
    else:
        a1 = sum[i1]
        a2 = sum[i-1] - sum[i1]
    
    
    half2 = (sum[n] + sum[i-1]) // 2
    i2 = bisect.bisect_right(sum, half2)
    if (half2 - sum[i2 - 1]) < sum[i2] - half2:
        a3 = sum[i2 - 1] - sum[i-1]
        a4 = sum[n] - sum[i2 - 1]
    else:
        a3 = sum[i2] - sum[i-1]
        a4 = sum[n] - sum[i2]
    result.append(max(a1,a2,a3,a4) - min(a1,a2,a3,a4))
print(min(result))

Submission status: Accepted

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

l = 1
m = 1
r = 3

sumll = a[0]
suml = a[0]
sumrr = sum(a[3:])
sumr = a[1]+a[2]+sumrr

res = sumr + a[0]

for m in range(1,n-2):
    suml += a[m]
    sumr -= a[m]
    while sumll+a[l]<=suml/2 and l<m:
        sumll += a[l]
        l += 1
    while sumrr-a[r]>=sumr/2 and r<n-1:
        sumrr -= a[r]
        r += 1
    p1 = sumll
    q1 = suml - sumll
    r1 = sumr - sumrr
    s1 = sumrr
    # print(p1,q1,r1,s1)
    p2 = p1 + a[l]
    q2 = q1 - a[l]
    r2 = r1 + a[r]
    s2 = s1 - a[r]
    abs1 = max(p1,q1,r1,s1)-min(p1,q1,r1,s1)
    abs2 = max(p2,q2,r2,s2)-min(p2,q2,r2,s2)
    abs3 = max(p1,q1,r2,s2)-min(p1,q1,r2,s2)
    abs4 = max(p2,q2,r1,s1)-min(p2,q2,r1,s1)
    rest = min(abs1,abs2,abs3,abs4)
    if res > rest:
        res = rest

print(res)

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:
import random
from itertools import accumulate
N = int(input())
As = [int(i) for i in input().split(' ')]

#N = pow(10, 4)
#As = [random.randint(0,1000) for r in range(N)] 
As = list(accumulate(As))


def bsearch(L, l, r, ls, rs):
    if r - l == 0:
        l_temp = L[l-1] if l!=0 else 0
        lsum = l_temp - ls
        return [max(lsum, rs - L[l]), min(lsum, rs - L[l]) + L[l] - l_temp]
    n = int((r-l)/2)
    lsum = L[l+n] - ls
    rsum = rs - L[l+n]
    if lsum > rsum:
        return bsearch(L, l, l+n, ls, rs)
    else:
        return bsearch(L, l+n+1, r, ls, rs)

for i in range(N-3):
    cs = bsearch(As, 0, i+1, 0, As[i+1]) + bsearch(As ,i+2, N-1, As[i+1], As[-1])
    if i == 0:
        result = max(cs) - min(cs)
    else:
        if max(cs) - min(cs) < result:
            result = max(cs) - min(cs)
print(result)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = list(map(int, input().split()))
accum = [0 for i in range(N + 1)]
for i in range(N):
    accum[i + 1] = accum[i] + A[i]
total = accum[N]
#accum[i + 1] = A[0] + A[1] + ... + A[i]
#sum(A[i:j]) = A[i] + A[i+1] + ... + A[j-1] = accum[j] - accum[i]
ans = float('inf')
for i in range(2, N - 1, 1): #2番目の区切りを A[i-1]とA[i]の間に入れる
    zenhan = accum[i] #(= sum(A[:i]))
    kouhan = total - zenhan #(= accum[N] - accum[i] = sum(A[i:N]))
    index1l = bisect.bisect(accum, zenhan // 2, lo = 2, hi = i) - 1
    index1r = min(index1l + 1, i - 1)
    index3l = bisect.bisect(accum, zenhan + (kouhan // 2), lo = i + 2, hi = N) - 1
    index3r = min(index3l + 1, N - 1)
    for index1 in (index1l, index1r):
        for index3 in (index3l, index3r):
            B, C, D, E = accum[index1], zenhan - accum[index1], accum[index3] - zenhan, total - accum[index3]
            M = max(B, C, D, E)
            m = min(B, C, D, E)
            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


ans = float("inf")
if N == 4:
    ans = min(ans, (max(A) - min(A)))
else:
    cs = list(accumulate(A))
    l = 0
    r = 0
    for i in range(1, N - 2):
        while cs[i] > cs[l] + cs[l+1]:
            l += 1
        while cs[-1] + cs[i] > cs[r] + cs[r+1]:
            r += 1
        P = cs[l]
        Q = cs[i] - P
        R = cs[r] - P - Q
        S = cs[-1] - cs[r]
        ans = min(ans, (max(P, Q, R, S) - min(P, Q, R, S)))

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

P = list(accumulate(A))
P.insert(0, 0)

ans = float('inf')
for i in range(2, N-1):
    # 左
    Lmid = P[i] / 2
    Lx = bisect_left(P, Lmid)
    if abs(P[Lx] - Lmid) > abs(P[Lx-1] - Lmid):
        Lx -= 1

    # 右
    Rmid = (P[i] + P[N]) / 2
    Rx = bisect_left(P, Rmid)
    if abs(P[Rx] - Rmid) > abs(P[Rx-1] - Rmid):
        Rx -= 1

    M = max(P[Lx], P[i]-P[Lx], P[Rx]-P[i], P[N]-P[Rx])
    m = min(P[Lx], P[i]-P[Lx], P[Rx]-P[i], P[N]-P[Rx])

    ans = min(ans, M-m)

print(ans)

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
a=i2()
c=[0 for i in range(n)]


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

l=0
r=2
f=float("inf")
for i in range(1,n-1):
 while abs(c[l]-(c[i]-c[l]))>abs(c[l+1]-(c[i]-c[l+1])):
   l+=1
 while abs(c[r]-c[i]-(c[n-1]-c[r]))>abs(c[r+1]-c[i]-(c[n-1]-c[r+1])):
   r+=1
 e=[c[l],c[i]-c[l],c[r]-c[i],c[n-1]-c[r]]
 f=min(f,max(e)-min(e))
print(f)

Submission status: Accepted

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

pref = [0]

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

lt = 1
rt = 3
ans = 10**18
for i in range(2,n):
    while lt+1<i and abs(pref[i] - pref[lt+1] - pref[lt+1]) < abs(pref[i] - pref[lt] - pref[lt]):
        lt+=1
    
    while rt>=i and rt<n and (abs(pref[n] - pref[rt+1] - pref[rt+1] + pref[i]) < abs(pref[n] - pref[rt] - pref[rt] + pref[i])):
        rt+=1
    #print(i)
    ans = min(ans, abs(max(pref[lt], pref[i]-pref[lt], pref[rt]-pref[i], pref[n]-pref[rt]) - min(pref[lt], pref[i]-pref[lt], pref[rt]-pref[i], pref[n]-pref[rt])))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
def f(a):
    l, r = a[:2]
    m = 1
    b = [(l,r)]
    for i in range(2, n-2):
        r += a[i]
        while m<i and abs(l-r)>abs(l-r+a[m]*2): 
            l, r = l+a[m], r-a[m]
            m += 1
        b.append((l,r))
    return b
print(min(max(p,q,r,s)-min(p,q,r,s)
        for ((p,q),(r,s)) in zip(f(a), f(a[::-1])[::-1])))

Submission status: Accepted

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

l, r = a[:2]
m = 1
b = [(l,r)]
for i in range(2, n-2):
    r += a[i]
    for j in range(m, i):
        nl, nr = l+a[j], r-a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m += 1
    b.append((l,r))

l, r = a[-2:]
m = n-2
c = [(l,r)]
for i in range(2, n-2)[::-1]:
    l += a[i]
    for j in range(i+1, m+1)[::-1]:
        nl, nr = l-a[j], r+a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m -= 1
    c.append((l,r))

r = 10**9
for i in range(n-3):
    x = max(b[i]+c[-i-1])
    y = min(b[i]+c[-i-1])
    r = min(r, x-y)
print(r)

Submission status: Accepted

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

cumsum = list(accumulate(A))
cumsum.insert(0, 0)

ans = float('inf')
for m in range(2, N-1):
    # 左
    Lmid = cumsum[m] / 2
    Lx = bisect_left(cumsum, Lmid)
    if abs(Lmid-cumsum[Lx]) > abs(Lmid-cumsum[Lx-1]):
        Lx -= 1

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

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

print(ans)

Submission status: Accepted

Solution code:
INF = 99999999999
N = int(input())
a = list(map(int, input().split()))
ss = [0] * (N + 1)
s = 0
for i, n in enumerate(a):
    s += n
    ss[i + 1] = s


def psum(l, r):
    return ss[r] - ss[l]

min_ns = [[0, 0, 0, 0] for _ in range(N - 3)]

l = 1
for r in range(2, N - 1):
    min_n = abs(psum(0, l) - psum(l, r))
    while True:
        if l + 1 < r and min_n > abs(psum(0, l + 1) - psum(l + 1, r)):
            min_n = abs(psum(0, l + 1) - psum(l + 1, r))
            l += 1
        else:
            break
    min_ns[r - 2][0] = psum(0, l)
    min_ns[r - 2][1] = psum(l, r)

a.reverse()
s = 0
for i, n in enumerate(a):
    s += n
    ss[i + 1] = s

l = 1
for r in range(2, N - 1):
    min_n = abs(psum(0, l) - psum(l, r))
    while True:
        if l + 1 < r and min_n > abs(psum(0, l + 1) - psum(l + 1, r)):
            min_n = abs(psum(0, l + 1) - psum(l + 1, r))
            l += 1
        else:
            break
    min_ns[N - r - 2][2] = psum(0, l)
    min_ns[N - r - 2][3] = psum(l, r)

ans = INF
for l in min_ns:
    ans = min(ans, max(l) - min(l))
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from itertools import accumulate

N = int(input())
A = list(map(int, input().split()))
Acum = list(accumulate([0] + A))

def cumsum(left, right):
    # [i, j)
    return Acum[right] - Acum[left]

def find_best_cut(left, right, prev):
    prev = max(prev, left+1)
    now = prev
    res = now
    best = abs(cumsum(left, prev) - cumsum(prev, right))
    while True:
        now += 1
        score = abs(cumsum(left, now) - cumsum(now, right))
        if score < best:
            best = score
            res = now
        else:
            return res

left = 0
right = 0
best = float('inf')
for center in range(1, N-1):
    # 左しゃくとり
    left = find_best_cut(0, center, left)
    right = find_best_cut(center, N, right)
    
    t = [cumsum(0, left), cumsum(left, center), cumsum(center, right), cumsum(right, N)]
    score = max(t) - min(t)
    if score < best:
        best = score
    
print(best)

Submission status: Accepted

Solution code:
#from collections import deque
from bisect import bisect_left
N=int(input())
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]

num=10**14
for i in range(2,N-1):
    ans=[]
    x=(A[i]+A[0])/2
    j=bisect_left(A,x)
    #print(j,x)
    if A[j]-x>x-A[j-1]:
        j-=1
    ans+=[A[j]-A[0],A[i]-A[j]]
    y=(A[N]+A[i])/2
    k=bisect_left(A,y)
    #print(k,y)
    if A[k]-y>y-A[k-1]:
        k-=1
    ans+=[A[N]-A[k],A[k]-A[i]]
    #print(ans)
    t=max(ans)-min(ans)
    num=min(num,t)
print(num)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    n = I()
    a = LI()
    b = [a[0]]
    for c in a[1:]:
        b.append(b[-1]+c)
    d = [0] * n
    d[-1] = a[-1]
    for i in range(n-2,-1,-1):
        d[i] = d[i+1] + a[i]

    g = [[] for _ in range(n)]
    g[0] = [0,inf]
    j = 0
    for i in range(1,n):
        t = b[i]
        k = abs((b[i] - b[j]) - b[j])
        while j < i-1 and k > abs((b[i] - b[j+1]) - b[j+1]):
            k = abs((b[i] - b[j+1]) - b[j+1])
            j += 1
        g[i].append(b[j])
        g[i].append(b[i] - b[j])

    g[-1] = [0,inf]
    g[-2] = [0,inf]
    j = n-1
    for i in range(n-2,-1,-1):
        t = d[i]
        k = abs((d[i] - d[j]) - d[j])
        while j > i+1 and k > abs((d[i] - d[j-1]) - d[j-1]):
            k = abs((d[i] - d[j-1]) - d[j-1])
            j -= 1
        g[i-1].append(d[i] - d[j])
        g[i-1].append(d[j])

    r = inf
    for i in range(n):
        t = max(g[i]) - min(g[i])
        if r > t:
            r = t

    return r



print(main())

Submission status: Accepted

Solution code:
from bisect import bisect_left
from itertools import accumulate

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

cumsum = list(accumulate(A))
cumsum.insert(0, 0)

ans = float('inf')
# 真ん中区切り全探索
for m in range(2, N-1):
    # 左
    Lmid = cumsum[m] / 2
    Lx = bisect_left(cumsum, Lmid)

    # 境界チェック
    if abs(Lmid - cumsum[Lx]) > abs(Lmid - cumsum[Lx-1]):
        Lx -= 1


    # 右
    Rmid = (cumsum[m] + cumsum[N]) / 2
    Rx = bisect_left(cumsum, Rmid)

    # 境界チェック
    if abs(Rmid - cumsum[Rx]) > abs(Rmid - cumsum[Rx-1]):
        Rx -= 1

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

print(ans)

Submission status: Accepted

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

cums = [0]
for a in src:
    cums.append(cums[-1] + a)

ps = [None] * (N+1)
qs = [None] * (N+1)
rs = [None] * (N+1)
ss = [None] * (N+1)

l = 1
for r in range(2,N-1):
    p1 = cums[l]
    q1 = cums[r] - cums[l]
    d1 = abs(p1-q1)
    while l < r:
        p2 = cums[l+1]
        q2 = cums[r] - cums[l+1]
        d2 = abs(p2-q2)
        if d2 > d1: break
        l += 1
        p1,q1,d1 = p2,q2,d2
    ps[r] = p1
    qs[r] = q1

r = N-1
for l in range(N-2,1,-1):
    r1 = cums[r] - cums[l]
    s1 = cums[N] - cums[r]
    d1 = abs(r1-s1)
    while l < r:
        r2 = cums[r-1] - cums[l]
        s2 = cums[N] - cums[r-1]
        d2 = abs(r2-s2)
        if d2 > d1: break
        r -= 1
        r1,s1,d1 = r2,s2,d2
    rs[l] = r1
    ss[l] = s1

ans = cums[-1] * 999
for p,q,r,s in zip(ps,qs,rs,ss):
    if p is None: continue
    tmp = max(p,q,r,s) - min(p,q,r,s)
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))
S = C[N]
f = lambda x:abs(x[0]-x[1])
def it():
  k1 = 1
  k2 = 3
  for i in range(2,N-1):
    ci = C[i]
    k1 = bisect(C, ci//2, lo=k1,hi=i)
    a,b = min(((ci-c,c) for c in (C[k1-1],C[k1])), key=f)
    k2 = bisect(C, (S+ci)//2, lo=k2,hi=N)
    c,d = min(((S-c,c-ci) for c in (C[k2-1],C[k2])), key=f)
    yield max(a,b,c,d)-min(a,b,c,d)

print(min(it()))

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))
S = C[N]

def it():
  k1 = 1
  k2 = 3
  for i in range(2,N-1):
    ci = C[i]
    k1 = bisect(C, ci//2, lo=k1,hi=i)
    _,a,b = min((abs(ci-2*c),ci-c,c) for c in (C[k1-1],C[k1]))
    k2 = bisect(C, (S+ci)//2, lo=k2,hi=N)
    _,c,d = min((abs(ci+S-2*c),S-c,c-ci) for c in (C[k2-1],C[k2]))
    yield max(a,b,c,d)-min(a,b,c,d)

print(min(it()))

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))
S = C[N]

def solve(x):
  cx = C[x]
  k = bisect(C, cx//2, lo=1,hi=x)
  _,a,b = min((abs(cx-2*c),cx-c,c) for c in (C[k-1],C[k]))
  k = bisect(C, (S+cx)//2, lo=x+1,hi=N)
  _,c,d = min((abs(cx+S-2*c),S-c,c-cx) for c in (C[k-1],C[k]))
  L = (a,b,c,d)
  return max(L)-min(L)

print(min(solve(i) for i in range(2,N-1)))

Submission status: Accepted

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

def left_list(a):
  i = 1
  left_sum = a[0] + a[1]
  left_1 = a[0]
  left = []
  left.append([a[0], a[1]])
  for j in range(2, n-2):
    left_sum += a[j]
    while 2 * (left_1 + a[i]) <= left_sum:
      left_1 += a[i]
      i += 1
    diff = left_sum - 2 * left_1
    diff_1 = 2 * (left_1 + a[i]) - left_sum
    if diff_1 < diff:
      left_1 += a[i]
      i += 1
    left.append([left_1, left_sum-left_1])
  # print(left)
  return left

left_t = left_list(a)
a = a[::-1]
right_t = left_list(a)
right_t = right_t[::-1]
res = sum(a)
for x, y in zip(left_t, right_t):
  diff = max(max(x), max(y)) - min(min(x), min(y))
  if diff < res:
    res = diff
print(res)