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: Wrong Answer

Solution code:
import sys


def cumsum(li):
    ret = [0]
    sum = 0
    for i in li:
        sum += i
        ret.append(sum)
    return ret


sys.setrecursionlimit(10000)
INF = float('inf')

N = int(input())
A = list(map(int, input().split()))
# 最初が0
cs = cumsum(A)
assert len(cs) == N + 1


def calc_diff(d1, d2, d3):
    diffs = [
        cs[d1] - cs[0],
        cs[d2] - cs[d1],
        cs[d3] - cs[d2],
        cs[N] - cs[d3]
    ]
    return max(diffs) - min(diffs)


# dp1[d2]: 2 つ目に切る位置を d2 としたときに最適な、1 つ目に切る位置
dp1 = [0 for _ in range(N)]
dp1[2] = 1
for d2 in range(3, N - 1):
    d1 = dp1[d2 - 1]
    while abs((cs[d2] - cs[d1]) - (cs[d1] - cs[0])) > abs((cs[d2] - cs[d1 + 1]) - (cs[d1 + 1] - cs[0])):
        d1 += 1
    dp1[d2] = d1

# dp2[d3]: 3 つ目に切る位置を d3 としたときに最適な、2 つ目に切る位置
dp2 = [0 for _ in range(N)]
dp2[3] = 2
ans = calc_diff(1, 2, 3)
for d3 in range(4, N):
    d2 = dp2[d3 - 1]
    if calc_diff(dp1[d2], d2, d3) > calc_diff(dp1[d2 + 1], d2 + 1, d3):
        d2 += 1
    dp2[d3] = d2
    ans = min(ans, calc_diff(dp1[d2], d2, d3))

print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int, list(input().split()))) + [0]

w = 0
for i in range(N+1):
    p = w
    w += A[i]
    A[i] = p

S = [x for x in range(5)]
S[4] = N
KEI = [0] * 4
SA = -1

x = 0
for x in range(2, N-1):

    S[2] = x

    for offset in range(1, 4, 2):
        left = S[offset-1]
        right = S[offset+1]
        allvalue = A[right] - A[left]

        while right - left > 1:
            middle = (left + right) // 2
            if allvalue - ((A[middle] - A[S[offset-1]]) * 2 - (A[middle] - A[middle-1])) < 0:
                right = middle
            elif allvalue - ((A[middle] - A[S[offset-1]]) * 2 + (A[middle+1] - A[middle])) < 0:
                break
            else:
                left = middle

        S[offset] = middle

    for x in range(4):
        KEI[x] = A[S[x+1]] - A[S[x]]

    w = max(KEI) - min(KEI)
    if SA < 0:
        SA = w
    else:
        SA = min(SA, w)
        if w > SA:
            break

    #print((S, KEI, SA, w))


#print((A, KEI, S))
print(SA)

Submission status: Wrong Answer

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

b = 0
B = [0]
for i in A:
    b += i
    B.append(b)


