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:
from itertools import accumulate
from bisect import bisect_left, bisect_right

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

ys = [0] + list(accumulate(xs))

rs = range(2, n-2)
v = []
for i in rs:
    j = bisect_left(ys, ys[i]//2)
    minmax1 = sorted([ys[j], ys[i] - ys[j]])
    minmax2 = sorted([ys[j-1], ys[i] - ys[j-1]])
    minmax3 = sorted([ys[j+1], ys[i] - ys[j+1]]) if j+1 <= i else (-float('inf'), float('inf'))
    _, max1, min1 = min((x-n, x, n) for n, x in (minmax1, minmax2, minmax3))

    k = bisect_left(ys, (ys[-1] - ys[i])//2 + ys[i])
    minmax1 = sorted([ys[k] - ys[i], ys[-1] - ys[k]])
    minmax2 = sorted([ys[k-1] - ys[i], ys[-1] - ys[k-1]])
    minmax3 = sorted([ys[k+1] - ys[i], ys[-1] - ys[k+1]]) if k+1 < len(ys) else (-float('inf'), float('inf'))
    _, max2, min2 = min((x-n, x, n) for n, x in (minmax1, minmax2, minmax3))

    minn, _, _, maxx = sorted([max1, min1, max2, min2])
    v.append(maxx - minn)

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

Submission status: Wrong Answer

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

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

ys = [0] + list(accumulate(xs))

rs = range(2, n-2)
v = []
for i in rs:
    j = bisect_left(ys, ys[i]//2)
    min1, max1 = sorted([ys[j], ys[i] - ys[j]])
    min2, max2 = sorted([ys[j-1], ys[i] - ys[j-1]])
    max_, min_ = (max1, min1) if max1 - min1 < max2 - min2 else (max2, min2)

    k = bisect_left(ys, (ys[-1] - ys[i])//2 + ys[i])
    min1, max1 = sorted([ys[k] - ys[i], ys[-1] - ys[k]])
    min2, max2 = sorted([ys[k-1] - ys[i], ys[-1] - ys[k-1]])
    max__, min__ = (max1, min1) if max1 - min1 < max2 - min2 else (max2, min2)

    minn, _, _, maxx = sorted([max_, min_, max__, min__])
    v.append(maxx - minn)

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

Submission status: Wrong Answer

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

    #累積和
    vs = [0] * n
    vs[0] = ai[0]
    for i in range(1, n):
        vs[i] = vs[i-1] + ai[i]

    ans = []
    for i in range(1,n-2):
        p = vs[i]
        for j in range(i+1, n-1):
            q = vs[j] - vs[i]
            for k in range(j+1, n):
                r = vs[k] - vs[j]
                s = vs[n-1] - vs[k]
                ans.append(abs(max(p,q,r,s) - min(p,q,r,s)))
                
    print(min(ans))

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
*A, = map(int, input().split())
X = sum(A)
A1 = [0,] + A[:]
for i in range(1,N+1):
    A1[i] = A1[i-1] + A1[i]
    if A1[i] >= X/4 and A1[i-1] < X/4:
        *p1, = range(i-50, i+51)
    if A1[i] >= X/2 and A1[i-1] < X/2:
        *p2, = range(i-50, i+51)
    if A1[i] >= 3*X/4 and A1[i-1] < 3*X/4:
        *p3, = range(i-50, i+51)
mincost = -1
for r1 in p1:
    for r2 in p2:
        for r3 in p3:
            if 1<=r1<r2<r3<=N:
                P = A1[r1]
                Q = A1[r2] - A1[r1]
                R = A1[r3] - A1[r2]
                S = A1[N] - A1[r3]
                cost = max(P,Q,R,S) - min(P,Q,R,S)
                if mincost < 0 or mincost >  cost:
                    mincost = cost
print(mincost)

Submission status: Wrong Answer

Solution code:
N = int(input())
*A, = map(int, input().split())
X = sum(A)
A1 = [0,] + A[:]
for i in range(1,N+1):
    A1[i] = A1[i-1] + A1[i]
    if A1[i] >= X/4 and A1[i-1] < X/4:
        *p1, = range(i-5, i+6)
    if A1[i] >= X/2 and A1[i-1] < X/2:
        *p2, = range(i-5, i+6)
    if A1[i] >= 3*X/4 and A1[i-1] < 3*X/4:
        *p3, = range(i-5, i+6)
mincost = -1
for r1 in p1:
    for r2 in p2:
        for r3 in p3:
            if 1<=r1<r2<r3<=N:
                P = A1[r1]
                Q = A1[r2] - A1[r1]
                R = A1[r3] - A1[r2]
                S = A1[N] - A1[r3]
                cost = max(P,Q,R,S) - min(P,Q,R,S)
                if mincost < 0 or mincost >  cost:
                    mincost = cost
print(mincost)

Submission status: Wrong Answer

Solution code:
N = int(input())
*A, = map(int, input().split())
X = sum(A)
A1 = [0,] + A[:]
for i in range(1,N+1):
    A1[i] = A1[i-1] + A1[i]
    if A1[i] >= X/4 and A1[i-1] < X/4:
        p1 = {i-2, i-1, i, i+1, i+2}
    if A1[i] >= X/2 and A1[i-1] < X/2:
        p2 = {i-2, i-1, i, i+1, i+2}
    if A1[i] >= 3*X/4 and A1[i-1] < 3*X/4:
        p3 = {i-2, i-1, i, i+1, i+2}
mincost = -1
for r1 in p1:
    for r2 in p2:
        for r3 in p3:
            if 1<=r1<r2<r3<=N:
                P = A1[r1]
                Q = A1[r2] - A1[r1]
                R = A1[r3] - A1[r2]
                S = A1[N] - A1[r3]
                cost = max(P,Q,R,S) - min(P,Q,R,S)
                if mincost < 0 or mincost >  cost:
                    mincost = cost
print(mincost)

Submission status: Wrong Answer

Solution code:
from itertools import *
n=int(input())
s=[0]+list(accumulate(map(int,input().split())))
l,r,ans=0,2,s[n]
for m in range(1,n-2):
    p,q=s[m],s[n]
    while abs(p-s[l]*2)>abs(p-s[l+1]*2):l+=1
    while abs(q-s[r]*2+p)>abs(q-s[r+1]*2+p):r+=1
    x=sorted([s[l],p-s[l],s[r]-p,q-s[r]])
    ans=min(ans,x[3]-x[0])
print(ans)

Submission status: Wrong Answer

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

csum = [0]

for a in A:
    csum.append(csum[-1] + a)

def csum_(a, b):
    return csum[b] - csum[a]

def search(ok, ng, n, m):
    if abs(ok-ng) <= 1:
            return ok
    mid = (ok+ng) // 2
    if csum_(m, mid) < csum_(mid, n):
        return search(mid, ng, n, m)
    else:
        return search(ok, mid, n, m)

fans = []

for c in range(2, n):
    d = search(1, c, c, 0)
    f = search(c+1, n, n, c)
    
    ans = []

    if abs(csum_(0, d) - csum_(d, c)) > abs(csum_(0, d+1) - csum_(d+1, c)):
        d += 1

    if abs(csum_(c, f) - csum_(c, f)) > abs(csum_(c, min(n, f+1)) - csum_(min(n, f+1), n)):
        f += 1
 
    ans.append(csum_(0, d))
    ans.append(csum_(d, c))
    ans.append(csum_(c, f))
    ans.append(csum_(f, n))

    fans.append(max(ans) - min(ans))

print(min(fans))

Submission status: Wrong Answer

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

    #累積和
    vs = [0] * n
    vs[0] = ai[0]
    for i in range(1, n):
        vs[i] = vs[i-1] + ai[i]

    ans = []
    for i in range(1,n):
        p = vs[i]
        for j in range(i+1, n):
            q = vs[j] - vs[i]
            for k in range(j+1, n):
                r = vs[k] - vs[j]
                s = vs[n-1] - vs[k]
                ans.append(abs(max(p,q,r,s) - min(p,q,r,s)))
                
    print(min(ans))

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    #累積和
    vs = [0] * n
    vs[0] = ai[0]
    for i in range(1, n):
        vs[i] = vs[i-1] + ai[i]

    ans = []
    for i in range(1,n):
        p = vs[i]
        for j in range(i+1, n):
            q = vs[j] - vs[i]
            for k in range(j+1, n):
                r = vs[k] - vs[j]
                s = vs[n-1] - vs[k]
                ans.append(max(p,q,r,s) - min(p,q,r,s))
                
    print(min(ans))

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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+1]):
        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: Wrong Answer

Solution code:
import statistics
import math

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

B = []
C = []
D = []
E = []
ureshimi = []
k = 0
l = 0

sumBC = sum(A[0:2])
sumDE = sum(A) - sumBC

for i in range(N-3):
    BC = A[0 : i + 2]
    s = 0
    for j in range(k, i + 2):
        s += BC[j]
        if j == i + 1:
            k = j 
            B = BC[0 : j ]
            C = BC[j  : N - i]
            break
        elif s + BC[j + 1] > sumBC / 2:
            k = j
            if BC[j + 1] / 2 >= sumBC / 2 - s:
                B = BC[0 : j + 1]
                C = BC[j + 1 : i + 2]
            else:
                B = BC[0 : j + 2]
                C = BC[j + 2 : i + 2]
        break
    sumBC += A[i + 2]
    DE = A[i + 2 : N + 1]
    s = sum(DE[0:l - i + 1 ])
    for j in range(l - i + 1 , N - i - 2):
        if j == N - i - 3:
            l = j + i 
            D = DE[0 : j ]
            E = DE[j  : N - i]
            break
        elif s + DE[j ] > sumDE / 2:
            l = j + i
            if DE[j ] / 2 >= sumDE / 2 - s:
                D = DE[0 : j ]
                E = DE[j : N - i]
            else:
                D = DE[0 : j + 1]
                E = DE[j + 1 : N - i]
        break
        s += DE[j]
    sumDE -= A[i + 2]

    ureshimi.append(max(sum(B), sum(C), sum(D), sum(E)) - min(sum(B), sum(C), sum(D), sum(E)))



print(min(ureshimi))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N = int(input())
A = [int(x) for x in input().split(' ')]
sA = [sum(A[:i]) for i in range(1, len(A) + 1)]

def score(first, second, third):
    PQRS = [sum(A[:first]), sum(A[first:second]),
            sum(A[second:third]), sum(A[third:])]
    return max(PQRS) - min(PQRS)

def search(second):
    first = bisect_left(sA[:second], sum(A[:second]) / 2)
    third = bisect_left([sa - sA[second] for sa in sA[second:]], sum(A[second:]) / 2) + second

    return min([score(fi, second, ti) for fi, ti in \
        [[first, third], [first+1, third], [first, third+1], [first+1, third+1]]])

best = float('inf')
for second in range(2, N - 2):
    best = min(best, search(second))
print(best)

Submission status: Wrong Answer

Solution code:
import statistics
import math

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

B = []
C = []
D = []
E = []
ureshimi = []
k = 0
l = 0

sumBC = sum(A[0:2])
sumDE = sum(A) - sumBC

for i in range(N-3):
    BC = A[0 : i + 2]
    s = 0
    for j in range(k, i + 2):
        s += BC[j]
        if j == i + 1:
            k = j 
            B = BC[0 : j ]
            C = BC[j  : N - i]
            break
        elif s + BC[j + 1] > sumBC / 2:
            k = j
            if BC[j + 1] / 2 >= sumBC / 2 - s:
                B = BC[0 : j + 1]
                C = BC[j + 1 : i + 2]
            else:
                B = BC[0 : j + 2]
                C = BC[j + 2 : i + 2]
            break
    sumBC += A[i + 2]
    DE = A[i + 2 : N + 1]
    s = sum(DE[0:l - i + 1 ])
    for j in range(l - i + 1 , N - i - 2):
        if j == N - i - 3:
            l = j + i 
            D = DE[0 : j ]
            E = DE[j  : N - i]
            break
        elif s + DE[j ] > sumDE / 2:
            l = j + i
            if DE[j ] / 2 >= sumDE / 2 - s:
                D = DE[0 : j ]
                E = DE[j : N - i]
            else:
                D = DE[0 : j + 1]
                E = DE[j + 1 : N - i]
            break
        s += DE[j]
    sumDE -= A[i + 2]

    ureshimi.append(max(sum(B), sum(C), sum(D), sum(E)) - min(sum(B), sum(C), sum(D), sum(E)))



print(min(ureshimi))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N = int(input())
A = [int(x) for x in input().split(' ')]

def score(first, second, third):
    PQRS = [sum(A[:first]), sum(A[first:second]),
            sum(A[second:third]), sum(A[third:])]
    return max(PQRS) - min(PQRS)

def search(second):
    left = A[:second]
    left_sums = [sum(left[:i]) for i in range(1, len(left)+1)]
    first = bisect_left(left_sums, left_sums[-1] / 2)
    right = A[second:]
    right_sums = [sum(right[:i]) for i in range(1, len(right)+1)]
    third = bisect_left(right_sums, right_sums[-1] / 2) + second

    return min([score(fi, second, ti) for fi, ti in \
        [[first, third], [first+1, third], [first, third+1], [first+1, third+1]]])

best = float('inf')
for second in range(2, N - 2):
    best = min(best, search(second))
print(best)

Submission status: Wrong Answer

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
while r + 1 < N and abs(pre[r+1] - pre[2] - pre[N] + pre[r+1]) < abs(pre[r] - pre[2] - pre[N] + pre[r]):
    r += 1
ans = max(pre[L],pre[2]-pre[L],pre[r]-pre[2],pre[N]-pre[r]) - \
      min(pre[L],pre[2]-pre[L],pre[r]-pre[2],pre[N]-pre[r])
        
for i in range(3,N):
    while L + 1 < i and abs(pre[L+1] - pre[i] + pre[L+1]) < abs(pre[L] - pre[i] + pre[L+1]):
        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: Wrong Answer

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
while r + 1 < N and abs(pre[r+1] - pre[2] - pre[N] + pre[r+1]) < abs(pre[r] - pre[2] - pre[N] + pre[r]):
    r += 1
ans = max(pre[L],pre[2]-pre[L],pre[r]-pre[2],pre[N]-pre[r]) - \
      min(pre[L],pre[2]-pre[L],pre[r]-pre[2],pre[N]-pre[r])
        
for i in range(3,N):
    while L + 1 < i and abs(pre[L+1] - pre[i] + pre[L+1]) < abs(pre[L] - pre[i] + pre[L+1]):
        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: Wrong Answer

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
while r + 1 < N and abs(pre[r+1] - pre[2] - pre[N] + pre[r+1]) < abs(pre[r] - pre[2] - pre[N] + pre[r]):
    r += 1
ans = max(pre[L],pre[2]-pre[L],pre[r]-pre[2],pre[N]-pre[r]) - \
      min(pre[L],pre[2]-pre[L],pre[r]-pre[2],pre[N]-pre[r])
        
for i in range(3,N-1):
    while L + 1 < i and abs(pre[L+1] - pre[i] + pre[L+1]) < abs(pre[L] - pre[i] + pre[L+1]):
        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: Wrong Answer

Solution code:
import statistics
import math

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

B = []
C = []
D = []
E = []
ureshimi = []
k = 0
l = 0

for i in range(N-3):
    BC = A[0 : i + 2]
    s = 0
    for j in range(k, i + 2):
        s += BC[j]
        if j == i + 1:
            k = j 
            B = BC[0 : j ]
            C = BC[j  : N - i]
            break
        elif s + BC[j + 1] > sum(BC) / 2:
            k = j
            if BC[j + 1] / 2 >= sum(BC) / 2 - s:
                B = BC[0 : j + 1]
                C = BC[j + 1 : i + 2]
            else:
                B = BC[0 : j + 2]
                C = BC[j + 2 : i + 2]
            break
    DE = A[i + 2 : N + 1]
    s = sum(DE[0:l - i + 1 ])
    for j in range(l - i + 1 , N - i - 2):
        if j == N - i - 3:
            l = j + i 
            D = DE[0 : j ]
            E = DE[j  : N - i]
            break
        elif s + DE[j ] > sum(DE) / 2:
            l = j + i
            if DE[j ] / 2 >= sum(DE) / 2 - s:
                D = DE[0 : j ]
                E = DE[j : N - i]
            else:
                D = DE[0 : j + 1]
                E = DE[j + 1 : N - i]
            break
        s += DE[j]
    ureshimi.append(max(sum(B), sum(C), sum(D), sum(E)) - min(sum(B), sum(C), sum(D), sum(E)))



print(min(ureshimi))

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import combinations
N = int(input())
A = np.array(list(map(int, input().split())), dtype= int)
X = A.sum()
A1 = np.cumsum(A)
mincost1 = -1
for r2 in range(1,N-2):
    Y = A1[r2]
    mincost2 = -1
    r1 = 1
    for i in range(0,r2):
        L = A1[i]
        R = Y - L
        cost = np.abs(R-L)
        if mincost2 < 0 or mincost2 >  cost:
            mincost2 = cost
            r1 = i
    P = A1[r1]
    Q = Y - A1[r1]

    mincost3 = -1
    r3 = N-1
    for i in range(r2+1,N):
        L = A1[i] - Y
        R = X - Y - L
        cost = np.abs(R-L)
        if mincost3 < 0 or mincost3 >  cost:
            mincost3 = cost
            r3 = i

    R = A1[r3]-Y
    S = X-A1[r3]
    cost = max(P,Q,R,S) - min(P,Q,R,S)
    print(r1,r2,r3)
    print(P,Q,R,S,cost)
    if mincost1 < 0 or mincost1 >  cost:
            mincost1 = cost
print(mincost1)

Submission status: Wrong Answer

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]
 
# initialize
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 + 1

# time complexity: O(N)?
for mid_sep in range(2, N - 1):
    left_sum = cuml_A_list[mid_sep - 1]
    right_sum = cuml_A_list[-1] - cuml_A_list[mid_sep - 1]
    for left_sep_cand in range(left_sep, mid_sep):
        # obtain the best first separation position
        if abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep_cand]) < abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep]):
            left_sep = left_sep_cand
        else:
            break
    for right_sep_cand in range(right_sep, N):
        # obtain the best third separation position
        if abs(cuml_A_list[-1] - cuml_A_list[right_sep_cand] - (cuml_A_list[right_sep_cand] - cuml_A_list[mid_sep]))\
            < abs(cuml_A_list[-1] - cuml_A_list[right_sep] - (cuml_A_list[right_sep] - cuml_A_list[mid_sep])):
            right_sep = right_sep_cand
        else:
            break
    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: Wrong Answer

