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[i]+A[i])

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

        if S[c_before] - S[b] > S[N] - S[c_before]:
                c=c_before
        else:
                for i in range(c_before,N):
                        if S[i] - S[b] > S[N] - S[i]:
                                if abs((S[N]-S[i-1]) - (S[i-1]-S[b])) < abs((S[N]-S[i]) - (S[i]-S[b])):
                                        c=i-1
                                        c_before = i-1
                                        break
                                else:
                                        c=i
                                        c_before = i
                                        break
                else:
                        c=N-1
                        c_before = N-1

        ans_tmp.append(max(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])-min(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0]))

print(min(ans_tmp))

Submission status: Accepted

Solution code:
from itertools import accumulate


def run(n, a):
    # sum_a = [sum(a[0:i+1]) for i in range(n)]
    sum_a = list(accumulate(a))
    li = 0
    ri = 2
    t = sum_a[-1]
    diff = sum_a[-1]
    # 真ん中の切れ込みを順に変更
    # 左の切れ込みの位置はiに対して単調増加
    # 左の切れ込みで真ん中の項を移動するかどうかは、
    # 真ん中の項を除いて、小さい方に入れる
    # ただし単調増加なので、左の切れ込みの左側が
    # 小さいときに真ん中を左の切れ込みの左側に入れる
    # 右も同様に考える
    for i in range(1, n-2):
        while sum_a[i] > sum_a[li+1] + sum_a[li]:
            li += 1
        while t + sum_a[i] > sum_a[ri+1] + sum_a[ri]:
            ri += 1
        p = sum_a[li]
        q = sum_a[i] - p
        r = sum_a[ri] - q - p
        s = t - sum_a[ri]
        diff = min(diff, max(p, q, r, s) - min(p, q, r, s))
    return diff


def read_line():
    n = int(input())
    a = list(map(int, input().split()))
    return (n, a)


def main():
    n, a = read_line()
    print(run(n, a))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

i, j, k = 1, 2, 3
B, C, D, E = A[0], A[1], A[2], sum(A[3:])

result = 10 ** 20

while 1:

    while 1:   
        newB, newC = B + A[i], C - A[i]
        if abs(B - C) < abs(newB - newC):
            break
        i += 1
        B, C = newB, newC

    while 1:   
        newD, newE = D + A[k], E - A[k]
        if abs(D - E) < abs(newD - newE):
            break
        k += 1
        D, E = newD, newE

    r = max(B, C, D, E) - min(B, C, D, E)
    result = min(result, r)

    C, D = C + A[j], D - A[j]
    j += 1
    if j == N - 1:
        break
    
print(result)

Submission status: Accepted

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

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

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

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

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

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

print(res)

Submission status: Accepted

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

n = int(input())
xs = [int(x) for x in input().split()]
ys = list(accumulate(xs))
zs, total = ys[:-1], ys[-1]

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

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

    minn, _, _, maxx = sorted((a,b,c,d))
    v.append(maxx - minn)

print(min(v) if v else max(xs) - min(xs))

Submission status: Accepted

Solution code:
from itertools import accumulate
import bisect

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

def solve(x):
  cnt=S[x]
  L=bisect.bisect_left(S,cnt/2)
  R=bisect.bisect_left(S,(cnt+S[N-1])/2)
  L2=L-1
  R2=R-1
  res=10**10
  if R < N:
    ans=[S[L],cnt-S[L],S[R]-cnt,S[N-1]-S[R]]
    ans2=[S[L2],cnt-S[L2],S[R]-cnt,S[N-1]-S[R]]
    res=min(res,max(ans)-min(ans),max(ans2)-min(ans2))
  if R2 < N:
    ans3=[S[L],cnt-S[L],S[R2]-cnt,S[N-1]-S[R2]]
    ans4=[S[L2],cnt-S[L2],S[R2]-cnt,S[N-1]-S[R2]]
    res=min(res,max(ans3)-min(ans3),max(ans4)-min(ans4))
  return res

res=10**10
for i in range(N):
  a=solve(i)
  res=min(res,a)
print(res)

Submission status: Accepted

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

N = int(input())
A = [int(t) for t in input().split()]
if len(A) != N: raise

