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:
# arc 100 D

def ruiseki(n,array):
    res = [0]*(n+1)
    for i in range(n):
        res[i+1] = res[i] + array[i]
    return res

n = int(input())
A = list(map(int,input().split()))
sa = ruiseki(n,A)

from bisect import bisect_right

ans = 10**15
for i in range(1,n-2):
    left = sa[i+1]
    right = sa[-1] - sa[i+1]

    lsplit = min(bisect_right(sa[:i+1],left//2) - 2,i-1)
    rsplit = min(bisect_right(sa[i+1:],right//2 + left) + i-1,n-2)
    lleft = [(sa[lsplit + 1],sa[i+1] - sa[lsplit + 1]),(sa[lsplit + 2],sa[i+1] - sa[lsplit + 2])]
    rright = [(sa[rsplit+1] - sa[i+1],sa[-1] - sa[rsplit+1]),(sa[rsplit+2] - sa[i+1],sa[-1] - sa[rsplit+2])]
    lM = max(max(lleft[0]),max(lleft[1]))
    rM = max(max(rright[0]),max(rright[1]))

    M = max(lM,rM)
    m = min(sa[i+1]-lM,sa[-1] - sa[i+1] - rM)
    ans = min(ans, M-m)

print(ans)

Submission status: Wrong Answer

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    import itertools
    import math
    B = list(itertools.accumulate(A))
    C = [i*A[i] for i in range(N)]
    D = list(itertools.accumulate(C))

    g = math.floor(D[-1]/B[-1])
    g1 = math.floor(D[g]/B[g])
    g2 = math.floor((D[-1]-D[g])/(B[-1]-B[g]))

    answer = pow(10, 10)
    for i in range(-20, 21):
        for j in range(-20, 21):
            for k in range(-20, 21):
                if 0 <= g1+i and g1+i < g+j and g+j < g2+k and g2+k < N:
                    m = min(B[g1+i], B[g+j]-B[g1+i], B[g2+k]-B[g+j], B[-1]-B[g2+k])
                    M = max(B[g1+i], B[g+j]-B[g1+i], B[g2+k]-B[g+j], B[-1]-B[g2+k])
                    answer = min(answer, M-m)

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    import itertools
    import math
    B = list(itertools.accumulate(A))
    C = [i*A[i] for i in range(N)]
    D = list(itertools.accumulate(C))

    g = math.floor(D[-1]/B[-1])
    g1 = math.floor(D[g]/B[g])
    g2 = math.floor((D[-1]-D[g])/(B[-1]-B[g]))

    answer = pow(10, 10)
    for i in range(-10, 11):
        for j in range(-10, 11):
            for k in range(-10, 11):
                if 0 <= g1+i and g1+i < g+j and g+j < g2+k and g2+k < N:
                    m = min(B[g1+i], B[g+j]-B[g1+i], B[g2+k]-B[g+j], B[-1]-B[g2+k])
                    M = max(B[g1+i], B[g+j]-B[g1+i], B[g2+k]-B[g+j], B[-1]-B[g2+k])
                    answer = min(answer, M-m)

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    import itertools
    import math
    B = list(itertools.accumulate(A))
    C = [i*A[i] for i in range(N)]
    D = list(itertools.accumulate(C))

    g = math.floor(D[-1]/B[-1])
    g1 = math.floor(D[g]/B[g])
    g2 = math.floor((D[-1]-D[g])/(B[-1]-B[g]))

    answer = pow(10, 10)
    for i in range(-2, 3):
        for j in range(-2, 3):
            for k in range(-2, 3):
                if 0 <= g1+i and g1+i < g+j and g+j < g2+k and g2+k < N:
                    m = min(B[g1+i], B[g+j]-B[g1+i], B[g2+k]-B[g+j], B[-1]-B[g2+k])
                    M = max(B[g1+i], B[g+j]-B[g1+i], B[g2+k]-B[g+j], B[-1]-B[g2+k])
                    answer = min(answer, M-m)

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
from itertools import accumulate
C=list(accumulate(A))
from bisect import bisect_left
x=bisect_left(C,C[-1]//2)
r=10**16
for i in range(x-4,x+5):
    if not 1<i<N-1:continue
    D=10**16
    for j in range(i):
        if abs(C[i-1]-C[j]*2)<D:
            a,b=C[j],C[i-1]-C[j]
            D=abs(a-b)
    D=10**16
    for k in range(i,N):
        if abs(C[N-1]-C[k]*2+C[i-1])<D:
            c,d=C[k]-C[i-1],C[N-1]-C[k]
            D=abs(c-d)
    r=min(r,max(a,b,c,d)-min(a,b,c,d))
print(r)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
from itertools import accumulate
C=list(accumulate(A))
from bisect import bisect_left
x=bisect_left(C,C[-1]//2)
r=10**16
for i in range(x-2,x+3):
    if not 1<i<N-1:continue
    D=10**16
    for j in range(i):
        if abs(C[i-1]-C[j]*2)<D:
            a,b=C[j],C[i-1]-C[j]
            D=abs(a-b)
    D=10**16
    for k in range(i,N):
        if abs(C[N-1]-C[k]*2+C[i-1])<D:
            c,d=C[k]-C[i-1],C[N-1]-C[k]
            D=abs(c-d)
    r=min(r,max(a,b,c,d)-min(a,b,c,d))
print(r)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
from itertools import accumulate
C=list(accumulate(A))
from bisect import bisect_left
x=bisect_left(C,C[-1]//2)
r=10**16
for i in range(x-2,x+3):
    if not 1<i<N-1:continue
    D=10**16
    for j in range(i):
        if abs(C[i-1]-C[j]*2)<D:
            a,b=C[j],C[i-1]-C[j]
            D=abs(a-b)
    D=10**16
    for k in range(i,N):
        if abs(C[N-1]-C[k]*2+C[i-1])<D:
            c,d=C[k]-C[i-1],C[N-1]-C[k]
            D=abs(c-d)
    print(i,a,b,c,d)
    r=min(r,max(a,b,c,d)-min(a,b,c,d))
print(r)

Submission status: Wrong Answer

Solution code:
import bisect

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

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

ans = 10**20
for i in range(2, N-1):
    left = S[:i]
    m = bisect.bisect(left, left[-1]//2)

    if m == 0:
        L = [left[0], left[-1]-left[0]]
    else:
        L = [left[m], left[-1]-left[m]]
        L2 = [left[m-1], left[-1]-left[m-1]]

        #if(abs(L[0]-L[1]) > abs(L2[0]-L2[1])): L = L2

    right = S[i:]
    m = bisect.bisect(right, (right[-1]+left[-1])//2)
    if m == 0:
        R = [right[0]-left[-1], right[-1]-right[0]]
    else:
        R = [right[m]-left[-1], right[-1]-right[m]]
        R2 = [right[m-1]-left[-1], right[-1]-right[m-1]]

        #if(abs(R[0]-R[1]) > abs(R2[0]-R2[1])): R = R2

    #print(L, end="")
    #print(R)

    ans = min(ans, max(L[0],L[1],R[0],R[1]) - min(L[0],L[1],R[0],R[1]))

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

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

ans = 1e18
for i in range(2, N-1):
    left = S[:i]
    m = bisect.bisect(left, left[-1]//2)

    if m == 0:
        L = [left[0], left[-1]-left[0]]
    else:
        L = [left[m], left[-1]-left[m]]
        L2 = [left[m-1], left[-1]-left[m-1]]

        if(abs(L[0]-L[1]) > abs(L2[0]-L2[1])): L = L2

    right = S[i:]
    m = bisect.bisect(right, (right[-1]+left[-1])//2)
    if m == 0:
        R = [right[0]-left[-1], right[-1]-right[0]]
    else:
        R = [right[m]-left[-1], right[-1]-right[m]]
        R2 = [right[m-1]-left[-1], right[-1]-right[m-1]]

        if(abs(R[0]-R[1]) > abs(R2[0]-R2[1])): R = R2

    print(L, end="")
    print(R)

    ans = min(ans, max(L[0],L[1],R[0],R[1]) - min(L[0],L[1],R[0],R[1]))

print(ans)

Submission status: Wrong Answer

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

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

N = ir()
A = lr()
Acum = list(accumulate(A))
l_cut = [None] * N  # 左のリストで2つに切り分けるindex
l_cut[1] = 0
l = A[0]; r = A[1]
for i in range(2, N):
    r += A[i]
    diff = abs(r-l)
    index = l_cut[i-1]
    while index < i - 1:
        temp = abs(l + A[index+1] - (r - A[index+1]))
        if temp < diff:
            index += 1
            l += A[index]
            r -= A[index]
        else:
            break
    l_cut[i] = index

r_cut = [None] * N
r_cut[-2] = N-2
l = A[-2]; r = A[-1]
for i in range(N-3, 0, -1):
    l += A[i]
    diff = abs(r-l)
    index = r_cut[i+1]
    while index > i:
        temp = abs(r + A[index] - (l - A[index]))
        if temp < diff:
            index -= 1
            r += A[index+1]
            l -= A[index+1]
            diff = temp
        else:
            break
    r_cut[i] = index

answer = 10 ** 17
for i in range(1, N-2):
    a = Acum[l_cut[i]]
    b = Acum[i] - a
    c = Acum[r_cut[i+1]] - Acum[i]
    d = Acum[-1] - (a + b + c)
    temp = max(a, b, c, d) - min(a, b, c, d)
    if temp < answer:
        answer = temp

print(answer)
# 27r

Submission status: Wrong Answer

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

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

N = ir()
A = lr()
Acum = list(accumulate(A))
l_cut = [None] * N  # 左のリストで2つに切り分けるindex
l_cut[1] = 0
l = A[0]; r = A[1]
for i in range(2, N):
    r += A[i]
    diff = abs(r-l)
    index = l_cut[i-1]
    while index < i - 1:
        temp = abs(l + A[index+1] - (r - A[index+1]))
        if temp < diff:
            index += 1
            l += A[index]
            r -= A[index]
        else:
            break
    l_cut[i] = index

r_cut = [None] * N
r_cut[-2] = N-2
l = A[-2]; r = A[-1]
for i in range(N-3, 0, -1):
    l += A[i]
    diff = abs(r-l)
    index = r_cut[i+1]
    while index > i:
        temp = abs(r + A[index] - (l - A[index]))
        if temp < diff:
            index -= 1
            r += A[index+1]
            l -= A[index+1]
            diff = temp
        else:
            break
    r_cut[i] = index

answer = 10 ** 15
for i in range(1, N-2):
    a = Acum[l_cut[i]]
    b = Acum[i] - a
    c = Acum[r_cut[i+1]] - Acum[i]
    d = Acum[-1] - (a + b + c)
    temp = max(a, b, c, d) - min(a, b, c, d)
    if temp < answer:
        answer = temp

print(answer)
# 27r

Submission status: Wrong Answer

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

from bisect import bisect
cums=[0]
for a in A:
    cums.append(cums[-1]+a)

lmn=[]
lmx=[]
for i in range(2,n-1):
    j=bisect(cums,cums[i]//2)
    a1,b1=cums[j],cums[i]-cums[j]
    a2,b2=cums[j-1],cums[i]-cums[j-1]
    if abs(a1-b1)<abs(a2-b2):
        lmn.append(min(a1,b1))
        lmx.append(max(a1,b1))
    else:
        lmn.append(min(a2,b2))
        lmx.append(max(a2,b2))
A.reverse()
cums=[0]
for a in A:
    cums.append(cums[-1]+a)

rmn=[]
rmx=[]
for i in range(2,n-1):
    j=bisect(cums,cums[i]//2)
    a1,b1=cums[j],cums[i]-cums[j]
    a2,b2=cums[j-1],cums[i]-cums[j-1]
    if abs(a1-b1)<abs(a2-b2):
        rmn.append(min(a1,b1))
        rmn.append(max(a1,b1))
    else:
        rmn.append(min(a2,b2))
        rmx.append(max(a2,b2))
rmn.reverse()
rmx.reverse()
ans=float('inf')
for ln,lx,rn,rx in zip(lmn,lmx,rmn,rmx):
    d=max(lx,rx)-min(ln,rn)
    ans=min(ans,d)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]
 
ans = []
t = []
c = 0
for i in range(N):
    c += A[i]
    t.append(c)
    
l = 0
r = 0

for _ in range(2, N-1):
    while t[_] > t[l]+t[l+1]:
        l += 1
    while t[-1]+t[_] > t[r]+t[r+1]:
        r += 1
    n = [t[l], t[_]-t[l], t[r]-t[_], t[-1]-t[r]]
    ans.append(max(n)-min(n))
    
print(min(ans))

Submission status: Wrong Answer

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

ans = []
t = []
c = 0
for i in range(N):
    c += A[i]
    t.append(c)

for _ in range(2, N-1):
    c = 0
    while True:
        if t[c] > t[_]-t[c]:
            if t[c] - (t[_]-t[c]) >  (t[_]-t[c-1]) - t[c-1]:
                n = [t[_]-t[c-1], t[c-1]]
            else:
                n = [t[c], (t[_]-t[c]) ]
            c = 0
            break
        c += 1
    while True:
        if t[_+c]-t[_] > t[-1] - t[_+c]:
            if (t[_+c]-t[_]) - (t[-1] - t[_+c]) >  (t[-1] - t[_+c-1]) - (t[_+c-1]-t[_]):
                m = [t[_+c]-t[_], t[-1] - t[_+c]]
            else:
                m = [t[c], (t[i]-t[c]) ]
            break
        c += 1
               
    ans.append(max(n+m)-min(n+m))
print(min(ans))

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate
from bisect import bisect
def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    ac = [0] + list(accumulate(A))

    def calc(lst): return abs(max(lst) - min(lst))
    def sm(l,r): return ac[r+1] - ac[l]
    def get_min_max(l,r):
        if r-l <= 1: return [A[l], A[r]]
        med = ac[l] + sm(l,r) / 2
        i = bisect(ac, med, l+1, r+1)
        r1 = [sm(l,i-1), sm(i,r)]
        if i-1 == l: return r1
        r2 = [sm(l,i-2), sm(i-1,r)]
        return r1 if calc(r1) < calc(r2) else r2

    ans = 10**18
    for R_left in range(2,N-2):
        PQ_mm = get_min_max(0, R_left-1)
        RS_mm = get_min_max(R_left, N-1)
        ans = min(ans, calc(PQ_mm + RS_mm))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate
from bisect import bisect
def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    ac = [0] + list(accumulate(A))

    def calc(lst): return abs(max(lst) - min(lst))
    def sm(l,r): return ac[r+1] - ac[l]
    def get_min_max(l,r):
        if r-l <= 1: return [A[l], A[r]]
        med = ac[l] + sm(l,r) / 2
        i = bisect(ac, med, l, r)
        r1 = [sm(l,i-1), sm(i,r)]
        if i-1 == l: return r1
        r2 = [sm(l,i-2), sm(i-1,r)]
        return r1 if calc(r1) < calc(r2) else r2

    ans = 10**18
    for R_left in range(2,N-2):
        PQ_mm = get_min_max(0, R_left-1)
        RS_mm = get_min_max(R_left, N-1)
        ans = min(ans, calc(PQ_mm + RS_mm))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def bsearch(mn, mx, func):
    #func(i)=False を満たす最大のi
    idx = (mx + mn)//2
    while mx-mn>1:
        if func(idx):
            idx, mx = (idx + mn)//2, idx
            continue
        idx, mn = (idx + mx)//2, idx
    return idx
N, = map(int, input().split())
A = list(map(int, input().split()))
X = [0]*(N+2)
Y = [0]*(N+2)
for i in range(N):
    X[i+1] = X[i] + A[i]
for i in range(N, 0, -1):
    Y[i] = Y[i+1] + A[i-1]

R = 10**18
for i in range(2, N-1):
    # X0, X1, X2 .. Xi
    # Xj Xj+1 (1<= j <= i-1)
    idx1 = bsearch(1, i-1, lambda j:X[i]//2 < X[j])
    idx2 = bsearch(i+1, N, lambda j:(X[N]-X[i])//2 < (X[j]-X[i]))
#    print(X[idx1], X[i]-X[idx1], X[idx2]-X[i], X[N]-X[idx2])
    cand = []
    if idx1+1 <= i-1:
        if abs(2*X[idx1]-X[i]) > abs(2*X[idx1+1]-X[i]):
            idx1+=1
    if idx2+1 <= i-1:
        if abs(2*X[idx2]-X[i]-X[N]) > abs(2*X[idx2+1]-X[i]-X[N]):
            idx2+=1
    mx = max([X[idx1], X[i]-X[idx1], X[idx2]-X[i], X[N]-X[idx2]])
    mn = min([X[idx1], X[i]-X[idx1], X[idx2]-X[i], X[N]-X[idx2]])
#    print(idx1, i, idx2)
#    print(mx-mn)
    R = min(R, mx-mn)
print(R)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
m = sum(a)/4

mx, mn = 0, 1e18
cnt = a[0]
for i in range(1,n):
        if abs(cnt-m)<abs(cnt+a[i]-m):
                mx = max(mx, cnt)
                mn = min(mn, cnt)
                cnt = a[i]
        else: cnt += a[i]
print(mx-mn)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
m = sum(a)/4

mx = cnt = 0
mn = 1e18
for i in range(n):
        if abs(cnt-m)<abs(cnt+a[i]-m):
                mx = max(mx, cnt)
                mn = min(mn, cnt)
                cnt = a[i]
        else: cnt += a[i]
print(mx-mn)

Submission status: Wrong Answer

Solution code:
import bisect
n=int(input())
a=list(map(int,input().split()))
l=[0]
for i in range(n):
    l.append(l[-1]+a[i])
ans=10**10
for i in range(n-3):
    m=i+2
    f=bisect.bisect_left(l,l[m]//2)
    if f==m:
        f-=1
    if f==m-1:
        z=[l[f],l[m]-l[f]]
    else:
        if abs(l[m]-2*l[f])>abs(l[m]-2*l[f+1]):
            z=[l[m]-l[f+1],l[f+1]]
        else:
            z=[l[m]-l[f],l[f]]
    b=bisect.bisect_left(l,l[m]+(l[-1]-l[m])//2)
    if b==n+1:
        b-=1
    if b==n:
        b-=1
    if abs((l[-1]-l[b])-(l[b]-l[m]))>abs((l[-1]-l[b+1])-(l[b+1]-l[m])):
        z.append(l[-1]-l[b+1])
        z.append(l[b+1]-l[m])
    else:
        z.append(l[-1]-l[b])
        z.append(l[b]-l[m])
    ans=min(ans,max(z)-min(z))
print(ans)

Submission status: Wrong Answer

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

ll = sorted(a)[-1]
ss = sum(a)
minmin=1000000000
s1 = 0
for i10 in range(0,n-2):
    s1 += a[i10]
    if s1 > ss // 4 - ll:
        break
i10 -= 1
s1 = sum(a[0:i10])
for i1 in range(i10,n-2):
    s1 += a[i1]
    if s1 > ss // 4 + ll:
        break
    s2 = 0
    for i2 in range(i1+1, n-1):
        s2 += a[i2]
        if s1 > s2:
            min1 = s2
            max1 = s1
        else:
            min1 = s1
            max1 = s2
        for i3 in range(i2+2, n):
            s3 = sum(a[i2+1:i3])
            s4 = sum(a[i3:])
            if s3 > s4:
                min2 = s4
                max2 = s3
            else:
                min2 = s3
                max2 = s4
            if max1 > max2:
                max3 = max1
            else:
                max3 = max2
            if min1 > min2:
                min3 = min2
            else:
                min3 = min1
            minmin1 = max3 - min3
            if minmin > minmin1:
                minmin = minmin1
#            print("{} {} {}: {} {} {} {} -> {}".format(i1, i2, i3, s1, s2, s3, s4, max3 - min3))
print(minmin)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

split_A = (np.array_split(A,4))
sum0 = np.sum(split_A[0])
sum1 = np.sum(split_A[1])
sum2 = np.sum(split_A[2])
sum3 = np.sum(split_A[3])
sum_list = np.hstack((sum0, sum1, sum2, sum3))
print(abs(sum_list.max() - sum_list.min()))

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import bisect

readInt = lambda : [int(i) for i in input().split()];
n = readInt()[0]
A = readInt()

B = list(itertools.accumulate(A))

cand = 2 * pow(10, 14)
for i in range(2, len(A)-1):
  z = B[i-1]
  s = z // 2
  j = bisect.bisect_right(B, s)
  c0 = abs(2 * B[j-1] - z)
  c1 = abs(2 * B[j] - z)
  j0 = j-1 if c0 < c1 else j

  z = B[i-1]
  s = z + (B[-1] - z) // 2
  j = bisect.bisect_right(B, s)
  c0 = abs(2 * B[j-1] - z)
  c1 = abs(2 * B[j] - z)
  j1 = j-1 if c0 < c1 else j

  c = [B[j0], B[i-1] - B[j0], B[j1] - B[i-1], B[-1] - B[j1]]
  cand = min(cand, max(c) - min(c))

ans = cand
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

def binsearch(a, start, end):
    low = start
    high = end

    mindiff = 2**63
    minpos = 0
    minleftsum = 0
    minrightsum = 0
    premid = -2
    mid = -1

    # print('--start--')
    while low <= high:
        premid = mid
        mid = (low + high) // 2
        leftsum = a[start:mid].sum()
        rightsum = a[mid:end].sum()
        diff = np.abs(leftsum - rightsum)
        if diff < mindiff:
            mindiff = diff
            minpos = mid
            minleftsum = leftsum
            minrightsum = rightsum

        # print(low, high, mid, leftsum, rightsum, diff, minpos)
        if leftsum < rightsum:
            low = mid + 1
        elif leftsum > rightsum:
            high = mid - 1
        else:
            return mid, leftsum, rightsum

    return minpos, minleftsum, minrightsum

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

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

mid0 = binsearch(A, 0, N)[0]
mid1, p, q = binsearch(A, 0, mid0)
mid2, r, s = binsearch(A, mid0, N)

diff = calcfinaldiff(p, q, r, s)

if mid0 > 0:
    mid1, p, q = binsearch(A, 0, mid0 - 1)
    mid2, r, s = binsearch(A, mid0 - 1, N)
    tmpdiff = calcfinaldiff(p, q, r, s)
    if tmpdiff < diff:
        diff = tmpdiff

if mid0 < N - 1:
    mid1, p, q = binsearch(A, 0, mid0 + 1)
    mid2, r, s = binsearch(A, mid0 + 1, N)
    tmpdiff = calcfinaldiff(p, q, r, s)
    if tmpdiff < diff:
        diff = tmpdiff

print(diff)

Submission status: Wrong Answer

Solution code:
def main():
    from itertools import accumulate as ac
    from bisect import bisect_right as br
    n=int(input())
    a=list(map(int,input().split()))
    b=list(ac([0]+a))
    ans=[]
    for i in range(2,n-1):
        l=b[i]
        r=b[n]
        lc=br(b,l/2)
        rc=br(b,l+r/2)
        temp_l=[]
        temp_r=[]
        if lc>1:
            temp_l.append([b[lc-1],l-b[lc-1]])
        if lc<i:
            temp_l.append([b[lc],l-b[lc]])
        if rc>i+2:
            temp_r.append([b[rc-2]-l,r-b[rc-2]])
        if rc<n+1:
            temp_r.append([b[rc-1]-l,r-b[rc-1]])
        temp_l.sort(key=lambda x:abs(x[0]-x[1]))
        temp_r.sort(key=lambda x:abs(x[0]-x[1]))
        temp=temp_l[0]+temp_r[0]
        temp.sort()
        ans.append(temp[-1]-temp[0])
    print(min(ans))
main()

Submission status: Wrong Answer

Solution code:
def main():
    from itertools import accumulate as ac
    from bisect import bisect_right as br
    n=int(input())
    a=list(map(int,input().split()))
    b=list(ac([0]+a))
    ans=[]
    for i in range(2,n-1):
        l=b[i]
        r=b[n]
        lc=br(b,l/2)
        rc=br(b,l+r/2)
        temp_l=[]
        temp_r=[]
        if lc>1:
            temp_l.append([b[lc-1],l-b[lc-1]])
        if lc<i:
            temp_l.append([b[lc],l-b[lc]])
        if rc>i+1:
            temp_r.append([b[rc-2]-l,r-b[rc-2]])
        if rc<n:
            temp_r.append([b[rc-1]-l,r-b[rc-1]])
        temp_l.sort(key=lambda x:abs(x[0]-x[1]))
        temp_r.sort(key=lambda x:abs(x[0]-x[1]))
        temp=temp_l[0]+temp_r[0]
        temp.sort()
        ans.append(temp[-1]-temp[0])
    print(min(ans))
main()

Submission status: Wrong Answer

Solution code:
def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    n=int(input())
    a=list(map(int,input().split()))
    b=list(ac([0]+a))
    ans=[]
    for i in range(2,n-1):
        l=b[i]
        r=b[n]
        lc=bl(b,l/2)
        rc=bl(b,l+r/2)
        temp_l=[]
        temp_r=[]
        if lc>1:
            temp_l.append([b[lc-1],l-b[lc-1]])
        if lc<i:
            temp_l.append([b[lc],l-b[lc]])
        if rc>i+1:
            temp_r.append([b[rc-2]-l,r-b[rc-2]])
        if rc<n:
            temp_r.append([b[rc-1]-l,r-b[rc-1]])
        temp_l.sort(key=lambda x:abs(x[0]-x[1]))
        temp_r.sort(key=lambda x:abs(x[0]-x[1]))
        temp=temp_l[0]+temp_r[0]
        temp.sort()
        ans.append(temp[-1]-temp[0])
    print(min(ans))
main()

Submission status: Wrong Answer

Solution code:
import bisect

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

#処理内容
def main():
	N = int(input())
	A = getlist()
	B = [0]
	for i in range(N):
		B.append(B[-1] + A[i])
	#print(B)
	ans = float("inf")
	for i in range(2, N - 1):
		Q = B[i]
		x = bisect.bisect_left(B, Q // 2)
		P = max(B[x], B[1])
		P = min(P, B[i - 1])
		if x >= 1:
			P2 = max(B[x - 1], B[1])
			Q2 = Q - P2
		Q3 = max(B[i] - B[i - 1], B[i] - B[x + 1])
		P3 = Q - Q3
		Q -= P
		S = B[N] - B[i]
		y = bisect.bisect_left(B, (B[i] + B[N]) // 2)
		R = max(B[y] - B[i] , B[i + 1] - B[i])
		R = min(R, B[N - 1] - B[i])
		R2 = max(B[y - 1] - B[i] , B[i + 1] - B[i])
		S2 = S - R2
		if y < N:
			S3 = max(B[N] - B[N - 1], B[N] - B[y + 1])
			R3 = S - S3
		S -= R
		ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
		if x >= 1:
			ans = min(ans, max(P2, Q2, R2, S2) - min(P2, Q2, R2, S2))
		if y < N:
			ans = min(ans, max(P3, Q3, R3, S3) - min(P3, Q3, R3, S3))
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import bisect

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

#処理内容
def main():
	N = int(input())
	A = getlist()
	B = [0]
	for i in range(N):
		B.append(B[-1] + A[i])
	#print(B)
	ans = float("inf")
	for i in range(2, N - 1):
		Q = B[i]
		x = bisect.bisect_left(B, Q // 2)
		P = max(B[x], B[1])
		if x >= 1:
			P2 = max(B[x - 1], B[1])
			Q2 = Q - P2
		Q3 = max(B[i] - B[i - 1], B[i] - B[x + 1])
		P3 = Q - Q3
		Q -= P

		S = B[N] - B[i]
		y = bisect.bisect_left(B, (B[i] + B[N]) // 2)
		R = max(B[y] - B[i] , B[i + 1] - B[i])
		R2 = max(B[y - 1] - B[i] , B[i + 1] - B[i])
		S2 = S - R2
		if y < N:
			S3 = max(B[N] - B[N - 1], B[N] - B[y + 1])
			R3 = S - S3
		S -= R
		#print(P, Q, R, S)
		#print(sum([P, Q, R, S]))
		ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
		if x >= 1:
			ans = min(ans, max(P2, Q2, R2, S2) - min(P2, Q2, R2, S2))
		if y < N:
			ans = min(ans, max(P3, Q3, R3, S3) - min(P3, Q3, R3, S3))
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

N = int(input())
A = list(map(int, input().split()))
INF = 10**14

S = sum(A)

def dfs(ind, part, remain, prob):
    if part == 1:
        if remain == 0: return INF
        prob.append(remain)
        return max(prob)-min(prob)
    border = remain/part
    s = 0
    while s < border and ind <= N-part:
        s += A[ind]
        ind += 1
    if s > A[ind-1]:
        a1 = dfs(ind-1, part-1, remain-s+A[ind-1], prob+[s-A[ind-1]])
    else:
        a1 = INF
    a2 = dfs(ind, part-1, remain-s, prob+[s])
    return min(a1, a2)

ans = dfs(0, 4, S, [])
print(ans)

Submission status: Wrong Answer

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

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

S = sum(A)

def dfs(ind, part, remain, prob):
    if part == 1:
        prob.append(remain)
        return max(prob)-min(prob)
    border = remain/part
    s = 0
    while s < border and ind <= N-part:
        s += A[ind]
        ind += 1
    a1 = dfs(ind-1, part-1, remain-s+A[ind-1], prob+[s-A[ind-1]])
    a2 = dfs(ind, part-1, remain-s, prob+[s])
    return min(a1, a2)

ans = dfs(0, 4, S, [])
print(ans)

Submission status: Wrong Answer

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(3, n-1):
        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: Wrong Answer

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(3, n-1):
        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(p-q) > 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: Wrong Answer

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(3, n-1):
        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(p-q) > 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(p, q, r, s)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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(3, n-1):
        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(p-q) > abs(p+a[lb] - (q-a[lb])):
            p += a[lb]
            q -= a[lb]
            lb += 1
        while rb < 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: Wrong Answer

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, A_sum, sum_half2//2)
print(ans)