Solution code:
import numpy as np
from itertools import combinations
N = int(input())
A = np.array(list(map(int, input().split())), dtype= int)
X = A.sum()
A1 = np.cumsum(A)
mincost1 = -1
for r2 in range(2,N-1):
    Y = A1[r2]
    mincost2 = -1
    r1 = 1
    for i in range(1,r2):
        L = A1[i]
        R = Y - L
        cost = np.abs(R-L)
        if mincost2 < 0 or mincost2 >  cost:
            mincost2 = cost
            r1 = i
    P = A1[r1]
    Q = Y - A1[r1]

    mincost3 = -1
    r3 = N-1
    for i in range(r2+1,N):
        L = A1[i] - Y
        R = X - Y - L
        cost = np.abs(R-L)
        if mincost3 < 0 or mincost3 >  cost:
            mincost3 = cost
            r3 = i

    R = A1[r3]-Y
    S = X-A1[r3]
    cost = max(P,Q,R,S) - min(P,Q,R,S)
    if mincost1 < 0 or mincost1 >  cost:
            mincost1 = cost
print(mincost1)

Submission status: Wrong Answer

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

def func2(a,i):   
    bb,bc=func3(a[:i])
    cb,cc=func3(a[i:])
    l=[bb,bc,cb,cc]
    return abs(max(l)-min(l))