def left_sum_cut(A):
    """左部分和と左部分列を均等に分ける位置を返す"""
    A = list(A)

    # 左部分列の和
    leftsum = [0] * len(A)
    leftsum[0] = A[0]
    for i in range(1, len(A)):
        leftsum[i] = leftsum[i-1] + A[i]

    # 左部分列を均等に分ける位置
    leftcut = [0] * len(A)
    leftcut[0] = None
    leftcut[1] = 0
    for i in range(2, len(A)):
        j = leftcut[i-1]
        m = float('inf')
        while j <= i - 1:
            suml = leftsum[j]
            sumr = leftsum[i] - suml
            if m <= abs(suml - sumr): break
            m = abs(suml - sumr)
            j += 1
        leftcut[i] = j - 1
    return leftsum, leftcut

leftsum,  leftcut  = left_sum_cut(A)
rightsum, rightcut = left_sum_cut(reversed(A))

# 中央の切断位置
m = float('inf')
for i in range(1, N - 2):
    P = leftsum[leftcut[i]]
    Q = leftsum[i] - P
    S = rightsum[rightcut[N - 1 - (i + 1)]]
    R = rightsum[N - 1 - (i + 1)] - S
    m = min(max(P, Q, R, S) - min(P, Q, R, S), m)
print(m)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate
n=int(input())
a=list(map(int, input().split()))
acc=list(accumulate(a))
left=0; center=1; right=2
ans=float('inf')
score=[acc[left], acc[center]-acc[left], acc[right]-acc[center], acc[n-1]-acc[right]]
nextS=[acc[left+1], acc[center]-acc[left+1], acc[right+1]-acc[center], acc[n-1]-acc[right+1]]
for center in range(1,n-1):
    while abs(score[1]-score[0]) > abs(nextS[1]-nextS[0]):
        left+=1
        score[0]+=a[left]
        score[1]-=a[left]
        nextS[0]+=a[left+1]
        nextS[1]-=a[left+1]
    while abs(score[3]-score[2]) > abs(nextS[3]-nextS[2]):
        right+=1
        score[2]+=a[right]
        score[3]-=a[right]
        nextS[2]+=a[right+1]
        nextS[3]-=a[right+1]
    ans=min(ans, max(score)-min(score))
    score[1]+=a[center+1]
    score[2]-=a[center+1]
    nextS[1]+=a[center+1]
    nextS[2]-=a[center+1]
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n=int(input())
a=list(map(int, input().split()))
acc=list(accumulate(a))
left=0; right=2
ans=float('inf')
for center in range(1,n-1):
    while abs(acc[center]-acc[left]-acc[left]) > abs(acc[center]-acc[left+1]-acc[left+1]):
        left+=1 
    while abs(acc[n-1]-acc[right]-(acc[right]-acc[center])) > abs(acc[n-1]-acc[right+1]-(acc[right+1]-acc[center])):
        right+=1
    score=acc[left], acc[center]-acc[left], acc[right]-acc[center], acc[n-1]-acc[right]
    ans=min(ans, max(score)-min(score))

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n=int(input())
a=list(map(int, input().split()))
acc=list(accumulate(a))
sumA=acc[-1]
cut=[0, 1, 2, len(a)-1]
score=[acc[cut[0]], acc[cut[1]]-acc[cut[0]], acc[cut[2]]-acc[cut[1]], acc[cut[3]]-acc[cut[2]]]
ans=max(score)-min(score)
for i in range(1,len(a)-1):
    cut[1]=i    
    while abs(acc[cut[1]]-acc[cut[0]]-acc[cut[0]]) > abs(acc[cut[1]]-acc[cut[0]+1]-acc[cut[0]+1]):
        cut[0]+=1 
    while abs(acc[cut[3]]-acc[cut[2]]-(acc[cut[2]]-acc[cut[1]])) > abs(acc[cut[3]]-acc[cut[2]+1]-(acc[cut[2]+1]-acc[cut[1]])):
        cut[2]+=1
    score=[acc[cut[0]], acc[cut[1]]-acc[cut[0]], acc[cut[2]]-acc[cut[1]], acc[cut[3]]-acc[cut[2]]]
    ans=min(ans, max(score)-min(score))

print(ans)

Submission status: Accepted

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

