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 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 - 1):
	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)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N = int(input())
A = list(map(int, input().split()))
S1 = [A[0]]*N
S2 = [A[-1]]*N
for i in range(1, N):
    S1[i] = S1[i-1]+A[i]
    S2[i] = S2[i-1]+A[N-i-1]
ans = S1[-1]
for i in range(1, N-2):
    s1 = S1[i]
    b = bisect_left(S1, s1/2)
    if abs(S1[b]-s1/2)>abs(s1/2-S1[b-1]):
        b-=1
    P, Q = S1[b], s1-S1[b]
    s2 = S2[N-i-2]
    c = bisect_left(S2, s2/2)
    if abs(S1[c]-s2/2)>abs(s2/2-S1[c-1]):
        c-=1
    R, S = S2[c], s2-S2[c]
    res = max(P, Q, R, S)-min(P, Q, R, S)
    ans = min(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

def main():
    N = int(input())
    As = list(map(int, input().split()))
    ruiseki = []
    tmp = 0
    for e in As:
        tmp += e
        ruiseki.append(tmp)

    ans = tmp
    # first_separator は最初に半分に割る区切り(index番目の前に置くことにする)(0-origin indexの2の前が最小)
    for _first_separator in range(2, N-1):
        d('fsep', _first_separator)
        for dd in [-1,0,1]:
            first_separator = _first_separator + dd
            lseps = separate_seq(ruiseki, 0, first_separator)
            rseps = separate_seq(ruiseki, first_separator, N)
            for lsep in lseps:
                for rsep in rseps:
                    s1 = sum_of_segment(ruiseki, 0, lsep)
                    s2 = sum_of_segment(ruiseki, lsep, first_separator)
                    s3 = sum_of_segment(ruiseki, first_separator, rsep)
                    s4 = sum_of_segment(ruiseki, rsep, N)
                    if min(s1, s2, s3, s4) == 0:
                        d('error')
                        continue
                    diff = max(s1, s2, s3, s4) - min(s1, s2, s3, s4)
                    ans = diff if ans > diff else ans
                    d('ans', ans, 'diff', diff, 'sums', s1, s2, s3, s4, 'seps', lsep, first_separator, rsep)
    print(ans)

def d(*args):
#    print(*args)
    pass


def separate_seq(seq, l, r):
    '''
    配列の総和が真ん中になりそうなところを探す
    '''
    d('ss in', seq, l, r)
    S = (seq[r-1]-seq[l])/2 + seq[l]
    ret = []
    lidx = bisect.bisect_left(seq, S)
    ret.append(lidx-1)
    ret.append(lidx)
    ret.append(lidx+1)
    d('ss out', seq, 'S', S, 'ret', ret, lidx)
    return ret


def sum_of_segment(seq, start, end):
    ret = seq[0]
    if start == 0:
        ret = seq[end-1]
    elif end-1!=0:
        ret = seq[end-1] - seq[max(start-1,0)]
    d('sos out', seq, start, end, ret)
    return ret

main()

Submission status: Wrong Answer

Solution code:
import bisect

def main():
    N = int(input())
    As = list(map(int, input().split()))
    ruiseki = []
    tmp = 0
    for e in As:
        tmp += e
        ruiseki.append(tmp)

    ans = tmp
    # first_separator は最初に半分に割る区切り(index番目の前に置くことにする)(0-origin indexの2の前が最小)
    for first_separator in range(1, N):
        d('fsep', first_separator)
        lseps = separate_seq(ruiseki, 0, first_separator)
        rseps = separate_seq(ruiseki, first_separator, N)
        for lsep in lseps:
            for rsep in rseps:
                s1 = sum_of_segment(ruiseki, 0, lsep)
                s2 = sum_of_segment(ruiseki, lsep, first_separator)
                s3 = sum_of_segment(ruiseki, first_separator, rsep)
                s4 = sum_of_segment(ruiseki, rsep, N)
                if min(s1, s2, s3, s4) == 0:
                    d('error')
                    continue
                diff = max(s1, s2, s3, s4) - min(s1, s2, s3, s4)
                ans = diff if ans > diff else ans
                d('ans', ans, 'diff', diff, 'sums', s1, s2, s3, s4, 'seps', lsep, first_separator, rsep)
    print(ans)

def d(*args):
#    print(*args)
    pass


def separate_seq(seq, l, r):
    '''
    配列の総和が真ん中になりそうなところを探す
    '''
    d('ss in', seq, l, r)
    S = (seq[r-1]-seq[l])/2 + seq[l]
    ret = []
    lidx = bisect.bisect_left(seq, S)
    ret.append(lidx-1)
    ret.append(lidx)
    ret.append(lidx+1)
    d('ss out', seq, 'S', S, 'ret', ret, lidx)
    return ret


def sum_of_segment(seq, start, end):
    ret = seq[0]
    if start == 0:
        ret = seq[end-1]
    elif end-1!=0:
        ret = seq[end-1] - seq[max(start-1,0)]
    d('sos out', seq, start, end, ret)
    return ret

main()

Submission status: Wrong Answer

Solution code:
import bisect

def main():
    N = int(input())
    As = list(map(int, input().split()))
    ruiseki = []
    tmp = 0
    for e in As:
        tmp += e
        ruiseki.append(tmp)

    ans = tmp
    # first_separator は最初に半分に割る区切り(index番目の前に置くことにする)(0-origin indexの2の前が最小)
    for first_separator in range(2, N-1):
        d('fsep', first_separator)
        lseps = separate_seq(ruiseki, 0, first_separator)
        rseps = separate_seq(ruiseki, first_separator, N)
        for lsep in lseps:
            for rsep in rseps:
                s1 = sum_of_segment(ruiseki, 0, lsep)
                s2 = sum_of_segment(ruiseki, lsep, first_separator)
                s3 = sum_of_segment(ruiseki, first_separator, rsep)
                s4 = sum_of_segment(ruiseki, rsep, N)
                if min(s1, s2, s3, s4) == 0:
                    d('error')
                    continue
                diff = max(s1,s2,s3,s4) - min(s1,s2,s3,s4)
                ans = diff if ans > diff else ans
                d('ans', ans, 'diff', diff, 'sums', s1, s2, s3, s4, 'seps', lsep, first_separator, rsep)
    print(ans)


def d(*args):
#    print(*args)
    pass


def calc(num, seq):
    pass

def separate_seq(seq, l, r):
    '''
    配列の総和が真ん中になりそうなところを探す
    '''
    d('ss in', seq, l, r)
    S = (seq[r-1]-seq[l])/2 + seq[l]
    ret = []
    lidx = bisect.bisect_left(seq, S)
    ret.append(lidx-1)
    ret.append(lidx)
    ret.append(lidx+1)
    d('ss out', seq, 'S', S, 'ret', ret, lidx)
    return ret


def sum_of_segment(seq, start, end):
    ret = seq[0]
    if start == 0:
        ret = seq[end-1]
    elif end-1!=0:
        ret = seq[end-1] - seq[max(start-1,0)]
    d('sos out', seq, start, end, ret)
    return ret

main()

Submission status: Wrong Answer

Solution code:
import bisect

def main():
    N = int(input())
    As = list(map(int, input().split()))
    ruiseki = []
    tmp = 0
    for e in As:
        tmp += e
        ruiseki.append(tmp)

    ans = tmp
    # first_separator は最初に半分に割る区切り(index番目の前に置くことにする)(0-origin indexの2の前が最小)
    for first_separator in range(2, N-1 -1):
        lseps = separate_seq(ruiseki[0:first_separator])
        rseps = list(map(lambda x: x + first_separator, separate_seq(ruiseki[first_separator:N])))
        for lsep in lseps:
            for rsep in rseps:
                s1 = sum_of_segment(ruiseki, 0, lsep)
                s2 = sum_of_segment(ruiseki, lsep, first_separator)
                s3 = sum_of_segment(ruiseki, first_separator, rsep)
                s4 = sum_of_segment(ruiseki, rsep, N)
                diff = max(s1,s2,s3,s4) - min(s1,s2,s3,s4)
                ans = diff if ans > diff else ans
        d('ans', ans, 'sums', s1, s2, s3, s4, 'seps', lsep, first_separator, rsep)
    print(ans)


def d(*args):
#    print(args)
    pass


def calc(num, seq):
    pass

def separate_seq(seq):
    '''
    配列の総和が真ん中になりそうなところを探す O(n)
    '''
    S = seq[-1] - seq[0]
    tmp = 10**20
    ret = -1
    lidx = bisect.bisect_left(seq, S/2)
    return lidx, lidx+1

    for idx in range(1, len(seq)):
        left = seq[idx] - seq[0]
        right = seq[len(seq)-1] - seq[idx]
        tt = abs(left-right)
        if tmp > tt:
            tmp = tt
            ret = idx
    d('ss', seq, ret)
    return ret


def sum_of_segment(seq, start, end):
    d('sos', seq, start, end)
    if end==0:
        return seq[0]
    return seq[end-1] - seq[start]

main()

Submission status: Wrong Answer

Solution code:


def main():
    N = int(input())
    As = list(map(int, input().split()))
    ruiseki = []
    tmp = 0
    for e in As:
        tmp += e
        ruiseki.append(tmp)

    ans = tmp
    # first_separator は最初に半分に割る区切り(index番目の前に置くことにする)(0-origin indexの2の前が最小)
    for first_separator in range(2, N-1 -1):
        lsep = separate_seq(ruiseki[0:first_separator])
        rsep = first_separator + separate_seq(ruiseki[first_separator:N])
        s1 = sum_of_segment(ruiseki, 0, lsep)
        s2 = sum_of_segment(ruiseki, lsep, first_separator)
        s3 = sum_of_segment(ruiseki, first_separator, rsep)
        s4 = sum_of_segment(ruiseki, rsep, N)
        diff = max(s1,s2,s3,s4) - min(s1,s2,s3,s4)
        ans = diff if ans > diff else ans
        d('ans', ans, 'sums', s1, s2, s3, s4, 'seps', lsep, first_separator, rsep)
    print(ans)


def d(*args):
    print(args)
    pass


def calc(num, seq):
    pass

def separate_seq(seq):
    '''
    配列の総和が真ん中になりそうなところを探す O(n)
    '''
    tmp = 10**20
    ret = -1
    for idx in range(1, len(seq)):
        left = seq[idx] - seq[0]
        right = seq[len(seq)-1] - seq[idx]
        tt = abs(left-right)
        if tmp > tt:
            tmp = tt
            ret = idx
    d('ss', seq, ret)
    return ret


def sum_of_segment(seq, start, end):
    d('sos', seq, start, end)
    if end==0:
        return seq[0]
    return seq[end-1] - seq[start]

main()

Submission status: Wrong Answer

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

tmp = 0
sum = [0 for i in range(N)]

for a, b in enumerate(A):
    tmp += b
    sum[a] = tmp


def search(l, r):
    mid = lower_bound(l, r + 1, get_sum(l, r) / 2 + (0 if l == 0 else sum[l]))
    for i in range(mid - 2, mid + 3):
        if l <= i and i + 1 <= r:
            yield get_sum(l, i), get_sum(i + 1, r)


#
# 10
# 10 71 84 33 6 47 23 25 52 64
## 81 84 86 164
## 81 84 134 116
## 81 123 95 116
## (81, 117, 101, 116)

def lower_bound(l, r, val):
    while r-l > 1:
        mid = (r + l) // 2
        if sum[mid] <= val:
            l = mid
        else:
            r = mid
    return l


def get_sum(l, r):
    return sum[r] - (0 if l == 0 else sum[l - 1])


ans = tmp

for ind in range(1, N - 2):
    for l1, r1 in search(0, ind):
        for l2, r2 in search(ind + 1, N - 1):
            # print(ind)
            # print(l1, r1, l2, r2)
            t = l1, r1, l2, r2
            # print(t)
            ans = min(ans, max(t) - min(t))
            # if ans == 36:
            #     print("ans   ", t)

print(ans)

Submission status: Wrong Answer

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

tmp = 0
sum = [0 for i in range(N)]

for a, b in enumerate(A):
    tmp += b
    sum[a] = tmp


def search(l, r):
    mid = lower_bound(l, r + 1, get_sum(l, r) / 2 + sum[l])
    for i in range(mid - 2, mid + 3):
        if l <= i and i + 1 <= r:
            yield get_sum(l, i), get_sum(i + 1, r)


#
# 10
# 10 71 84 33 6 47 23 25 52 64
## 81 84 86 164
## 81 84 134 116
## 81 123 95 116
## (81, 117, 101, 116)

def lower_bound(l, r, val):
    while r-l > 1:
        mid = (r + l) // 2
        if sum[mid] <= val:
            l = mid
        else:
            r = mid
    return l


def get_sum(l, r):
    return sum[r] - (0 if l == 0 else sum[l - 1])


ans = tmp

for ind in range(1, N - 2):
    for l1, r1 in search(0, ind):
        for l2, r2 in search(ind + 1, N - 1):
            # print(ind)
            # print(l1, r1, l2, r2)
            t = l1, r1, l2, r2
            # print(t)
            ans = min(ans, max(t) - min(t))
            # if ans == 36:
            #     print("ans   ", t)

print(ans)

Submission status: Wrong Answer

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

tmp = 0
sum = [0 for i in range(N)]

for a, b in enumerate(A):
    tmp += b
    sum[a] = tmp


def search(l, r):
    mid = lower_bound(l, r + 1, get_sum(l, r) / 2)
    for i in range(mid - 2, mid + 3):
        if l <= i and i + 1 <= r:
            yield get_sum(l, i), get_sum(i + 1, r)


#
# 10
# 10 71 84 33 6 47 23 25 52 64
## 81 84 86 164
## 81 84 134 116
## 81 123 95 116

def lower_bound(l, r, val):
    while r-l > 1:
        mid = (r + l) // 2
        if val < sum[mid]:
            r = mid
        else:
            l = mid
    return l


def get_sum(l, r):
    return sum[r] - (0 if l == 0 else sum[l - 1])


ans = tmp

for ind in range(1, N - 2):
    for l1, r1 in search(0, ind):
        for l2, r2 in search(ind + 1, N - 1):
            # print(ind)
            # print(l1, r1, l2, r2)
            ans = min(ans, max(l1, r1, l2, r2) - min(l1, r1, l2, r2))

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

tmp = 0
sum = [0 for i in range(N)]

for a, b in enumerate(A):
    tmp += b
    sum[a] = tmp


def search(l, r):
    # print("l = " , l)
    mid = lower_bound(l, r + 1, get_sum(l, r) / 2)
    # print("hoge ", l, r, mid)
    for i in range(mid - 2, mid + 3):
        if l <= i and i + 1 <= r:
            yield get_sum(l, i), get_sum(i + 1, r)


#
# 10
# 10 71 84 33 6 47 23 25 52 64
## 81 84 86 164
## 81 84 134 116
## 81 123 95 116

def lower_bound(l, r, val):
    while r-l > 1:
        mid = (r + l) // 2
        if val <= sum[mid]:
            l = mid
        else:
            r = mid
    return l


def get_sum(l, r):
    return sum[r] - (0 if l == 0 else sum[l - 1])


ans = tmp

for ind in range(1, N - 2):
    for l1, r1 in search(0, ind):
        for l2, r2 in search(ind + 1, N - 1):
            # print(ind)
            # print(l1, r1, l2, r2)
            ans = min(ans, max(l1, r1, l2, r2) - min(l1, r1, l2, r2))

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

tmp = 0
sum = [0 for i in range(N)]

for a, b in enumerate(A):
    tmp += b
    sum[a] = tmp


def search(l, r):
    # print("l = " , l)
    mid = bisect.bisect_left(sum, get_sum(l, r) / 2, l, r + 1) + l
    # print("hoge ", l, r, mid)
    for i in range(mid - 2, mid + 3):
        if l <= i and i + 1 <= r:
            yield get_sum(l, i), get_sum(i + 1, r)


#
# 10
# 10 71 84 33 6 47 23 25 52 64
## 81 84 86 164
## 81 84 134 116
## 81 123 95 116
def get_sum(l, r):
    return sum[r] - (0 if l == 0 else sum[l - 1])


ans = tmp

for ind in range(1, N - 2):
    for l1, r1 in search(0, ind):
        for l2, r2 in search(ind + 1, N - 1):
            # print(ind)
            # print(l1, r1, l2, r2)
            ans = min(ans, max(l1, r1, l2, r2) - min(l1, r1, l2, r2))

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect


def get_sum(l, r):
    return sum[r] - (0 if l == 0 else sum[l - 1])


def search(l, r):
    mid = bisect.bisect_left(sum, get_sum(l, r) / 2, l, r + 1)
    if l <= mid - 1 and mid <= r:
        yield get_sum(l, mid - 1), get_sum(mid, r)
    if l <= mid and mid + 1 <= r:
        yield get_sum(l, mid), get_sum(mid + 1, r)
    if l <= mid + 1 and mid + 2 <= r:
        yield get_sum(l, mid + 1), get_sum(mid + 2, r)


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

tmp = 0
sum = [0 for i in range(N)]

for a, b in enumerate(A):
    tmp += b
    sum[a] = tmp

ans = tmp

for ind in range(1, N - 2):
    for l1, r1 in search(0, ind):
        for l2, r2 in search(ind + 1, N - 1):
            ans = min(ans, max(l1, r1, l2, r2) - min(l1, r1, l2, r2))

print(ans)

def search(l, r):
    mid = bisect.bisect_left(sum, get_sum(l, r) / 2, l, r + 1)
    if l <= mid - 1 and mid <= r:
        yield get_sum(l, mid - 1), get_sum(mid, r)
    if l <= mid and mid + 1 <= r:
        yield get_sum(l, mid), get_sum(mid + 1, r)
    if l <= mid + 1 and mid + 2 <= r:
        yield get_sum(l, mid + 1), get_sum(mid + 2, r)


def get_sum(l, r):
    return sum[r] - (0 if l == 0 else sum[l - 1])

Submission status: Wrong Answer

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

i, k = 1, 3
p, q, r, s = a[0], a[1], a[2], sum(a[3:])
ans = abs(max([p, q, r, s]) - min([p, q, r, s]))
for j in range(2, n-2):
    q += a[j]
    while abs((q-a[i]) - (p+a[i])) < abs(q - p):
        p += a[i]
        q -= a[i]
        i += 1

    r -= a[j]
    while abs((s-a[k]) - (r+a[k])) < abs(s - r):
        r += a[k]
        s -= a[k]
        k += 1

    pqrs = [p, q, r, s]
    ans = min(ans, abs(max(pqrs) - min(pqrs)))
    # print(i, j, k, ans, pqrs)
    
print(ans)

Submission status: Wrong Answer

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

i, k = 1, 3
p, q, r, s = a[0], a[1], a[2], sum(a[3:])
ans = abs(max([p, q, r, s]) - min([p, q, r, s]))
for j in range(2, n-2):
    q += a[j]
    while abs((q-a[i]) - (p+a[i])) <= abs(q - p):
        p += a[i]
        q -= a[i]
        i += 1

    r -= a[j]
    while abs((s-a[k]) - (r+a[k])) <= abs(s - r):
        r += a[k]
        s -= a[k]
        k += 1

    pqrs = [p, q, r, s]
    ans = min(ans, abs(max(pqrs) - min(pqrs)))
    # print(i, j, k, ans, pqrs)
    
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
inlis=[int(i) for i in input().split()]
csum=[0]*(N+1)
for i, v in enumerate(inlis, start=1): csum[i] = csum[i-1] + v

i, k = 1, 3
resmin = 9223372036854775807
print(csum)
for j in range(2, N-1):
    while abs((csum[i]-csum[0]) - (csum[j]-csum[i])) > abs((csum[i+1]-csum[0]) - (csum[j]-csum[i+1])): i += 1
    while abs((csum[k]-csum[j]) - (csum[N]-csum[k])) > abs((csum[k+1]-csum[j]) - (csum[N]-csum[k+1])): k += 1
    # print("p{} q{} r{} s{}".format(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k]))
    # minkamo = max(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k]) - min(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k])
    # print(i,j,k, minkamo)
    resmin = min(resmin, max(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k]) - min(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k]))