answer = b*4
for cut2 in range(3, N):

    cut1 = max(2, bisect.bisect_right(B[:cut2], B[cut2]//2))

    cut3 = max(2, bisect.bisect_right(B[cut2-1:], (b - B[cut2-1])//2+B[cut2-1])) + cut2-1

    S = [B[cut1-1], B[cut2-1]-B[cut1-1], B[cut3-1]-B[cut2-1], b-B[cut3-1]]
    answer = min(answer, max(S)-min(S))

print(answer)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate as acc
from bisect import bisect_left as bl

def ans(n):
    tmp=0
    for i in range(N):
        tmp+=abs(a[i]-a[n-1])
    return tmp


N=int(input())
a=list(map(int,input().split()))
a=list(acc(a))

ans=10**18
for j in range(1,N-2):
    x=a[j]/2
    p=bl(a,x)
    if p==j: p-=1
    elif p>0 and x-a[p-1]<a[p]-x: p-=1

    y=(a[j]+a[N-1])/2

    q=bl(a,y)
    if q==N-1: q-=1
    elif q>j+1 and x-a[q-1]<a[q]-x: q-=1

    P,Q,R,S=a[p], a[j]-a[p], a[q]-a[j], a[N-1]-a[q]
    ans=min(ans, max(P,Q,R,S)-min(P,Q,R,S))

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate as acc
from bisect import bisect_left as bl

def ans(n):
    tmp=0
    for i in range(N):
        tmp+=abs(a[i]-a[n-1])
    return tmp


N=int(input())
a=list(map(int,input().split()))
a=list(acc(a))

ans=10**18
for j in range(1,N-2):
    x=a[j]/2
    p=bl(a,x)
    if p==j: p-=1
    elif p>0 and x-a[p-1]<a[p]-x: p-=1

    y=(a[j]+a[N-1])/2

    q=bl(a,y)
    if q==N-1: q-=1
    elif q>j+2 and x-a[q-1]<a[q]-x: q-=1

    P,Q,R,S=a[p], a[j]-a[p], a[q]-a[j], a[N-1]-a[q]
    ans=min(ans, max(P,Q,R,S)-min(P,Q,R,S))

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import itertools
INF = float("inf")


def solve(N: int, A: "List[int]"):

    wa = list(itertools.accumulate(A))
    # print(wa)
    m = INF
    # しゃくとり法
    atama1, atama2 = 0, 2
    # 真ん中iを固定する
    for i in range(1, N-3):
        # 0からi-1までの分割位置を決める
        # 最も前後の数列の和が近くなるように

        # 前の虫
        s0, s1 = wa[atama1], wa[i]-wa[atama1]
        for j in range(atama1+1, i):
            t0, t1 = wa[j], wa[i]-wa[j]
            # print(s0, s1, t0, t1, atama1)
            if t0 >= t1:
                if abs(s1-s0) >= abs(t1-t0):
                    s0, s1 = t0, t1
                    atama1 += 1
                break
            s0, s1 = t0, t1
            atama1 += 1
        # print(s0, s1, t0, t1)

        # 後ろの虫
        s2, s3 = wa[atama2]-wa[i], wa[N-1]-wa[atama2]
        for j in range(atama2+1, N):
            t2, t3 = wa[j]-wa[i], wa[N-1]-wa[j]
            if t2 >= t3:
                if abs(s3-s2) >= abs(t3-t2):
                    s2, s3 = t2, t3
                    atama2 += 1
                break
            s2, s3 = t2, t3
            atama2 += 1

        s = [s0, s1, s2, s3]
        # print(s)
        s.sort()
        m = min(s[3]-s[0], m)

    print(m)
    return


def main():

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import itertools
INF = float("inf")


def solve(N: int, A: "List[int]"):

    wa = list(itertools.accumulate(A))
    # print(wa)
    m = INF
    # しゃくとり法
    atama1, atama2 = 0, 2
    # 真ん中iを固定する
    for i in range(1, N-3):
        # 0からi-1までの分割位置を決める
        # 最も前後の数列の和が近くなるように

        # 前の虫
        s0, s1 = wa[atama1], wa[i]-wa[atama1]
        for j in range(atama1+1, i):
            t0, t1 = wa[j], wa[i]-wa[j]
            # print(s0, s1, t0, t1, atama1)
            if t0 >= t1:
                if abs(s1-s0) > abs(t1-t0):
                    s0, s1 = t0, t1
                    atama1 += 1
                break
            s0, s1 = t0, t1
            atama1 += 1
        # print(s0, s1, t0, t1)

        # 後ろの虫
        s2, s3 = wa[atama2]-wa[i], wa[N-1]-wa[atama2]
        for j in range(atama2+1, N):
            t2, t3 = wa[j]-wa[i], wa[N-1]-wa[j]
            if t2 >= t3:
                if abs(s3-s2) > abs(t3-t2):
                    s2, s3 = t2, t3
                    atama2 += 1
                break
            s2, s3 = t2, t3
            atama2 += 1

        s = [s0, s1, s2, s3]
        # print(s)
        s.sort()
        m = min(s[3]-s[0], m)

    print(m)
    return


def main():

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import itertools
INF = float("inf")


# class Bit:
#     def __init__(self, n):
#         self.size = n
#         self.tree = [0] * (n + 1)

#     def sum(self, i):
#         s = 0
#         while i > 0:
#             s += self.tree[i]
#             i -= i & -i
#         return s

#     def add(self, i, x):
#         while i <= self.size:
#             self.tree[i] += x
#             i += i & -i


def solve(N: int, A: "List[int]"):

    wa = list(itertools.accumulate(A))
    # print(wa)
    m = INF
    # 真ん中iを固定する
    for i in range(2, N-2):
        # 0からi-1までの分割位置を決める
        # 最も前後の値が近い場所
        s0, s1 = -INF, INF
        for j in range(1, i):
            t0, t1 = wa[j-1], wa[i-1]-wa[j-1]
            if abs(s1 - s0) > abs(t1 - t0):
                s0, s1 = t0, t1
        # print(s0, s1)
        # iからN-1までの分割位置を決める
        s2, s3 = -INF, INF
        for j in range(i, N):
            t2, t3 = wa[j]-wa[i-1], wa[N-1]-wa[j]
            if abs(s3 - s2) > abs(t3 - t2):
                s2, s3 = t2, t3
        # print(s2, s3)

        # 今回の悲しさ
        s = [s0, s1, s2, s3]
        s.sort()
        m = min(s[3]-s[0], m)

    print(m)
    return


def main():

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

S = [0]
for i,a in enumerate(A,1):
    S.append(S[i-1]+a)
Sn = S[-1]
ans = Sn

for j in range(2,N-1):
    tmpS = S[j]
    l,r = 1,j
    while l+1 < r:
        i = (l+r)//2
        if S[i] > tmpS/2:
            r = i
        else:
            l = i
    i = r
    i -= (tmpS - S[i] - S[i]) < (tmpS - S[i-1] - S[i-1])
    l,r = j+1,N
    while l+1 < r:
        k = (l+r)//2
        if S[k]-tmpS > (Sn-tmpS)/2:
            r = k
        else:
            l = k
    k = r
    k -= (Sn-S[k] - S[k] + tmpS) < (Sn - S[k-1] - S[k-1] + tmpS)
    P = (S[i],S[j]-S[i],S[k]-S[j],S[-1]-S[k])
    ans = min(ans,max(P)-min(P))
print(ans)

Submission status: Wrong Answer

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

S = [0]
for i,a in enumerate(A,1):
    S.append(S[i-1]+a)
Sn = S[-1]
ans = Sn

for j in range(2,N-1):
    tmpS = S[j]
    for i in range(1,j):
        if S[i] > tmpS/2:
            break
    i -= (tmpS - S[i] - S[i]) > (tmpS - S[i-1] - S[i-1])
    for k in range(j+1,N):
        if S[k]-tmpS > (Sn-tmpS)/2:
            break
    k -= (Sn-S[k] - S[k] + tmpS) > (Sn - S[k-1] - S[k-1] + tmpS)
    P = (S[i],S[j]-S[i],S[k]-S[j],S[-1]-S[k])
    ans = min(ans,max(P)-min(P))
print(ans)

Submission status: Wrong Answer

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

S = [0]
for i,a in enumerate(A,1):
    S.append(S[i-1]+a)

ans = S[-1]
for i in range(1,N-2):
    if S[i] > S[-1]/4:
        break
for i2 in set((max(1,i-1),i)):
    tmpS = S[i2]
    for j in range(i2+1,N-1):
        if S[j] - tmpS > S[-1]/4:
            break
    for j2 in set((max(i2+1,j-1),j)):
        tmpS = S[j2]
        for k in range(j2+1,N):
            if S[k] - tmpS > S[-1]/4:
                break
        for k2 in set((max(j2+1,k-1),k)):
            P = (S[i2],S[j2]-S[i2],S[k2]-S[j2],S[-1]-S[k2])
            ans = min(ans,max(P)-min(P))

print(ans)

Submission status: Wrong Answer

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

S = [0]
for i,a in enumerate(A,1):
    S.append(S[i-1]+a)

ans = S[-1]
for i in range(1,N-2):
    if S[i] > S[-1]/4:
        break
for i2 in set((max(1,i-1),i)):
    tmpS = S[i2]
    for j in range(i2+1,N-1):
        if S[j] - tmpS > S[-1]/4:
            break
    for j2 in set((max(i2,j-1),j)):
        tmpS = S[j2]
        for k in range(j2+1,N):
            if S[k] - tmpS > S[-1]/4:
                break
        for k2 in set((max(j2,k-1),k)):
            P = (S[i2],S[j2]-S[i2],S[k2]-S[j2],S[-1]-S[k2])
            ans = min(ans,max(P)-min(P))

print(ans)

Submission status: Wrong Answer

Solution code:
def solve(mid,l,r):
    global d
    x=a[mid]-a[l-1]
    y=a[r]-a[mid]
    t=abs(y-x)
    if t<=d:
        d=t
        return 1
    return 0
n,*a=map(int,open(0).read().split())
m=1e18
for i in range(n-1):
    a[i+1]+=a[i]
a=[0]+a
for i in range(2,n-1):
    ok=1
    ng=i
    d=abs(a[i]-a[1]*2)
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve(mid,1,i):
            ok=mid
        else:
            ng=mid
    p,q=a[ok],a[i]-a[ok]
    ok=i+1
    ng=n
    d=abs(a[i+1]*2-a[i]-a[n])
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve(mid,i+1,n):
            ok=mid
        else:
            ng=mid
    r,s=a[ok]-a[i],a[n]-a[ok]
    m=min(m,max(p,q,r,s)-min(p,q,r,s))
print(m)

Submission status: Wrong Answer

Solution code:
def solve(mid,l,r):
    global d
    x=a[mid]-a[l-1]
    y=a[r]-a[mid]
    t=abs(y-x)
    if t<d:
        d=t
        return 1
    return 0
n,*a=map(int,open(0).read().split())
m=1e18
for i in range(n-1):
    a[i+1]+=a[i]
a=[0]+a
for i in range(2,n-1):
    ok=1
    ng=i
    d=abs(a[i]-a[1]*2)
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve(mid,1,i):
            ok=mid
        else:
            ng=mid
    p,q=a[ok],a[i]-a[ok]
    ok=i+1
    ng=n
    d=abs(a[i+1]*2-a[i]-a[n])
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve(mid,i+1,n):
            ok=mid
        else:
            ng=mid
    r,s=a[ok]-a[i],a[n]-a[ok]
    m=min(m,max(p,q,r,s)-min(p,q,r,s))
print(m)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [ int(x) for x in input().split() ]
SS = [0]
for a in A:
    SS += [SS[-1] + a]

part1 = {2:1}

for i in range(3, N-1):
    p1 = part1[i-1]

    d1 = abs(SS[p1]-(SS[i]-SS[p1]))
    d2 = abs(SS[p1+1]-(SS[i]-SS[p1+1]))

    if d1 >= d2:
        part1[i] = p1+1
    else:
        part1[i] = p1

part3 = {N-2:N-1}

for i in range(N-3, 1, -1):
    p3 = part3[i+1]

    d1 = abs( (SS[N] - SS[p3]) - (SS[p3] - SS[i]) )
    d2 = abs( (SS[N] - SS[p3-1]) - (SS[p3-1] - SS[i]) )

    if d1 >= d2:
        part3[i] = p3-1
    else:
        part3[i] = p3

ans = float("inf")

for part2 in range(2, N-1):
    p1 = part1[part2]
    p2 = part2
    p3 = part3[part2]

    min_v = min(SS[p1], SS[p2]-SS[p1], SS[p3]-SS[p2], SS[N]-SS[p3])
    max_v = max(SS[p1], SS[p2]-SS[p1], SS[p3]-SS[p2], SS[N]-SS[p3])
    ans = min(ans, max_v-min_v)

print(ans)

Submission status: Wrong Answer

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

cumsum = [0] * n
for i in range(n):
  if i == 0:
    cumsum[0] = a[0]
  else:
    cumsum[i] = cumsum[i-1] + a[i]
    
l = 0
r = 2
ans = sum(a)
for i in range(2, n-1):
  while cumsum[i] - cumsum[l+1] > cumsum[l]:
    l += 1
  while cumsum[-1] - cumsum[r+1] > cumsum[r] - cumsum[i]:
    r += 1
  a = cumsum[l]
  b = cumsum[i] - cumsum[l]
  c = cumsum[r] - cumsum[i]
  d = cumsum[-1] - cumsum[r]
  
  ans = min(ans, max(a,b,c,d) - min(a,b,c,d))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

lst_accum = list(itertools.accumulate(lst))

def shaku(lst_accum, first):
    all_sum = lst_accum[-1]
    min_diff = 10**100
    for k in range(len(lst_accum)-1):
        diff = abs(all_sum - 2*lst_accum[k] + first)
        if min_diff > diff:
            index = k
            min_diff = diff
            P = lst_accum[k] - first
    return P, all_sum - P - first

min_diff = 10**100
for k in range(1, len(lst_accum)-2):
    lst_first = lst_accum[:k+1]
    lst_second = lst_accum[k+1:]
    print('length_first: ', len(lst_first))
    P, Q = shaku(lst_first, 0)
    print('length_second: ', len(lst_second))
    R, S = shaku(lst_second, lst_accum[k])
    min_diff = min(min_diff, max(P, Q, R, S) - min(P, Q, R, S))
print(min_diff)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
if n==4:
    print(max(a)-min(a))
    exit()
for i in range(1,n):
    a[i] += a[i-1]
l_l,r_r = 1,3
ans = float('inf')
for i in range(2,n-2):
    while True:
        if abs(a[i-1]-a[l_l-1]*2)>=abs(a[i-1]-a[l_l]*2) and l_l<i:
            l_l += 1
        else:
            break
    while True:
        if abs((a[-1]-a[r_r-1])-(a[r_r-1]-a[i-1]))>=abs((a[-1]-a[r_r])-(a[r_r]-a[i-1])) or r_r<=i:
            r_r += 1
        else:
            break
    mx = max(a[l_l-1],a[i-1]-a[l_l-1],a[r_r-1]-a[i-1],a[-1]-a[r_r-1])
    mn = min(a[l_l-1],a[i-1]-a[l_l-1],a[r_r-1]-a[i-1],a[-1]-a[r_r-1])
    ans = min(ans,mx-mn)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
if n==4:
    print(max(a)-min(a))
    exit()
for i in range(1,n):
    a[i] += a[i-1]
l_l,r_r = 1,3
ans = float('inf')
for i in range(2,n-2):
    while True:
        if abs(a[i-1]-a[l_l-1]*2)>abs(a[i-1]-a[l_l]*2) and l_l<i:
            l_l += 1
        else:
            break
    while True:
        if abs((a[-1]-a[r_r-1])-(a[r_r-1]-a[i-1]))>abs((a[-1]-a[r_r])-(a[r_r]-a[i-1])) or r_r<=i:
            r_r += 1
        else:
            break
    mx = max(a[l_l-1],a[i-1]-a[l_l-1],a[r_r-1]-a[i-1],a[-1]-a[r_r-1])
    mn = min(a[l_l-1],a[i-1]-a[l_l-1],a[r_r-1]-a[i-1],a[-1]-a[r_r-1])
    ans = min(ans,mx-mn)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
if n==4:
    print(max(a)-min(a))
    exit()
for i in range(1,n):
    a[i] += a[i-1]
l_l,r_r = 1,3
ans = 10**9
for i in range(2,n-2):
    while True:
        if abs(a[i-1]-a[l_l-1]*2)>abs(a[i-1]-a[l_l]*2) and l_l<i:
            l_l += 1
        else:
            break
    while True:
        if abs((a[-1]-a[r_r-1])-(a[r_r-1]-a[i-1]))>abs((a[-1]-a[r_r])-(a[r_r]-a[i-1])) or r_r<=i:
            r_r += 1
        else:
            break
    mx = max(a[l_l-1],a[i-1]-a[l_l-1],a[r_r-1]-a[i-1],a[-1]-a[r_r-1])
    mn = min(a[l_l-1],a[i-1]-a[l_l-1],a[r_r-1]-a[i-1],a[-1]-a[r_r-1])
    ans = min(ans,mx-mn)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
for i in range(1,n):
    a[i] += a[i-1]
l_l,r_r = 1,3
ans = 10**9
for i in range(2,n-2):
    while True:
        if abs(a[i-1]-a[l_l-1]*2)>abs(a[i-1]-a[l_l]*2) and l_l<i:
            l_l += 1
        else:
            break
    while True:
        if abs((a[-1]-a[r_r-1])-(a[r_r-1]-a[i-1]))>abs((a[-1]-a[r_r])-(a[r_r]-a[i-1])) or r_r<=i:
            r_r += 1
        else:
            break
    mx = max(a[l_l-1],a[i-1]-a[l_l-1],a[r_r-1]-a[i-1],a[-1]-a[r_r-1])
    mn = min(a[l_l-1],a[i-1]-a[l_l-1],a[r_r-1]-a[i-1],a[-1]-a[r_r-1])
    ans = min(ans,mx-mn)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
for i in range(1,n):
    a[i] += a[i-1]
l_l = 1
d = 10**9
for i in range(2,n-1):
    if (a[-1]-a[1])/2-(a[i]-a[1])<d:
        d = a[i]
r_r = a.index(d)
ans = 10**9
for i in range(2,n-2):
    if abs(a[i-1]-a[l_l-1]*2)>abs(a[i-1]-a[l_l]*2):
        l_l += 1
    if abs((a[-1]-a[r_r-1])-(a[r_r-1]-a[i-1]))>abs((a[-1]-a[r_r])-(a[r_r]-a[i-1])):
        r_r += 1
    mx = max(a[l_l-1],a[i-1]-a[l_l-1],a[r_r-1]-a[i-1],a[-1]-a[r_r-1])
    mn = min(a[l_l-1],a[i-1]-a[l_l-1],a[r_r-1]-a[i-1],a[-1]-a[r_r-1])
    ans = min(ans,mx-mn)
print(ans)

Submission status: Wrong Answer

Solution code:
def hersCode(L, x):
  ng = 0
  ok = len(L) - 1
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if L[mid] > x:
      ok = mid
    else:
      ng = mid
  return ok

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

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

t = hersCode(cs,(cs[N - 2] - A[0]) // 2)
b = 0
c = t
d = N - 2
e = N - 1
B = cs[b]
C = cs[c] - cs[b]
D = cs[d] - cs[c]
E = cs[e] - cs[d]

while True:
  t = C - D
  if t >= 0:
    if abs(t - 2 * A[c]) < t:
      C -= A[c]
      D += A[c]
      c -= 1
    else:
      break
  else:
    if abs(-t - 2 * A[c + 1]) < -t:
      C += A[c + 1]
      D -= A[c + 1]
      c += 1
    else:
      break

Ans = max(B, C, D, E) - min(B, C, D, E)
while True:
  if B >= C and B >= D and E >= C and E >=D:
    break
  if b == c - 1 and c == d - 1:
    break
  if b == c - 1:
    E += A[d]
    D -= A[d]
    d -= 1
  elif c == d - 1:
    B += A[b + 1]
    C -= A[b + 1]
    b += 1
  else:
    if B + A[b + 1] < E + A[d]:
      B += A[b + 1]
      C -= A[b + 1]
      b += 1
    else:
      E += A[d]
      D -= A[d]
      d -= 1
  while True:
    t = C - D
    if t >= 0:
      if abs(t - 2 * A[c]) < t:
        C -= A[c]
        D += A[c]
        c -= 1
      else:
        break
    else:
      if abs(-t - 2 * A[c + 1]) < -t:
        C += A[c + 1]
        D -= A[c + 1]
        c += 1
      else:
        break
  t = max(B, C, D, E) - min(B, C, D, E)
  if Ans > t:
    Ans = t
print(Ans)

Submission status: Wrong Answer

Solution code:
def hersCode(L, x):
  ng = 0
  ok = len(L) - 1
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if L[mid] > x:
      ok = mid
    else:
      ng = mid
  return ok

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

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

t = hersCode(cs,(cs[N - 2] - A[0]) // 2)
b = 0
c = t
d = N - 2
e = N - 1
B = cs[b]
C = cs[c] - cs[b]
D = cs[d] - cs[c]
E = cs[e] - cs[d]

Ans = max(B, C, D, E) - min(B, C, D, E)
while True:
  if B >= C and B >= D and E >= C and E >=D:
    break
  if B + A[b + 1] < E + A[d]:
    B += A[b + 1]
    C -= A[b + 1]
    b += 1
  else:
    E += A[d]
    D -= A[d]
    d -= 1
  while True:
    t = C - D
    if t >= 0:
      if abs(t - 2 * A[c]) < t:
        C -= A[c]
        D += A[c]
        c -= 1
      else:
        break
    else:
      if abs(-t - 2 * A[c + 1]) < -t:
        C += A[c + 1]
        D -= A[c + 1]
        c += 1
      else:
        break
  t = max(B, C, D, E) - min(B, C, D, E)
  if Ans > t:
    Ans = t
print(Ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)
def spl_l(i,b):
    while abs(h[i]-2*h[b])>abs(h[i]-2*h[b+1]):
        b+=1
    return b
def spl_r(i,b):
    while abs(h[-1]-2*h[b]+h[i])>abs(h[-1]-2*h[b+1]+h[i]):
        b+=1
    return b
def calc(j,i,k):
    pqrs=[h[j],h[i]-h[j],h[k]-h[i],h[-1]-h[k]]
    ans=max(pqrs)-min(pqrs)
    return ans

j=0
k=2
ans=18**20
ans=min(ans,calc(j,1,k))
for i in range(2,N-2):
    j=spl_l(i,j)
    k=spl_r(i,k)
    ans=min(ans,calc(j,i,k))
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)
def spl_l(i,b):
    while abs(h[i]-2*h[b])>=abs(h[i]-2*h[b+1]):
        b+=1
    return b
def spl_r(i,b):
    while abs(h[-1]-2*h[b]+h[i])>=abs(h[-1]-2*h[b+1]+h[i]):
        b+=1
    return b
def calc(j,i,k):
    pqrs=[h[j],h[i]-h[j],h[k]-h[i],h[-1]-h[k]]
    ans=max(pqrs)-min(pqrs)
    return ans

j=0
k=2
ans=calc(j,1,k)
for i in range(2,N-2):
    j=spl_l(i,j)
    k=spl_r(i,k)
    ans=min(ans,calc(j,i,k))
print(int(ans))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)
def spl_l(i,b):
    while abs(h[i]-2*h[b])>abs(h[i]-2*h[b+1]):
        b+=1
    return b
def spl_r(i,b):
    while abs(h[-1]-2*h[b]+h[i])>abs(h[-1]-2*h[b+1]+h[i]):
        b+=1
    return b
def calc(j,i,k):
    pqrs=[h[j],h[i]-h[j],h[k]-h[i],h[-1]-h[k]]
    ans=max(pqrs)-min(pqrs)
    return ans

j=0
k=2
ans=calc(j,1,k)
for i in range(2,N-2):
    j=spl_l(i,j)
    k=spl_r(i,k)
    ans=min(ans,calc(j,i,k))
print(int(ans))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)
def spl_l(i,b):
    while abs(h[i]-2*h[b])>abs(h[i]-2*h[b+1]):
        b+=1
    return b
def spl_r(i,b):
    while abs(h[-1]-2*h[b]+h[i])>abs(h[-1]-2*h[b+1]+h[i]):
        b+=1
    return b
def calc(j,i,k):
    pqrs=[h[j],h[i]-h[j],h[k]-h[i],h[-1]-h[k]]
    ans=max(pqrs)-min(pqrs)
    return ans

j=0
k=2
ans=calc(j,1,k)
for i in range(2,N-2):
    j=spl_l(i,j)
    k=spl_r(i,k)
    ans=min(ans,calc(j,i,k))
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)

def spl_l(i,b):
    while abs(h[i]-2*h[b])>abs(h[i]-2*h[b+1]):
        b+=1
    return b
def spl_r(i,b):
    while abs(h[-1]-2*h[b]+h[i])>abs(h[-1]-2*h[b+1]+h[i]):
        b+=1
    return b
j=0
k=2
p=h[j]
q=h[1]-h[j]
r=h[k]-h[1]
s=h[-1]-h[k]
ans=max([p,q,r,s])-min([p,q,r,s])
for i in range(2,N-2):
    j=spl_l(i,j)
    k=spl_r(i,k)
    p=h[j]
    q=h[i]-h[j]
    r=h[k]-h[i]
    s=h[-1]-h[k]
    if max([p,q,r,s])-min([p,q,r,s])<ans:
        ans=max([p,q,r,s])-min([p,q,r,s])
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)

def spl_l(i,b):
    while (h[i]-h[b])>h[b]:
        b+=1
    if 2*h[b]-h[i]>=h[i]-2*h[b-1]:
        return b-1
    return b
def spl_r(i,b):
    while (h[-1]-h[b])>(h[b]-h[i]):
        b+=1
    if 2*h[b]-h[-1]-h[i]>=h[-1]-2*h[b-1]+h[i]:
        return b-1
    return b
j=0
k=2
p=h[j]
q=h[1]-h[j]
r=h[k]-h[1]
s=h[-1]-h[k]
ans=max([p,q,r,s])-min([p,q,r,s])
for i in range(2,N-2):
    j=spl_l(i,j)
    k=spl_r(i,k)
    p=h[j]
    q=h[i]-h[j]
    r=h[k]-h[i]
    s=h[-1]-h[k]
    if max([p,q,r,s])-min([p,q,r,s])<ans:
        ans=max([p,q,r,s])-min([p,q,r,s])
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)