ans = float('inf')
cumsum = []
sum = 0
for a in A:
    sum += a
    cumsum.append(sum)

l = 0
r = 2
for m in range(1, N-2):
    # left
    P = cumsum[l]
    Q = cumsum[m] - cumsum[l]
    dist = abs(P-Q)
    while True:
        P_ = cumsum[l+1]
        Q_ = cumsum[m] - cumsum[l+1]
        dist_ = abs(P_ - Q_)
        if dist < dist_: break
        P, Q, dist = P_, Q_, dist_
        l += 1

    # right
    R = cumsum[r] - cumsum[m]
    S = cumsum[-1] - cumsum[r]
    dist = abs(S-R)
    while True:
        R_ = cumsum[r+1] - cumsum[m]
        S_ = cumsum[-1] - cumsum[r+1]
        dist_ = abs(R_ - S_)
        if dist < dist_: break
        R, S, dist = R_, S_, dist_
        r += 1

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

Submission status: Accepted

Solution code:
from itertools import *
n=int(input())
sumA=[0]+list(accumulate(map(int,input().split())))
def check(l,m,r):
    if m==r:return False
    tmp=sumA[r]+sumA[l]
    return abs(tmp-sumA[m+1]*2)<abs(tmp-sumA[m]*2)
res=float('inf')
li,ri=1,3
for mid in range(2,n-1):
    while check(0,li,mid):li+=1
    while check(mid,ri,n):ri+=1
    x=sorted([sumA[li],sumA[mid]-sumA[li],sumA[ri]-sumA[mid],sumA[n]-sumA[ri]])
    tmp=x[3]-x[0]
    if tmp<res:res=tmp
print(res)

Submission status: Accepted

Solution code:
##https://beta.atcoder.jp/contests/abc102/submissions/2779056
n = int(input())
a = list(map(int, input().split()))
s = [a[0]]
for i in range(n-1):
    s.append(s[i] + a[i+1])
ans = s[n-1]

##i,j,kは左側の区間の右端
##iは1からN-3まで
j = 0
k = 2             
for i in range(1, (n - 3) + 1):
    ##BC(i)DE
    ##BCの区間[0, i]: 最低でも2要素→0,1を取るのでi=1から
    ##DEの区間[i+1, N-1]: 最低でも2要素→N-2, N-1を取るので、i+1=N-2よりi=N-3まで

    ##B(j)C(i)DE
    #Bの区間[0, j]
    #Cの区間[j+1, i]
    ##sumB = s[j]
    ##sumC = s[i] - s[j]
    while abs(s[i] - 2 * s[j]) > abs(s[i] - 2 * s[j+1]):
        j += 1

    ##B(j)C(i)D(k)E
    #Dの区間[i+1, k]
    #Eの区間[k+1, N-1]
    ##sumD = s[k] - s[i]
    ##sumE = s[N-1] - s[k]
    while abs(s[n-1] - 2 * s[k] + s[i]) > abs(s[n-1] - 2 * s[k+1] + s[i]):
        k += 1
             
    pqrs = list((s[j],s[i]-s[j],s[k]-s[i],s[n-1]-s[k]))
    ans = min(ans, max(pqrs) - min(pqrs))
print(ans)

Submission status: Accepted

Solution code:
def d_equal_cut(N, A):
    import itertools
    import bisect

    cumsum = [0] + list(itertools.accumulate(A))  # Aの累積和

    def get_sum(left, right):
        # A[left]~A[right]の総和を得る
        return cumsum[right+1] - cumsum[left]

    def get_optimum_division(left, right):
        # A[left]~A[right]を、前後の総和の差を最小にするように分解する
        total = get_sum(left, right)
        # A[left]~A[right]の総和の半分以上になる要素の要素番号を求める
        # left, right はAの要素番号を指定しているので、
        # cumsumのために[0]をつけた分+1して、最後に-1している
        mid = bisect.bisect_right(
            cumsum, cumsum[left] + total/2, left+1, right+1) - 1

        # midがleftまたはrightと一致しないとき、真ん中の切り方は2通りある
        # (真ん中の要素を左側に入れるか右側に入れるか)ので、
        # 両方計算して差が小さな方を採用する
        diff1, diff2 = float('inf'), float('inf')
        if mid != left:
            sum_L1 = get_sum(left, mid-1)
            sum_R1 = get_sum(mid, right)
            diff1 = abs(sum_L1 - sum_R1)
        if mid != right:
            sum_L2 = get_sum(left, mid)
            sum_R2 = get_sum(mid+1, right)
            diff2 = abs(sum_L2 - sum_R2)
        return [sum_L1, sum_R1] if diff1 <= diff2 else [sum_L2, sum_R2]

    # 真ん中の区切りを全通り試す
    ans = float('inf')
    # 0~mid_cut番の要素を「左側」、mid_cut~N-1番の要素を「右側」とする
    # Aの1番からN-3番までが「左と右を分ける仕切り」になれる
    # (0, N-2, N-1番をその仕切りにすると、空な部分列ができてしまう)
    for mid_cut in range(1, (N-3) + 1):
        total = []
        total.extend(get_optimum_division(0, mid_cut))
        total.extend(get_optimum_division(mid_cut+1, N-1))
        ans = min(ans, abs(max(total) - min(total)))
    return ans

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