print(resmin)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

n = int(input())

a = l()

ans = Max
o = 0
oo = a[0]+a[1]
ooo = 0
oooo =sum(a[2:])
l = 0
r = 2
s = a[0]+a[1]
su = sum(a[2:])
for i in range(2,n-2):
	while(l < i and (s >= abs((oo - a[l]) - (o + a[l])))):
		s =  abs((oo - a[l]) - (o + a[l]))
		oo -= a[l]
		o += a[l]
		l += 1

	while(r < n and (su >= abs((oooo - a[r]) - (ooo + a[r])))):
		su = abs((oooo - a[r]) - (ooo + a[r]))
		if(su == 0):
			print(1,ooo,oooo)
		ooo += a[r]
		oooo -= a[r]
		r += 1
	ans = min(ans,(max(o,oo,ooo,oooo) - min(o,oo,ooo,oooo)))
	oo += a[i]
	ooo -= a[i]
	s = abs(oo-o)
	su = abs(ooo-oooo)
	if ooo == 0:
		ooo += a[i+1]
		oooo -= a[i+1]
		su = abs(ooo-oooo)
		r += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

n = int(input())

a = l()

ans = Max
o = 0
oo = a[0]+a[1]
ooo = 0
oooo = sum(a[2:])
l = 0
r = 3
s = a[0]+a[1]
su = sum(a[2:])
for i in range(2,n-2):
	while(l < i and (s >= abs((oo - a[l]) - (o + a[l])))):
		s =  abs((oo - a[l]) - (o + a[l]))
		oo -= a[l]
		o += a[l]
		l += 1

	while(r < n and (su >= abs((oooo - a[r]) - (ooo + a[r])))):
		su = abs((oooo - a[r]) - (ooo + a[r]))
		ooo += a[r]
		oooo -= a[r]
		r += 1
	ans = min(ans,(max(o,oo,ooo,oooo) - min(o,oo,ooo,oooo)))
	oo += a[i]
	ooo -= a[i]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