def spl_l(i,b):
    while (h[i]-h[b])>h[b]:
        b+=1
    if 2*h[b]-h[i]>h[i]-2*h[b-1]:
        return b-1
    return b
def spl_r(i,b):
    while (h[-1]-h[b])>(h[b]-h[i]):
        b+=1
    if 2*h[b]-h[-1]-h[i]>h[-1]-2*h[b-1]+h[i]:
        return b-1
    return b

ans=10**18
j=0
k=2
p=h[j]
q=h[1]-h[j]
r=h[k]-h[1]
s=h[-1]-h[k]
if (max([p,q,r,s])-min([p,q,r,s]))<ans:
    ans=max([p,q,r,s])-min([p,q,r,s])
for i in range(N):
    if i>1 and i<N-2:
        j=spl_l(i,j)
        k=spl_r(i,k)
        p=h[j]
        q=h[i]-h[j]
        r=h[k]-h[i]
        s=h[-1]-h[k]
        if abs(max([p,q,r,s])-min([p,q,r,s]))<ans:
            ans=max([p,q,r,s])-min([p,q,r,s])
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)

def spl_l(i,b):
    while (h[i]-h[b])>h[b]:
        b+=1
    if 2*h[b]-h[i]>h[i]-2*h[b-1]:
        return b-1
    return b