Submission status: Accepted

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

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

L = 1
r = 3
ans = 10**18
        
for i in range(2,N-1):
    while L + 1 < i and abs(pre[L+1] - pre[i] + pre[L+1]) < abs(pre[L] - pre[i] + pre[L]):
        L += 1

    while r <= i or (r + 1 < N and abs(pre[r+1] - pre[i] - pre[N] + pre[r+1]) < abs(pre[r] - pre[i] - pre[N] + pre[r])):
        r += 1

    ans = min(ans,max(pre[L],pre[i]-pre[L],pre[r]-pre[i],pre[N]-pre[r]) - \
          min(pre[L],pre[i]-pre[L],pre[r]-pre[i],pre[N]-pre[r]))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
xs=[int(s) for s in input().split()]
for i in range(1,n):
    xs[i]+=xs[i-1]
xs_last=xs[n-1]
ans=xs_last
l=0
r=2
for c in range(1,n-2):
    xs_center=xs[c]
    while l<c-1:
        if xs_center<xs[l+1]*2:
            if (xs[l+1]+xs[l])<xs_center:
                l+=1
            break
        l+=1
    while r<n-2:
        if xs_last+xs_center<2*xs[r+1]:
            if (xs[r+1]+xs[r])<xs_last+xs_center:
                r+=1
            break
        r+=1
    pqrs=[xs[l],xs_center-xs[l],xs[r]-xs_center,xs_last-xs[r]]
    ans=min(ans,max(pqrs)-min(pqrs))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A_list = [int(elem) for elem in input().split(' ')]
assert N >= 4
assert len(A_list) == N

# cummulative sum
cuml_A_list = [0] * N
cuml_A_list[0] = A_list[0]
for i in range(1, N):
    cuml_A_list[i] = cuml_A_list[i-1] + A_list[i]

best_diff = max(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])\
        - min(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])

left_sep = 0
right_sep = 2

# time complexity: O(N)
for mid_sep in range(1, N - 2):
    left_sum = cuml_A_list[mid_sep - 1]
    right_sum = cuml_A_list[-1] - cuml_A_list[mid_sep - 1]

    while abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep]) > abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep + 1]):
        left_sep += 1
    while abs(cuml_A_list[-1] - 2*cuml_A_list[right_sep] + cuml_A_list[mid_sep]) > abs(cuml_A_list[-1] - 2*cuml_A_list[right_sep + 1] + cuml_A_list[mid_sep]):
        right_sep += 1
    diff = max(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])\
        - min(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])
    best_diff = min(best_diff, diff)
print(best_diff)

Submission status: Accepted

Solution code:
import numpy
from bisect import bisect_left, bisect_right
from itertools import accumulate

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

ans=A[N-1]
for m in range(2,N-1):
  sum_left=A[m-1]
  i=bisect_left(A,sum_left/2)
  sum1=A[i]
  if i!=0:
    if A[i]+A[i-1]>sum_left:
      sum1=A[i-1]
  sum2=sum_left-sum1

  sum_right=A[N-1]-sum_left
  i=bisect_left(A,sum_left+sum_right/2)
  sum3=A[i]-sum_left
  if i!=m:
    if A[i]+A[i-1]-2*sum_left>sum_right:
      sum3=A[i-1]-sum_left
  sum4=sum_right-sum3
  max_sum=max(sum1,sum2,sum3,sum4)
  min_sum=min(sum1,sum2,sum3,sum4)
  dif=max_sum-min_sum
  if dif<ans:
    ans=dif