n = int(input())

a = l()

ans = Max
o = 0
oo = a[0]+a[1]
ooo = 0
oooo = sum(a[2:])
l = 0
r = 3
s = a[0]+a[1]
su = sum(a[2:])

for i in range(2,n-2):
	while(l < i-1 and (s >= abs((oo - a[l]) - (o + a[l])))):
		s =  abs((oo - a[l]) - (o + a[l]))
		oo -= a[l]
		o += a[l]
		l += 1

	while(r < n-1 and (su >= abs((oooo - a[r]) - (ooo + a[r])))):
		su = abs((oooo - a[r]) - (ooo + a[r]))
		ooo += a[r]
		oooo -= a[r]
		r += 1
	ans = min(ans,(max(o,oo,ooo,oooo) - min(o,oo,ooo,oooo)))
	oo += a[i]
	ooo -= a[i]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

n = int(input())

a = l()

ans = Max
o = 0
oo = a[0]+a[1]
ooo = 0
oooo = sum(a[2:])
l = 0
r = 2
s = a[0]+a[1]
su = sum(a[2:])

for i in range(2,n-2):
	while(l < i-1 and (s >= abs((oo - a[l]) - (o + a[l])))):
		s =  abs((oo - a[l]) - (o + a[l]))
		oo -= a[l]
		o += a[l]
		l += 1

	while(r < n-1 and (su >= abs((oooo - a[r]) - (ooo + a[r])))):
		su = abs((oooo - a[r]) - (ooo + a[r]))
		ooo += a[r]
		oooo -= a[r]
		r += 1
	ans = min(ans,(max(o,oo,ooo,oooo) - min(o,oo,ooo,oooo)))
	oo += a[i]
	ooo -= a[i]

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
n=int(input())
a=list(map(int,input().split()))
ac=[]
s=0
for i in range(n):
    s+=a[i]
    ac.append(s)