def spl_r(i,b):
    while (h[-1]-h[b])>(h[b]-h[i]):
        b+=1
    if 2*h[b]-h[-1]-h[i]>h[-1]-2*h[b-1]+h[i]:
        return b-1
    return b

ans=10**18
j=0
k=2
p=h[j]
q=h[1]-h[j]
r=h[k]-h[1]
s=h[-1]-h[k]
if (max([p,q,r,s])-min([p,q,r,s]))<ans:
    ans=max([p,q,r,s])-min([p,q,r,s])
for i in range(N):
    if i>1 and i<N-2:
        j=spl_l(i,j)
        k=spl_r(i,k)
        p=h[j]
        q=h[i]-h[j]
        r=h[k]-h[i]
        s=h[-1]-h[k]
        if (max([p,q,r,s])-min([p,q,r,s]))<ans:
            ans=max([p,q,r,s])-min([p,q,r,s])
print(ans)

Submission status: Wrong Answer

Solution code:
def spl_l(i,j,h):
    delta=[]
    for b in range(j,i):
        delta.append(abs(h[-1]-2*h[b]))
    m=delta.index(min(delta))
    return m+j
def spl_r(i,k,h):
    delta=[]
    for d in range(k,len(h)):
        delta.append(abs(h[-1]-2*h[d]+h[i]))
    m=delta.index(min(delta))
    return m+k