print(ans)

Submission status: Accepted

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

from itertools import accumulate
accum = list(accumulate(a))

i_left = 0
i_right = 2
ans = 10**18
for i in range(1, n-2):
    while True:
        p = accum[i_left]
        q = accum[i] - p
        p_new = accum[i_left+1]
        q_new = accum[i] - p_new
        if abs(p_new - q_new) < abs(p - q):
            i_left += 1
        else:
            break
    while True:
        r = accum[i_right] - accum[i]
        s = accum[-1] - accum[i_right]
        r_new = accum[i_right+1] - accum[i]
        s_new = accum[-1] - accum[i_right+1]
        if abs(r_new - s_new) < abs(r - s):
            i_right += 1
        else:
            break

    # print(p, q, r, s)
    diff = max([p, q, r, s]) - min([p, q, r, s])
    ans = min(ans, diff)

print(ans)

Submission status: Accepted

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

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

ans=A_sum[N-1]
for m in range(2,N-1):
  sum_left=A_sum[m-1]
  i=bisect_left(A_sum,sum_left/2)
  sum1=A_sum[i]
  if i!=0:
    if A_sum[i]+A_sum[i-1]>sum_left:
      sum1=A_sum[i-1]
  sum2=sum_left-sum1

  sum_right=A_sum[N-1]-sum_left
  i=bisect_left(A_sum,sum_left+sum_right/2)
  sum3=A_sum[i]-sum_left
  if i!=m:
    if A_sum[i]+A_sum[i-1]-2*sum_left>sum_right:
      sum3=A_sum[i-1]-sum_left
  sum4=sum_right-sum3
  max_sum=max(sum1,sum2,sum3,sum4)
  min_sum=min(sum1,sum2,sum3,sum4)
  dif=max_sum-min_sum
  if dif<ans:
    ans=dif

print(ans)

Submission status: Accepted

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

s=[a[0]]
for i in range(n-1):
	s.append(s[i]+a[i+1])
ans=s[n-1]
j=0
k=2
for i in range(1,n-2):
	while abs(s[i]-2*s[j]) > abs(s[i]-2*s[j+1]):
		j=j+1
	while abs(s[n-1]-2*s[k]+s[i]) > abs(s[n-1]-2*s[k+1]+s[i]):
		k=k+1
	t=max(s[j],s[i]-s[j],s[k]-s[i],s[n-1]-s[k])-min(s[j],s[i]-s[j],s[k]-s[i],s[n-1]-s[k])
	if ans>t:
		ans=t
print(ans)

Submission status: Accepted

Solution code:
def solve(xs, n):
    for i in range(1, n):
        xs[i] += xs[i - 1]
    l, r = (0, 2)
    xs_last = xs[n - 1]
    ans = xs_last
    for c in range(1, n - 2):
        xs_center = xs[c]
        while l < c - 1:
            if xs_center < 2 * xs[l + 1]:
                if (xs[l + 1] + xs[l]) < xs_center:
                    l += 1
                break
            l += 1
        while r < n - 2:
            if xs_last + xs_center < 2 * xs[r + 1]:
                if (xs[r + 1] + xs[r]) < xs_last + xs_center:
                    r += 1
                break
            r += 1
        pqrs = (xs[l], xs_center - xs[l], xs[r] - xs_center, xs_last - xs[r])
        ans = min(ans, max(pqrs) - min(pqrs))
    return ans

if __name__ == "__main__":
    n = int(input())
    xs = [int(s) for s in input().split()]
    print(solve(xs, n))

Submission status: Accepted

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

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

ts = list(accumulate(a))+[0]
r = 0

def calc(st, ed):
    t0 = ts[ed-1] - ts[st-1]
    i1 = bisect_left(ts, (ts[ed-1]+ts[st-1])/2, st+1, ed-1)
    t11 = ts[i1-1] - ts[st-1]
    t12 = t0 - t11
    t21 = ts[i1] - ts[st-1]
    t22 = t0 - t21
    if abs(t22-t21) > abs(t12-t11):
        return t11, t12
    else:
        return t21, t22