ans=n*10**9
l=0
r=2
last=ac[n-1]
for i in range(1,n-2):
    mid=ac[i]
    while ac[l+1]<=mid/2 and l<i-1:
        l+=1
    while ac[r+1]-mid<=(last-mid)/2 and r<n-2:
        r+=1
    ans=min(ans,max(ac[l],ac[i]-ac[l],ac[r]-ac[i],ac[n-1]-ac[r])-min(ac[l],ac[i]-ac[l],ac[r]-ac[i],ac[n-1]-ac[r]))
    #print(l,i,r,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
def inpl(): return list(map(int,input().split()))

N = int(input())
A = inpl()

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

mindiff = cum[N-1]
for j in range(2,N-1):
    sum1 = cum[j-1]
    sum2 = cum[N-1]-cum[j-1]
    i = bisect.bisect_left(cum, sum1/2)
    k = bisect.bisect_left(cum, sum1 + sum2/2)
    if i == 0:
        max1 = A[0]
        min1 = cum[j-1]-A[0]
    elif j == 2:
        max1 = A[i]
        min1 = cum[i-1]
    else:
        max1 = min(cum[i],cum[j-1]-cum[i-1])
        min1 = max(cum[i-1],cum[j-1]-cum[i])

    if k == j:
        max2 = A[j]
        min2 = cum[N-1]-cum[j]
    elif j == N-2:
        max2 = A[k]
        min2 = cum[k-1]-cum[j-1]
    else:
        max2 = min(cum[k],cum[N-1]-cum[k-1])
        min2 = max(cum[k-1],cum[N-1]-cum[k])

    max3 = max(max1,max2)
    min3 = min(min1,min2)
    mindiff = min(mindiff, max3-min3)

