Problem: 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.

Submission attempts (in order):
from itertools import accumulate

N = int( input())
A = list( map( int, input().split()))
a, b = 0, 2
ans = 10**9 + 1
S = list(accumulate(A))
for i in range(1,N-1):
    while S[a] < S[i] - S[a+1]:
        a += 1
    b = max(b,i+1)
    while S[b] - S[i] < S[-1] - S[b+1]:
        b += 1
    ans = min( ans, max(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]) - min(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]))
print(ans)

from itertools import accumulate
from bisect import bisect

def half(T, h):
    b = bisect(T,h)
    if abs(T[b-1]*2 - T[-1] - T[0]) <= abs(T[b]*2 - T[-1] - T[0]):
        return T[b-1] - T[0], T[-1]-T[b-1]
    return T[b] - T[0], T[-1]-T[b]
N = int( input())
A = list( map( int, input().split()))
S = [0] + list( accumulate(A))
ans = 10**9+1
for i in range(2, N-1):
    x, y = half(S[:i+1], S[i]//2)
    z, w = half(S[i:], (S[i] + S[-1])//2)
    print(x,y,z,w)
    m = min(x,y,z,w)
    M = max(x,y,z,w)
    if M-m < ans:
        ans = M-m
print(ans)

N = int(input())
*A, = map(int, input().split())
a = sum(A)/4
B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 + A[i] <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 + A[i] <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 + A[i] <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C1 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])
    
B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 + A[i] <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 + A[i] <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C2 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 + A[i] <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 + A[i] <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C3 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 + A[i] <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C4 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 + A[i] <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 + A[i] <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C5 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 + A[i] <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C6 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 + A[i] <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C7 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C8 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

print(min([C1, C2, C3, C4, C5, C6, C7, C8]))

from itertools import accumulate

N = int( input())
A = list( map( int, input().split()))
a, b = 0, 2
ans = 10**9 + 1
S = list(accumulate(A))
for i in range(1,N-2):
    while S[a] < S[i] - S[a+1]:
        a += 1
    b = max(b,i+1)
    while S[b] - S[i] < S[-1] - S[b+1]:
        b += 1
    ans = min( ans, max(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]) - min(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]))
print(ans)

Verdicts: Runtime Error

Wrong Answer

Wrong Answer

Accepted