ans = 10**18
for i in range(2, n-1):
    r1, r2 = calc(0, i)
    r3, r4 = calc(i, n)
    # print(r1, r2, r3, r4)
    diff = max([r1, r2, r3, r4]) - min([r1, r2, r3, r4])
    ans = min(ans, diff)

print(ans)

Submission status: Accepted

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

from itertools import accumulate
from bisect import bisect_left, bisect_right

ts = list(accumulate(A)) + [0]

r = 0

def calc(st, ed):
    t0 = ts[ed-1] - ts[st-1]
    i1 = bisect_left(ts, (ts[ed-1] + ts[st-1]) / 2, st + 1, ed - 1)
    t11 = ts[i1-1] - ts[st-1]
    t12 = t0 - t11
    t21 = ts[i1] - ts[st-1]
    t22 = t0 - t21
    #print("*", st, ed, t0, i1, t11, t12, t21, t22)
    if abs(t22-t21) > abs(t12-t11):
        return t11, t12
    else:
        return t21, t22

result = 999999999999999999999999
for i in range(2, N-1):
    r1, r2 = calc(0, i)
    r3, r4 = calc(i, N)
    #print(r1, r2, r3, r4)
    r = max(r1, r2, r3, r4) - min(r1, r2, r3, r4)
    result = min(result, r)

print(result)

Submission status: Accepted

Solution code:
from inspect import currentframe