print(mindiff)

Submission status: Wrong Answer

Solution code:
import bisect
def inpl(): return list(map(int,input().split()))

N = int(input())
A = inpl()

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

mindiff = cum[N-1]
for j in range(2,N-1):
    sum1 = cum[j-1]
    sum2 = cum[N-1]-cum[j-1]
    i = bisect.bisect_left(cum, sum1/2)
    k = bisect.bisect_left(cum, sum1 + sum2/2)
    if i == 0:
        max1 = A[0]
        min1 = cum[j-1]-A[0]
    elif i == j-1:
        max1 = A[i]
        min1 = cum[i-1]
    else:
        max1 = min(cum[i],cum[j-1]-cum[i-1])
        min1 = max(cum[i-1],cum[j-1]-cum[i])

    if k == j:
        max2 = A[j]
        min2 = cum[N-1]-cum[j]
    elif k == N-1:
        max2 = A[k]
        min2 = cum[k-1]-cum[j-1]
    else:
        max2 = min(cum[k],cum[N-1]-cum[k-1])
        min2 = max(cum[k-1],cum[N-1]-cum[k])

    max3 = max(max1,max2)
    min3 = min(min1,min2)
    mindiff = min(mindiff, max3-min3)

print(mindiff)

Submission status: Wrong Answer