N=int(input())
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)
ans=10**18
j=0
k=2
for i in range(N):
    if i>0 and i<N-2:
        p=h[j]
        q=h[i]-h[j]
        r=h[k]-h[i]
        s=h[-1]-h[k]
        if (max([p,q,r,s])-min([p,q,r,s]))<ans:
            ans=max([p,q,r,s])-min([p,q,r,s])
        j=spl_l(i,j,h)
        k=spl_r(i,k,h)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)
ans=10**18
for i in range(N):
    if i>0 and i<N-2:
        j=(len(h[:i+1])-1)//2
        k=(len(h[i+1:])-1)//2
        p=h[j]
        q=h[i]-h[j]
        r=h[k+i]-h[i]
        s=h[-1]-h[k+i]
        if (max([p,q,r,s])-min([p,q,r,s]))<ans:
            ans=max([p,q,r,s])-min([p,q,r,s])
print(ans)

Submission status: Wrong Answer

Solution code:
def spl(a):
    delta=[]
    for i in range(len(a)-1):
        delta.append(abs(a[-1]-2*a[i]))
    m=min(delta)
    index=[]
    for i in range(len(delta)):
        if delta[i]==m:
            index.append(i)
    return index

N=int(input())
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)
ans=10**18
for i in spl(h):
    if i>0 and i<N-2:
        g=[l-h[i] for l in h[i+1:]]
        for j in spl(h[:i+1]):
            for k in spl(g):
                p=h[j]
                q=h[i]-h[j]
                r=h[k+i+1]-h[i]
                s=h[-1]-h[k+i+1]
                if (max([p,q,r,s])-min([p,q,r,s]))<ans:
                    ans=max([p,q,r,s])-min([p,q,r,s])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + a[i]