def func3(b):
    s=10**10
    m,n=0,sum(b)
    for j in range(len(b)):
        t=abs(m-n)
        if s>t:
            s=t
        else:
            break
        m+=b[j]
        n-=b[j]
    return m-b[j-1],n+b[j-1]

m=10**10
for i in range(2,n-1):
    t=func2(a,i)
    if t<m:
        m=t
print(m)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import combinations
N = int(input())
A = np.array(list(map(int, input().split())), dtype= int)
X = A.sum()
A1 = np.cumsum(A)
mincost = -1
for r1, r2, r3 in combinations(range(1,N), 3):
    P = A1[r1]
    Q = A1[r2] - A1[r1]
    R = A1[r3]-A1[r2]
    S = X-A1[r3]
    cost = max(P,Q,R,S) - min(P,Q,R,S)
    if mincost < 0 or mincost >  cost:
        mincost = cost
print(mincost)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product
N = int(input())
A = np.array(list(map(int, input().split())), dtype= int)
X = A.sum()
A1 = np.cumsum(A)

mincost = -1
r2 = 2
for i in range(2,N-1):
    L = A1[i]
    R = X - L
    cost = np.abs(R-L)
    if mincost < 0 or mincost >  cost:
        mincost = cost
        r2 = i

Y = A1[r2]
mincost = -1
r1 = 1
for i in range(1,r2):
    L = A1[i]
    R = Y - L
    cost = np.abs(R-L)
    if mincost < 0 or mincost >  cost:
        mincost = cost
        r1 = i