Solution code:
from numpy import *
from scipy import *
from sys import *

n = int(input())
a = array(list(map(int, input().split())))
border = sum(a)/4.
a = cumsum(a)

ans = inf

b = searchsorted(a[0:-4], border, side='left')
c = searchsorted(a[b+1:-3]-a[b], border, side='left') + b + 1
d = searchsorted(a[c+1:-2]-a[c], border, side='left') + c + 1

ans = min(ans, abs(min(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d]) -
                   max(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d])))

d = max(c+1, d-1)


ans = min(ans, abs(min(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d]) -
                   max(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d])))

c = max(b+1, c-1)
d = searchsorted(a[c+1:-2]-a[c], border, side='left') + c + 1
ans = min(ans, abs(min(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d]) -
                   max(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d])))

d = max(c+1, d-1)


ans = min(ans, abs(min(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d]) -
                   max(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d])))

b = max(0, b-1)
c = searchsorted(a[b+1:-3]-a[b], border, side='left') + b + 1
d = searchsorted(a[c+1:-2]-a[c], border, side='left') + c + 1
ans = min(ans, abs(min(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d]) -
                   max(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d])))

d = max(c+1, d-1)


ans = min(ans, abs(min(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d]) -
                   max(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d])))

c = max(b+1, c-1)
d = searchsorted(a[c+1:-2]-a[c], border, side='left') + c + 1
ans = min(ans, abs(min(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d]) -
                   max(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d])))