llsum = a[0]
lrsum = a[1]
l = [0] * n
l[2] = 1
for mid in range(3, n-1):
    new = a[mid-1]
    unk = a[l[mid-1]]
    lrsum += new
    if abs(lrsum - llsum) > abs(lrsum - llsum - 2 * unk):
        l[mid] = l[mid-1] + 1
        llsum += unk
        lrsum -= unk
    else:
        l[mid] = l[mid-1]
rrsum = a[n-1]
rlsum = a[n-2]
r = [0] * n
r[n-2] = n-1
for mid in reversed(range(2, n-2)):
    new = a[mid]
    unk = a[r[mid+1]-1]
    rlsum += new
    if abs(rlsum - rrsum) > abs(rlsum - rrsum - 2 * unk):
        r[mid] = r[mid+1] - 1
        rrsum += unk
        rlsum -= unk
    else:
        r[mid] = r[mid+1]
minabs = 10 ** 20
for mid in range(2, n-1):
    c0 = cum[l[mid]]
    c1 = cum[mid]
    c2 = cum[r[mid]]
    sums = (c0, c1 - c0, c2 - c1, cum[n] - c2)
    minabs = min(minabs, max(sums) - min(sums))
print(minabs)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + a[i]
llsum = a[0]
lrsum = a[1]
l = [0] * n
l[2] = 1
for mid in range(3, n-1):
    new = a[mid-1]
    unk = a[l[mid-1]]
    lrsum += new
    if abs(lrsum - llsum) > abs(lrsum - llsum - 2 * unk):
        l[mid] = l[mid-1] + 1
        llsum += unk
        lrsum -= unk
    else:
        l[mid] = l[mid-1]
rrsum = a[n-1]
rlsum = a[n-2]
r = [0] * n
r[n-2] = n-1
for mid in reversed(range(2, n-2)):
    new = a[mid]
    unk = a[r[mid+1]-1]
    rlsum += new
    if abs(rlsum - rrsum) > abs(rlsum - rrsum - 2 * unk):
        r[mid] = r[mid+1] - 1
        rrsum += unk
        rlsum -= unk
    else:
        r[mid] = r[mid+1]
minabs = 10 ** 10
for mid in range(2, n-1):
    c0 = cum[l[mid]]
    c1 = cum[mid]
    c2 = cum[r[mid]]
    sums = (c0, c1 - c0, c2 - c1, cum[n] - c2)
    minabs = min(minabs, max(sums) - min(sums))
print(minabs)