P = A1[r1]
Q = Y - A1[r1]

mincost = -1
r3 = N-1
for i in range(r2+1,N):
    L = A1[i] - Y
    R = X - Y - L
    cost = np.abs(R-L)
    if mincost < 0 or mincost >  cost:
        mincost = cost
        r3 = i

R = A1[r3]-Y
S = X-A1[r3]
cost = max(P,Q,R,S) - min(P,Q,R,S)
print(cost)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))
def solve(x):
  def h(i,j):
    m = (C[j]+C[i])//2
    k = bisect(C, m, lo=i+1,hi=j)

    _,a,b = min((abs(m-C[x]),C[x]-C[i],C[j]-C[x]) for x in (k-1,k))
    return a,b

  L = h(0,x)+h(x,N)
  return max(L)-min(L)

m = bisect(C,C[N]//2,hi=2,lo=N-2)

best = solve(m)
exit()
i = m+1
while i < N-1 and abs(abs(C[N]-C[i])-abs(C[i])) < best*2:
  best = min(best, solve(i))
  i += 1

i = m-1
while i > 1 and abs(abs(C[N]-C[i])-abs(C[i])) < best*2:
  best = min(best, solve(i))
  i -= 1


print(best)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
p = 2 * 100000 * 1000000000
n = int(input())
nums = list(map(int,input().split()))

sums = [None for i in range(n)]
sums[0] = nums[0]
for i in range(n-1):
    sums[i+1] = sums[i] + nums[i+1]
    
def check(T,p):
    i = 0
    List = []
    for j in range(4):
        s = 0
        while s + T[i] <= p:
            s += T[i]
            i += 1
            if i == n:
                List.append(s)
                return n, List
        List.append(s)
    return i, List


def bs(p):
    left = 0
    right = p
    while right - left > 1:
        mid = (left+right)//2
        v, List = check(nums, mid)
        if v >= n:
            right = mid
        else:
            left = mid

    big = max(right,left)
    v, List = check(nums, big)
    return List
            

List = bs(p)
print(max(List) - min(List))

Submission status: Wrong Answer

Solution code:
#coding:utf-8
p = 2 * 100000 * 1000000000
n = int(input())
nums = list(map(int,input().split()))

sums = [None for i in range(n)]
sums[0] = nums[0]
for i in range(n-1):
    sums[i+1] = sums[i] + nums[i+1]
    
def check(T,p):
    i = 0
    List = []
    for j in range(4):
        s = 0
        while s + T[i] <= p:
            s += T[i]
            i += 1
            if i == n:
                List.append(s)
                return n, List
        List.append(s)
    return i, List


def bs(p):
    left = 0
    right = p
    while right - left > 1:
        mid = (left+right)//2
        v, List = check(nums, mid)
        if v >= n:
            right = mid
        else:
            left = mid

    v, List = check(nums, right)
    return List
            

List = bs(p)
print(max(List) - min(List))

Submission status: Wrong Answer

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

def func2(a,i):   
    bb,bc=func3(a[:i])
    cb,cc=func3(a[i:])
    *l,=map(sum,[bb,bc,cb,cc])
    return abs(max(l)-min(l))

def func3(b):
    i=0
    s=10**10
    for j in range(1,len(b)):
        t=abs(sum(b[:j])-sum(b[j:]))
        if s>t:
            s=t
            i=j
    return b[:i],b[i:]

m=10**10
for i in range(2,n-2):
    t=func2(a,i)
    if t<m:
        m=t
print(m)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
p = 10000000000
n = int(input())
nums = list(map(int,input().split()))

sums = [None for i in range(n)]
sums[0] = nums[0]
for i in range(n-1):
    sums[i+1] = sums[i] + nums[i+1]
    
def check(T,p):
    i = 0
    List = []
    for j in range(4):
        s = 0
        while s + T[i] <= p:
            s += T[i]
            i += 1
            if i == n:
                List.append(s)
                return n, List
        List.append(s)
    return i, List


def bs(p):
    left = 0
    right = p
    while right - left > 1:
        mid = (left+right)//2
        v, List = check(nums, mid)
        if v >= n:
            right = mid
        else:
            left = mid

    v, List = check(nums, right)
    return List
            

List = bs(p)
print(max(List) - min(List))

Submission status: Wrong Answer

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

def func2(a,i):
    s1=0
    m1=10**10
    for j in range(1,i):
        t=abs(sum(a[:j])-sum(a[j:i]))
        if t<m1:
            m1=t
            s1=j
        else:
            break
    
    s2=0
    m2=10**10
    for j in range(i+1,len(a)):
        t=abs(sum(a[i:j])-sum(a[j:]))
        if t<m2:
            m2=t
            s2=j
        else:
            break
            
    *l,=map(sum,[a[:s1],a[s1:i],a[i:s2],a[s2:]])
    return abs(max(l)-min(l))

m=10**10
for i in range(2,n-2):
    t=func2(a,i)
    if t<m:
        m=t
print(m)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect

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



def solve(x):
  def h(i,j):
    m = (C[j]+C[i])//2
    k = bisect(C, m, lo=i+1,hi=j)

    _,a,b = min((abs(m-C[x]),C[x]-C[i],C[j]-C[x]) for x in (k-1,k))
    return a,b

  L = h(0,x)+h(x,N)
  return max(L)-min(L)

m = bisect(C,C[N]//2,hi=2,lo=N-1)

best = solve(m)

i = m+1
while i < N-1 and abs(abs(C[N]-C[i])-abs(C[i])) < best*2:
  best = min(best, solve(i))
  i += 1

i = m-1
while i > 0 and abs(abs(C[N]-C[i])-abs(C[i])) < best*2:
  best = min(best, solve(i))
  i -= 1


print(best)

Submission status: Wrong Answer

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

def func2(a):
    m=10**9+1
    mi=0
    for i in range(len(a)):
        try:
            t=abs(sum(a[:i])-sum(a[i:]))
            if t<m:
                m=t
                mi=i   
        except:
            pass
    return a[:mi],a[mi:]
  
b,c=func2(a)
l=[]
if len(b)!=1:
    bb,bc=func2(b)
    if len(c)!=1:
        cb,cc=func2(c)
        l.append([bb,bc,cb,cc])
    else:
        if len(bb)!=1:
            bbb,bbc=func2(bb)
            l.append([bbb,bbc,bc,c])
        else:
            bcb,bcc=func2(bc)
            l.append([bb,bcb,bcc,c])
if len(c)!=1:
    cb,cc=func2(c)
    if len(b)!=1:
        bb,bc=func2(b)
        l.append([bb,bc,cb,cc])
    else:
        if len(cb)!=1:
            cbb,cbc=func2(cb)
            l.append([b,cbb,cbc,cc])
        else:
            ccb,ccc=func2(cc)
            l.append([b,cb,ccb,ccc])
            
v=10**9+1
for li in l:
    *t,=map(sum,li)
    tt=abs(max(t)-min(t))
    if v>tt:
        v=tt
print(v)

Submission status: Wrong Answer

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

SUM=sum(A)

left=0
i=0
while left<SUM/4:
    left+=A[i]
    i+=1


right=0
j=N-1
while right<SUM/4:
    right+=A[j]
    j-=1



    
def middlecut(i,j):
    left=sum(A[:i])
    right=sum(A[j:])
    ANS=10**16

    for k in range(i,j):
        midle=sum(A[i:k])
        midri=sum(A[k:j])

        if ANS>max(left,right,midle,midri)-min(left,right,midle,midri):
            ANS=max(left,right,midle,midri)-min(left,right,midle,midri)

    return ANS


ANS=10**16
for l in range(max(0,i-6),min(N,i+6)):
    for m in range(max(0,j-6),min(N,j+6)):
        ANS=min(ANS,middlecut(l,m))

print(ANS)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
d = 0
for i in range(0,n-3):
    for j in range(1+i,n-2):
        for k in range(1+j,n-1):
            list = [0,0,0,0]
            for index,x in enumerate(a):
                if index < (i+1):
                    list[0] += x
                elif (i+1) <= index and index < (j+1):
                    list[1]+= x
                elif (j+1) <= index and index < (k+1):
                    list[2] += x
                else:
                    list[3] += x
            tmp_max = list[0]
            tmp_min = list[0]
            for tmp in list:
                if tmp_max < tmp:
                    tmp_max = tmp
                if tmp_min > tmp:
                    tmp_min = tmp
            if i == 0 and j == 1 and k == 2:
                d = tmp_max - tmp_min
            else:
                if d > (tmp_max - tmp_min):
                    d = (tmp_max - tmp_min)
            print("i:"+str(i)+"j:"+str(j)+"k:"+str(k)+"d"+str(d))
print(d)

Submission status: Wrong Answer

Solution code:
import numpy as np

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


def s_cand(seq, n):
    l = len(seq)
    candidates = []
    s = sum(seq) / n
    su = 0
    for i in range(l):
        su += seq[i]
        if su == s:
            candidates.append(i+1)
            break
        elif su > s:
            if i > 0:
                candidates.append(i)
            if i < l - 1:
                candidates.append(i+1)
            break
    return candidates

ca = []
cand = s_cand(a, 4)
for c in cand:
    after = a[c:]
    canda = s_cand(after, 3)
    for cca in canda:
        after = after[cca:]
        candaa = s_cand(after, 2)
        for ccaa in candaa:
            ca.append([c, c + cca, c + cca + ccaa])
out = 1000000000
for hoge in ca:
    h = [sum(a[:hoge[0]]), sum(a[hoge[0]:hoge[1]]),
             sum(a[hoge[1]:hoge[2]]), sum(a[hoge[2]:])]
    o = max(h) - min(h)
    if o < out:
        out = o
print(out)