d = max(c+1, d-1)


ans = min(ans, abs(min(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d]) -
                   max(a[b], a[c]-a[b], a[d]-a[c], a[-1]-a[d])))


print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect

n = int(input())
a = list(map(int, input().split()))
b = [a[0]]
for i in range(1, n):
	b.append(b[-1] + a[i])

ans = float("inf")

mid_cut = bisect(b, b[-1] / 2)
#print(mid_cut)
for i in range(max(2, mid_cut-2), min(mid_cut + 2, n-1)):
	#print(i)
	former_cut = bisect(b[:i], b[i-1] / 2)
	if former_cut == 0 or b[former_cut-1] < b[i-1] - b[former_cut]:
		p, q = b[former_cut], b[i-1] - b[former_cut]
	else:
		p, q = b[former_cut-1], b[i-1] - b[former_cut-1]

	latter_cut = bisect(b[i:], (b[-1] + b[i-1]) / 2) + i
	#print(latter_cut)
	if latter_cut == i or b[latter_cut-1] - b[i-1] < b[-1] - b[latter_cut]:
		r, s = b[latter_cut] - b[i-1], b[-1] - b[latter_cut]
	else:
		r, s = b[latter_cut-1] - b[i-1], b[-1] - b[latter_cut-1]
	#print(p, q, r, s)
	ans = min(ans, max(p, q, r, s) - min(p, q, r, s))

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect

n = int(input())
a = list(map(int, input().split()))
b = [a[0]]
for i in range(1, n):
	b.append(b[-1] + a[i])

ans = float("inf")

mid_cut = bisect(b, b[-1] / 2)
#print(mid_cut)
for i in range(max(2, mid_cut-2), min(mid_cut + 2, n-1)):
	#print(i)
	former_cut = bisect(b[:i], b[i-1] / 2)
	if former_cut == 0 or b[former_cut-1] < b[i-1] - b[former_cut]:
		p, q = b[former_cut], b[i-1] - b[former_cut]
	else:
		p, q = b[former_cut-1], b[i-1] - b[former_cut-1]

	latter_cut = bisect(b[i:], (b[-1] + b[i-1]) / 2) + i
	#print(latter_cut)
	if b[latter_cut-1] - b[i-1] >= b[-1] - b[latter_cut]:
		r, s = b[latter_cut-1] - b[i-1], b[-1] - b[latter_cut-1]
	else:
		r, s = b[latter_cut] - b[i-1], b[-1] - b[latter_cut]
	#print(p, q, r, s)
	ans = min(ans, max(p, q, r, s) - min(p, q, r, s))

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect

n = int(input())
a = list(map(int, input().split()))
b = [a[0]]
for i in range(1, n):
	b.append(b[-1] + a[i])

ans = float("inf")

mid_cut = bisect(b, b[-1] / 2)
#print(mid_cut)
for i in range(max(2, mid_cut-1), min(mid_cut + 2, n-1)):
	#print(i)
	former_cut = bisect(b[:i], b[i-1] / 2)
	if former_cut == 0 or b[former_cut-1] < b[i-1] - b[former_cut]:
		p, q = b[former_cut], b[i-1] - b[former_cut]
	else:
		p, q = b[former_cut-1], b[i-1] - b[former_cut-1]

	latter_cut = bisect(b[i:], (b[-1] + b[i-1]) / 2) + i
	#print(latter_cut)
	if b[latter_cut-1] - b[i-1] >= b[-1] - b[latter_cut]:
		r, s = b[latter_cut-1] - b[i-1], b[-1] - b[latter_cut-1]
	else:
		r, s = b[latter_cut] - b[i-1], b[-1] - b[latter_cut]
	#print(p, q, r, s)
	ans = min(ans, max(p, q, r, s) - min(p, q, r, s))

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
a = np.array([int(item) for item in input().split()], dtype=int)

cum = np.cumsum(a)
total = np.sum(a)
def find(b, total):
    assert sum(b)==total
#     print("b: ", b)
    thre = total/2
    b = np.cumsum(b)
    out = np.argmin(np.abs(b-thre))
#     print("out:", out)
    return out
#     return np.min(np.where(b>thre)[0])

best = total
for i in range(1,N-2):
    left = cum[i]
    right = total - left
    ileft = find(a[:(i+1)], left)
    iright = find(a[(i+1):], right) + i + 1
    z1 = np.sum(a[:(ileft+1)])
    z2 = left - z1
    z3 = np.sum(a[(i+1):(iright+1)])
    z4 = np.sum(a[(iright+1):])  # right - z3
    M = max([z1,z2,z3,z4])
    m = min([z1,z2,z3,z4])
    best = min(best, M-m)
#     print([z1,z2,z3,z4])
best