def chkprint(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

from functools import reduce
from math import floor, ceil

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

left = 1
center = 2
right = 3

res = 10**16



p = sum(A[0:left])
q = sum(A[left:center])
r = sum(A[center:right])
s = sum(A[right:])

# print(A)

while center <= N - 2:
  while True:
    if abs(p-q) < abs(p-q+2*A[left]):
      break

    if left == center-1:
      break

    p += A[left]
    q -= A[left]
    left += 1

  while True:
    if abs(r-s) < abs(r-s+2*A[right]):
      break

    if right == N-1:
      break

    r += A[right]
    s -= A[right]
    right += 1

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

  # print(A[0:left], A[left:center], A[center:right], A[right:], res)
  q += A[center]
  r -= A[center]
  center += 1

print(res)

Submission status: Runtime Error

Solution code:
N=int(input())
L=list(map(int,input().split()))
c=sum(L)/4
sums=L[0]
i=1
ans=list()
while True:
  sums+=L[i]
  if sums>c:
    if abs(sums-c)>abs(sums-c-L[i]):
      ans.append(sums-L[i])
      sums=L[i]
      if len(ans)==3:
        ans.append(sum(L[i:]))
        break
    else:
      ans.append(sums)
      sums=L[i+1]
      i+=1
      if len(ans)==3:
        ans.append(sum(L[i+1:]))
        break
  i+=1
  if i==N:
    ans.append(sums)
    break
print(max(ans)-min(ans))

Submission status: Runtime Error

Solution code:
def divide(A):
    sum_a = sum(A)
    a_2 = sum_a/2
    left = []
    tmp = []
    for i,v in enumerate(A):
        tmp = left.copy()
        tmp.append(v)
        if i == len(A)-1:
            return A[:i],A[i:]
        if sum(tmp) > a_2:
            if abs(sum(tmp) - sum(A[i+1:])) > abs(sum(left) - sum(A[i:])):
                return left,A[i:]
            else:
                return tmp,A[i+1:]
        else:
            left.append(v)


import numpy as np
import math
N = int(input())
A = list(map(int, input().split()))
left, right = divide(A)
left_left, left_right = divide(left)
right_left, right_right = divide(right)
sum_list = [sum(left_left),sum(left_right),sum(right_left),sum(right_right)]
a = max(sum_list)-min(sum_list)

left = left + [right[0]]
right = right[1:]
left_left, left_right = divide(left)
right_left, right_right = divide(right)
sum_list = [sum(left_left),sum(left_right),sum(right_left),sum(right_right)]
b = max(sum_list)-min(sum_list)

right = left[-2:]+right
left = left[:-2]
left_left, left_right = divide(left)
right_left, right_right = divide(right)
sum_list = [sum(left_left),sum(left_right),sum(right_left),sum(right_right)]
c = max(sum_list)-min(sum_list)

print(min(a,b,c))

Submission status: Runtime Error

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

N = int(readline())
A = [0] + list(map(int,readline().split()))

sumA = [0] * len(A)
for i in range(1,len(A)):
  sumA[i] = sumA[i - 1] + A[i]
  
# 真ん中の分割点を決める
import bisect
mid = bisect.bisect_left(sumA, sumA[-1]//2)
ans = 10 ** 18
for i in range(max(0, mid - 1),min(mid + 2,len(sumA))):
  front = sumA[:i]
  back = list(map(lambda x:x - front[-1], sumA[i:]))
  if len(front) < 2 or len(back) < 2:
    continue
  front_mid = bisect.bisect_left(front, front[-1] // 2)
  back_mid = bisect.bisect_left(back, back[-1] // 2)
  for j in range(max(0, front_mid - 1), min(front_mid + 2, len(front))):
    P = front[j]
    Q = front[-1] - front[j]
    for k in range(max(0,back_mid - 1), min(back_mid + 2, len(back))):
      R = back[k]
      S = back[-1] - back[k]
      diff = max(P,Q,R,S) - min(P,Q,R,S)
      if ans > diff:
        ans = diff
      
print(ans)

Submission status: Runtime Error

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

N = int(readline())
A = [0] + list(map(int,readline().split()))

sumA = [0] * len(A)
for i in range(1,len(A)):
  sumA[i] = sumA[i - 1] + A[i]
  
# 真ん中の分割点を決める
import bisect
mid = bisect.bisect_left(sumA, sumA[-1]//2)
ans = 10 ** 18
for i in range(max(0, mid - 1),min(mid + 2,len(sumA))):
  front = sumA[:i]
  back = list(map(lambda x:x - front[-1], sumA[i:]))
  front_mid = bisect.bisect_left(front, front[-1] // 2)
  back_mid = bisect.bisect_left(back, back[-1] // 2)
  for j in range(max(0, front_mid - 1), min(front_mid + 2, len(front))):
    P = front[j]
    Q = front[-1] - front[j]
    for k in range(max(0,back_mid - 1), min(back_mid + 2, len(back))):
      R = back[k]
      S = back[-1] - back[k]
      diff = max(P,Q,R,S) - min(P,Q,R,S)
      if ans > diff:
        ans = diff
      
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
sl=[a[0]]
for i in range(1,n):
    sl.append(sl[-1]+a[i])
b=a[::-1]
sr=[b[0]]
for i in range(1,n):
    sr.append(sr[-1]+b[i])
from bisect import bisect_left,bisect_right
ans=[]
for i in range(1,n-3):
    #左側決める
    l=sl[i]
    kl=l//2
    lsl,lsr=bisect_left(a,kl,hi=i),bisect_right(a,kl,hi=i)-1
    if lsr<0:
        lsr+=1
    if abs(sl[lsl]-(l-sl[lsl]))<abs(sl[lsr]-(l-sl[lsr])):
        candl=[sl[lsl],l-sl[lsl]]
    else:
        candl=[sl[lsr],l-sl[lsr]]
    #右側決める
    r=sr[n-(i+1)-1]
    kr=r//2
    rsl,rsr=bisect_left(b,kr,hi=n-(i+1)-1),bisect_right(b,kr,hi=n-(i+1)-1)-1
    if rsr<0:
        rsr+=1
    if abs(sr[rsl]-(r-sr[rsl]))<abs(sr[rsr]-(r-sr[rsr])):
        candr=[sr[rsl],r-sr[rsl]]
    else:
        candr=[sr[rsr],r-sr[rsr]]
    ans.append(max(candl+candr)-min(candl+candr))
print(min(ans))

Submission status: Runtime Error

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]

def calc_ans(l, m, r):
    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]])
    return num_list[3] - num_list[0]

l, m, r = 1, 2, 3
ans = calc_ans(l, m, r)
for m in range(2, n - 2):
    print(m, a_list[:m], a_list[m:])

    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
    
    ans_temp = calc_ans(l, m, r)
    if ans_temp < ans:
        ans = ans_temp
print(ans)

Submission status: Runtime Error

Solution code:
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: Runtime Error

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)