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:
def m():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(1,n):
        a[i] += a[i-1]
    ans = 999999999
    left_i = 0
    right_i = 2
    for i in range(1,n-2):
        p,q = 99999999,9999999
        r,s = 99999999,9999999
        left_diff = 99999999
        right_diff = 99999999
        while left_i < i:
            d = abs(a[left_i] - (a[i]-a[left_i]))
            if d < left_diff:
                left_diff = d
                p = a[left_i]
                q = a[i]-a[left_i]
            else:
                break
            left_i += 1
        left_i -=1

        if right_i <= i:
            right_i = i+1

        while right_i < n:
            d = abs((a[right_i] - a[i]) - (a[n-1] - a[right_i]))
            if d < right_diff:
                right_diff = d
                r = a[right_i] - a[i]
                s = a[n-1] - a[right_i]
            else:
                break
            right_i += 1
        right_i -= 1

        ans = min(ans, max(p,q,r,s) - min(p,q,r,s))
    return ans

print(m())

Submission status: Wrong Answer

Solution code:
def m():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(1,n):
        a[i] += a[i-1]
    ans = 999999999
    left_i = 0
    right_i = 2
    for i in range(1,n-2):
        left_diff = 99999999
        p,q = 99999999,9999999
        r,s = 99999999,9999999
        while left_i < i:
            d = abs(a[left_i] - (a[left_i+1]-a[left_i]))
            if d < left_diff:
                left_diff = d
                p = a[left_i]
                q = a[left_i+1]-a[left_i]
            left_i += 1

        if right_i <= i:
            right_i = i+1

        right_diff = 99999999
        while right_i < n:
            d = abs((a[right_i] - a[right_i-1]) - (a[n-1] - a[right_i]))
            if d < right_diff:
                right_diff = d
                r = a[right_i] - a[right_i-1]
                s = a[n-1] - a[right_i]
            else:
                break
            right_i += 1
        ans = min(ans, max(p,q,r,s) - min(p,q,r,s))
    return ans

print(m())

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
input()
a=[int(i) for i in input().split()]
b=list(accumulate(a))
lp=0
rp=2
ans=float("INF")
for i in range(1,len(a)-2):
    while True:
        p=b[lp]
        q=b[i]-b[lp]
        r=b[rp]-b[i]
        s=b[len(a)-1]-b[rp]
        if abs(p-q)>abs(b[lp+1]-(b[i]-b[lp+1])):
            lp+=1
        elif abs(r-s)>abs(b[rp+1]-b[i]-(b[len(a)-1]-b[rp+1])):
            rp+=1
        else:
            break
ans=min(ans,abs(max(p,q,r,s)-min(p,q,r,s)))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
input()
a=[int(i) for i in input().split()]
b=list(accumulate(a))
lp=0
rp=2
for i in range(1,len(a)-2):
    while True:
        p=b[lp]
        q=b[i]-b[lp]
        r=b[rp]-b[i]
        s=b[len(a)-1]-b[rp]
        if abs(p-q)>abs(b[lp+1]-(b[i]-b[lp+1])):
            lp+=1
        elif abs(r-s)>abs(b[rp+1]-b[i]-(b[len(a)-1]-b[rp+1])):
            rp+=1
        else:
            break
print(abs(max(p,q,r,s)-min(p,q,r,s)))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
input()
a=[int(i) for i in input().split()]
b=list(accumulate(a))
lp=0
rp=2
for i in range(1,len(a)-2):
    while True:
        p=b[lp]
        q=b[i]-b[lp]
        r=b[rp]-b[i]
        s=b[len(a)-1]-b[rp]
        if abs(p-q)>abs(b[lp+1]-(b[i]-b[lp+1])):
            lp+=1
        elif abs(r-s)>abs(b[rp+1]-b[i]-(b[len(a)-1]-b[rp+1])):
            rp+=1
        else:
            break
print(max(p,q,r,s)-min(p,q,r,s))

Submission status: Wrong Answer

Solution code:
def dif(A):
    A_num = list(map(sum,A))
    return max(A_num) - min(A_num)


from copy import deepcopy

n = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)

B =[[],[],[],[]]

for i in range(n):
    if i <= 3:
        B[i].append(A[i])
    else:
        B_num = list(map(sum,B))
        B[B_num.index(min(B_num))].append(A[i])

flag = True

while flag:
    flag = False
    for i in range(4):
        if flag:
            break
        for j in B[i]:
            if flag:
                break
            for k in range(4):
                if flag:
                    break
                C = deepcopy(B)
                if k!=i:
                    C[i].remove(j)
                    C[k].append(j)
                    if dif(B) > dif(C):
                        B = C
                        flag = True

print(dif(B))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

N = int(input())
A = list(map(int, input().split(" ")))
Acc = []
a = 0
for i in range(N):
    a += A[i]
    Acc.append(a)
# print(A)
# print(Acc)

def centerPoint(L):
    diff = 10000000000
    p = 0
    temp = L[-1] / 2
    r = 0
    l = len(L) - 1
    while r < l:
        mid = int((r+l)/2)
        # print(r, l, mid)
        if L[mid] < temp:
            r = mid + 1
        else:
            l = mid - 1
    p = r
    # print(r)
    # for i in range(len(L)):
    #     if abs(L[i] - (L[-1] - L[i])) < diff:
    #         diff = abs(L[i] - (L[-1] - L[i]))
    #         p = i
    # print(p)
    return p

ret = 10000000000
for i in range(2, len(A)-1):
    p1 = centerPoint(Acc[:i])
    temp = list(map(lambda x: x - Acc[i-1], Acc[i:]))
    p2 = centerPoint(temp)
    # print(Acc[:i],temp)
    s1 = Acc[p1]
    s2 = Acc[i-1] - Acc[p1]
    s3 = Acc[p2+i] - Acc[i-1]
    s4 = Acc[-1] - Acc[p2+i]
    # print(s1,s2,s3,s4)
    # print(max(s1,s2,s3,s4) - min(s1,s2,s3,s4))
    if max(s1,s2,s3,s4) - min(s1,s2,s3,s4) < ret:
        ret = max(s1,s2,s3,s4) - min(s1,s2,s3,s4)
print(ret)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

N = int(input())
A = list(map(int, input().split(" ")))
Acc = []
a = 0
for i in range(N):
    a += A[i]
    Acc.append(a)
print(A)
print(Acc)

def centerPoint(L):
    diff = 10000000000
    p = 0
    for i in range(len(L)):
        if abs(L[i] - (L[-1] - L[i])) < diff:
            diff = abs(L[i] - (L[-1] - L[i]))
            p = i
    return p
ret = 10000000000
for i in range(2, len(A)-1):
    p1 = centerPoint(Acc[:i])
    temp = list(map(lambda x: x - Acc[i-1], Acc[i:]))
    p2 = centerPoint(temp)
    # print(Acc[:i],temp)
    s1 = Acc[p1]
    s2 = Acc[i-1] - Acc[p1]
    s3 = Acc[p2+i] - Acc[i-1]
    s4 = Acc[-1] - Acc[p2+i]
    # print(s1,s2,s3,s4)
    # print(max(s1,s2,s3,s4) - min(s1,s2,s3,s4))
    if max(s1,s2,s3,s4) - min(s1,s2,s3,s4) < ret:
        ret = max(s1,s2,s3,s4) - min(s1,s2,s3,s4)
print(ret)

Submission status: Wrong Answer

Solution code:
N = int(input())
*A, = map(int, input().split())
S = [0]*(N+1)
for i in range(N):
    S[i+1] = S[i] + A[i]
INF = 10**30
ans = INF
y = z = 0
def check(x, y, z):
    if 0 < y < x < z < N:
        B = (S[y], S[x]-S[y], S[z]-S[x], S[N]-S[z])
        return max(B)-min(B)
    return INF
for x in range(N):
    s = S[x+1]
    while y < N and S[y+1]*2 <= s:
        y += 1
    t = S[N]-s
    while z < N and (S[z+1]-s)*2 <= t:
        z += 1
    for p in [0, 1]:
        for q in [0, 1]:
            ans = min(ans, check(x, y+p, z+q))
print(ans)

Submission status: Wrong Answer

Solution code:
def split_med(cum_list, start, end):
    e = pow(10, 10)
    med_ind = 0
    for i in range(start, end):
        a = cum_list[i] - cum_list[start-1]
        b = cum_list[end] - cum_list[i]
        if abs(a - b) < e:
            e = abs(a - b)
            med_ind = i
    return med_ind

def calc_score(cum_list, left_index, med_index, right_index):
    p = cum_list[left_index]
    q = cum_list[med_index] - p
    r = cum_list[right_index] - p - q
    s = cum_list[len(cum_list)-1] - p - q - r
    return max([p, q, r, s]) - min([p, q, r, s])

n = int(input())
a_list = list(map(int, input().split()))
cum_list = [sum(a_list[:i]) for i in range(1, len(a_list)+1)]
left_index = 0
right_index = 0
scores = []
for i in range(1, len(a_list)-2):
    left_index = split_med(cum_list, left_index, i)
    right_index = split_med(cum_list, i+1, len(cum_list)-1)

    scores.append(calc_score(cum_list, left_index, i, right_index))

print(min(scores))

Submission status: Wrong Answer

Solution code:
def calc_score(b, c, d, e):
    p = sum(b)
    q = sum(c)
    r = sum(d)
    s = sum(e)

    max_sum = max([p, q, r, s])
    min_sum = min([p, q, r, s])
    return abs(max_sum - min_sum)

def split_med(num_list, offset):
    cum_list = [sum(num_list[:i]) for i in range(len(num_list)+1)]
    med_ind = 0
    e = pow(10, 10)
    med = cum_list[len(cum_list)-1] // 2
    for i in range(len(cum_list)):
        if abs(med - cum_list[i]) < e:
            med_ind = i
            e = abs(med - cum_list[i])
    if med_ind + offset <= 0:
        return num_list[:1], num_list[1:]
    elif med_ind + offset >= len(num_list):
        return num_list[:len(num_list)-1], num_list[len(num_list)-1:]
    return num_list[:med_ind+offset], num_list[med_ind+offset:]

def split_and_calc_scores(num_list):
    offsets = [-1, 0, 1]
    scores = []
    for offset_1 in offsets:
        a_1, a_2 = split_med(num_list, offset_1)
        for offset_2 in offsets:
            b, c = split_med(a_1, offset_2)
            for offset_3 in offsets:
                d, e = split_med(a_2, offset_3)
                scores.append(calc_score(b, c, d, e))
    return scores

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

scores = split_and_calc_scores(a_list)

print(min(scores))

Submission status: Wrong Answer

Solution code:
import numpy as np

_N = int(input())
_As = np.asarray(list(map(int, input().split())), dtype=np.int)
_AAs = np.add.accumulate(_As)

def _calculate_PQRS(_AAs, _index):
    (_i1, _i2, _i3) = _index
    return (_AAs[_i1 - 1],
            _AAs[_i2 - 1] - _AAs[_i1 - 1],
            _AAs[_i3 - 1] - _AAs[_i2 - 1],
            _AAs[-1] - _AAs[_i3 - 1])

def _evaluate(_AAs, _index):
    _PQRS = _calculate_PQRS(_AAs, _index)
    return np.abs(np.max(_PQRS) - np.min(_PQRS))

_index = [1,2,3]
_score = _evaluate(_AAs, _index)
while True:
    _PQRS = _calculate_PQRS(_AAs, _index)
    _maxi = np.argmax(_PQRS)
    _maxi_index = list(_index)
    if _maxi != 0:
        _maxi_index[_maxi - 1] += 1
    else:
        _maxi_index[_maxi] -= 1

    _mini = np.argmin(_PQRS)
    _mini_index = list(_index)
    if _mini != 0:
        _mini_index[_mini - 1] -= 1
    else:
        _mini_index[_mini] += 1

    _maxi_score = _evaluate(_AAs, _maxi_index)
    _mini_score = _evaluate(_AAs, _mini_index)
    if (_maxi_score > _score
        and _mini_score > _score):
        break
    if _maxi_score < _mini_score:
        _index = list(_maxi_index)
        _score = _maxi_score
    else:
        _index = list(_mini_index)
        _score = _mini_score

print(_score)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

def S(a, b):
    return cl[b] - (0 if a == 0 else cl[a-1])

def partial(start, end, last):
    #print("partial: {}-{} last:{}".format(start,end, last))
    mp = S(start, last-1)
    mq = S(last, end)
    odiff = abs(mp-mq)

    for c in range(last-1, end):
        p = S(start,c)
        q = S(c+1,end)
        diff = abs(p-q)
        if odiff < diff:
            break
        odiff = diff
        mp = p
        mq = q
    return c,mp,mq

if __name__ == '__main__':
    # read input
    n = int(input())
    l = list(map(int, input().split()))
    # create cumlative list first
    cl = list(accumulate(l))
    clen = len(l)

    #  0  F(i)      i i+1 G(i)      len-1
    #  |------|------|-------|-------|
    #         c0    c1       c2
    #  <-----L------> <------R------->
    # pick up a c1 (i:i+1) and evaluate
    result = 9 * 10e9
    c1 = 0
    c3 = 2
    for i in range(1,clen-2):
        #print("LEFT:RIGHT {}/={}=/{}".format(l[0:i+1], i, l[i+1: clen]))
        # LEFT
        c1, mb, mc = partial(0, i, c1)
        # RIGHT
        c3, md, me = partial(i+1, clen-1, c3)

        # evaluate
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        #print("\t\t{}/{}/{}: [{} {} {} {}]".format(c1, i, c3, mb, mc, md, me))
        #print("\t\tdiff={}".format(diff))
        if diff < result:
            result = diff

    print(result)

Submission status: Wrong Answer

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


# 累積
acc = [0]
for i in range(N):
    acc.append(acc[i] + A[i])


def dev_sec(start, end, previous_best):
    # check left
    dif_min = 10 ** 10
    best_p = -1
    best_q = -1
    best_sep= previous_best

    for p_end in range(previous_best, end):
        sum_of_p = acc[p_end + 1] - acc[start]
        sum_of_q = acc[end + 1] - acc[p_end + 1]
        # sumの最小
        dif = abs(sum_of_p - sum_of_q)
        if dif_min > dif:
            dif_min = dif
            best_p = sum_of_p
            best_q = sum_of_q
            best_sep = p_end
        else:
            break
    return best_p, best_q , best_sep



dif_min = 10 ** 10
previous_best_left = 0
previous_best_right = 2
for left_end in range(1, N-2):

    p, q, previous_best_left = dev_sec(0, left_end, previous_best_left)
    r, s, previous_best_right = dev_sec(left_end + 1, N - 1, previous_best_right)

    dif = max(p, q, r, s) - min(p, q, r, s)
    if dif_min > dif:
        dif_min = dif
print(dif_min)

Submission status: Wrong Answer

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


# 累積
acc = [0]
for i in range(N):
    acc.append(acc[i] + A[i])


def dev_sec(start, end, previous_best):
    # check left
    dif_min = 10 ** 10
    best_p = -1
    best_q = -1
    best_sep= previous_best

    for p_end in range(previous_best, end):
        sum_of_p = acc[p_end + 1] - acc[start]
        sum_of_q = acc[end + 1] - acc[p_end + 1]
        # sumの最小
        dif = abs(sum_of_p - sum_of_q)
        if dif_min > dif:
            dif_min = dif
            best_p = sum_of_p
            best_q = sum_of_q
            best_sep = p_end
        else:
            break
    return best_p, best_q , best_sep



dif_min = 10 ** 9
previous_best_left = 0
previous_best_right = 2
for left_end in range(1, N-2):

    p, q, previous_best_left = dev_sec(0, left_end, previous_best_left)
    r, s, previous_best_right = dev_sec(left_end + 1, N - 1, previous_best_right)

    dif = max(p, q, r, s) - min(p, q, r, s)
    if dif_min > dif:
        dif_min = dif
print(dif_min)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

def S(a, b):
    return cl[b] - (0 if a == 0 else cl[a-1])

def partial(start, end, last):
    #print("partial: {}-{} last:{}".format(start,end, last))
    last -= 1
    mp = S(start, last)
    mq = S(last+1, end)
    odiff = abs(mp-mq)

    for c in range(last, end):
        p = S(start,c)
        q = S(c+1,end)
        diff = abs(p-q)
        if odiff < diff:
            break
        odiff = diff
        mp = p
        mq = q
    return c,mp,mq

if __name__ == '__main__':
    # read input
    n = int(input())
    l = list(map(int, input().split()))
    # create cumlative list first
    cl = list(accumulate(l))
    clen = len(l)

    #  0  F(i)      i i+1 G(i)      len-1
    #  |------|------|-------|-------|
    #         c0    c1       c2
    #  <-----L------> <------R------->
    # pick up a c1 (i:i+1) and evaluate
    result = None
    c1 = 1
    c3 = 3
    for i in range(1,clen-2):
        # LEFT
        #print("LEFT: {} RIGHT: {}".format(l[0:i+1], l[i+1: clen]))
        c1, mb, mc = partial(0, i, c1)
        # RIGHT
        c3, md, me = partial(i+1, clen-1, c3)

        #print("{}/{}/{}: [{} {} {} {}]".format(c1, i+1, c3, mb, mc, md, me))

        # evaluate
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        if result is None:
            result = diff
        else:
            if result > diff:
                result = diff

    print(result)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

def S(a, b):
    return cl[b] - (0 if a == 0 else cl[a-1])

def partial(start, end, last):
    print("partial: {}-{} last:{}".format(start,end, last))
    last -= 1
    p = S(start, last)
    q = S(last+1, end)
    odiff = abs(p-q)

    for c in range(last, end):
        print("partial c:{}".format(c))
        p = S(start,c)
        q = S(c+1,end)
        diff = abs(p-q)
        if odiff is None:
            odiff = diff
        if odiff < diff:
            return c, mp, mq
        odiff = diff
        mp = p
        mq = q
    return c,mp,mq

if __name__ == '__main__':
    # read input
    n = int(input())
    l = list(map(int, input().split()))
    # create cumlative list first
    cl = list(accumulate(l))
    clen = len(l)

    #  0  F(i)      i i+1 G(i)      len-1
    #  |------|------|-------|-------|
    #         c0    c1       c2
    #  <-----L------> <------R------->
    # pick up a c1 (i:i+1) and evaluate
    result = None
    c1 = 1
    c3 = 3
    for i in range(1,clen-2):
        # LEFT
        #print("LEFT: {} RIGHT: {}".format(l[0:i+1], l[i+1: clen]))
        c1, mb, mc = partial(0, i, c1)
        # RIGHT
        c3, md, me = partial(i+1, clen-1, c3)

        #print("{}/{}/{}: [{} {} {} {}]".format(c1, i+1, c3, mb, mc, md, me))

        # evaluate
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        if result is None:
            result = diff
        else:
            if result > diff:
                result = diff

    print(result)

Submission status: Wrong Answer

Solution code:
# 整数列A 
# 3箇所で切って、４つに
# それぞれの総和の最大値と最小値の差の絶対値の最小値

# 中央を固定することを考える(結局、その固定を全検索するが)
# 中央固定後、左側について、両方が同じくらいの値になるのが最適と考えて良いらしい

from itertools import accumulate

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

tmpP=tmpQ=tmpR=tmpS=0
P=Q=R=S=0
ans=10e9
l = 0
r = 2

# midとmid+1の間が中間の切断
for mid in range(1,N-3):

	# l,rは、単調増加であるため、全ての中間点を求めるループの間、クリアの必要がないらしい

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while l < mid and abs(SumA[l+1]-(SumA[mid] - SumA[l+1])) <= abs(SumA[l]-(SumA[mid] - SumA[l])):
		l += 1

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while r <= mid or (r < N and abs((SumA[r+1]-SumA[mid]) - (SumA[N-1]-SumA[r+1])) <= abs((SumA[r] - SumA[mid]) - (SumA[N-1] - SumA[r]))):
		r += 1

	#print("{},{}".format(mid,l))

	P=SumA[l]
	Q=SumA[mid]-SumA[l]
	R=SumA[r]-SumA[mid]
	S=SumA[N-1]-SumA[r]

	#print(P,Q,R,S)
	diff=max(P,Q,R,S)-min(P,Q,R,S)
	diff=abs(diff)
	ans = min(ans,diff)

print(ans)

Submission status: Wrong Answer

Solution code:
# 整数列A 
# 3箇所で切って、４つに
# それぞれの総和の最大値と最小値の差の絶対値の最小値

# 中央を固定することを考える(結局、その固定を全検索するが)
# 中央固定後、左側について、両方が同じくらいの値になるのが最適と考えて良いらしい

from itertools import accumulate

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

tmpP=tmpQ=tmpR=tmpS=0
P=Q=R=S=0
ans=10e9
l = 0
r = 2

# midとmid+1の間が中間の切断
for mid in range(1,N-3):

	# l,rは、単調増加であるため、全ての中間点を求めるループの間、クリアの必要がないらしい

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while l < mid and abs(SumA[l+1]-(SumA[mid] - SumA[l+1])) < abs(SumA[l]-(SumA[mid] - SumA[l])):
		l += 1

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while r <= mid or (r < N and abs((SumA[r+1]-SumA[mid]) - (SumA[N-1]-SumA[r+1])) < abs((SumA[r] - SumA[mid]) - (SumA[N-1] - SumA[r]))):
		r += 1

	#print("{},{}".format(mid,l))

	P=SumA[l]
	Q=SumA[mid]-SumA[l]
	R=SumA[r]-SumA[mid]
	S=SumA[N-1]-SumA[r]

	#print(P,Q,R,S)
	diff=max(P,Q,R,S)-min(P,Q,R,S)
	diff=abs(diff)
	ans = min(ans,diff)

print(ans)

Submission status: Wrong Answer

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

def irekae(S,T,i):
    if abs(S-T)>abs((S-A[i-1])-(T+A[i-1])):
        
        S=S-A[i-1]
        T=T+A[i-1]
        i=i-1
        
    elif abs(T-S)>abs((T-A[i])-(S+A[i])):
        #print(T,S,T-S,i)
        S=S+A[i]
        T=T-A[i]
        i=i+1
        #print(T,S,T-S,i)

    return (S,T,i)

cut=N//2
cutb=0
A_2_1=A[:cut]
S_2_0=sum(A_2_1)
A_2_2=A[cut:]
S_2_1=sum(A_2_2)


while cutb!=cut:
    #print(cut)
    cutb=cut
    S_2_0,S_2_1,cut=irekae(S_2_0,S_2_1,cut)



cut_1=cut//2
cut_2=cut
cut_3=cut+(N-cut)//2

#print(cut_1,cut_2,cut_3,N)
A_0=A[:cut_1]
S_0=sum(A_0)

A_1=A[cut_1:cut_2]
S_1=sum(A_1)

A_2=A[cut_2:cut_3]
S_2=sum(A_2)

A_3=A[cut_3:]
S_3=sum(A_3)



cutb_1=0
cutb_2=0
cutb_3=0

while (cut_1,cut_2,cut_3)!=(cutb_1,cutb_2,cutb_3):
    #print(cut_1,cut_2,cut_3,[S_0,S_1,S_2,S_3])
    cutb_1=cut_1
    cutb_2=cut_2
    cutb_3=cut_3
    

    S_0,S_1,cut_1=irekae(S_0,S_1,cut_1)
    S_1,S_2,cut_2=irekae(S_1,S_2,cut_2)
    S_2,S_3,cut_3=irekae(S_2,S_3,cut_3)


#print(cut_1,cut_2,cut_3,[S_0,S_1,S_2,S_3],max([S_0,S_1,S_2,S_3]),min([S_0,S_1,S_2,S_3]))
print(max([S_0,S_1,S_2,S_3])-min([S_0,S_1,S_2,S_3]))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = [int(_) for _ in input().split()]

# my initial trial below ##############################
# from itertools import combinations
# INF = 10 ** 15
# combs = combinations(range(1, n), 3)
# grief = INF
# for comb in combs:
#     p = sum(a[:comb[0]])
#     q = sum(a[comb[0]:comb[1]])
#     r = sum(a[comb[1]:comb[2]])
#     s = sum(a[comb[2]:])

#     tmp = max(p, q, r, s) - min(p, q, r, s)
#     if tmp < grief:
#         grief = tmp

# print(grief)  # running time limit error

# solution below ######################################
INF = 10**15
cumul_sum = [0]
for i, ai in enumerate(a):
    cumul_sum.append(ai + cumul_sum[i])


def cal_sum(left, right):
    return cumul_sum[right] - cumul_sum[left]


def two_pointers(l, r, split, diff):
    left_sum = cal_sum(l, split)
    right_sum = cal_sum(split, r)

    for i in range(split, r):
        tmp_left_sum = cal_sum(l, i)
        tmp_right_sum = cal_sum(i, r)
        tmp_diff = abs(left_sum - right_sum)

        if diff >= tmp_diff:
            left_sum = tmp_left_sum
            right_sum = tmp_right_sum
            diff = tmp_diff
        else:
            return i - 1, diff, left_sum, right_sum
    else:
        return r - 1, diff, tmp_left_sum, tmp_right_sum


l_split = 1
r_split = 3
griefs = []
for i in range(2, n - 1):
    # left
    l_split, l_diff, p, q = two_pointers(0, i, l_split, INF)
    # right
    r_split, r_diff, r, s = two_pointers(i, n, r_split, INF)
    griefs.append(max(p, q, r, s) - min(p, q, r, s))

print(min(griefs))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = [int(_) for _ in input().split()]

# my initial trial below ##############################
# from itertools import combinations
# INF = 10 ** 15
# combs = combinations(range(1, n), 3)
# grief = INF
# for comb in combs:
#     p = sum(a[:comb[0]])
#     q = sum(a[comb[0]:comb[1]])
#     r = sum(a[comb[1]:comb[2]])
#     s = sum(a[comb[2]:])

#     tmp = max(p, q, r, s) - min(p, q, r, s)
#     if tmp < grief:
#         grief = tmp

# print(grief)  # running time limit error

# solution below ######################################
INF = 10**15
cumul_sum = [0]
for i, ai in enumerate(a):
    cumul_sum.append(ai + cumul_sum[i])


def cal_sum(left, right):
    return cumul_sum[right] - cumul_sum[left]


def two_pointers(l, r, split, diff):
    left_sum = cal_sum(l, split)
    right_sum = cal_sum(split, r)

    for i in range(split, r):
        tmp_left_sum = cal_sum(l, i)
        tmp_right_sum = cal_sum(i, r)
        tmp_diff = abs(left_sum - right_sum)

        if diff >= tmp_diff:
            left_sum = tmp_left_sum
            right_sum = tmp_right_sum
            diff = tmp_diff
        else:
            return i - 1, diff, left_sum, right_sum
    else:
        return r - 1, diff, left_sum, right_sum


l_split = 1
r_split = 3
griefs = []
for i in range(2, n - 1):
    # left
    l_split, l_diff, p, q = two_pointers(0, i, l_split, INF)
    # right
    r_split, r_diff, r, s = two_pointers(i, n, r_split, INF)
    griefs.append(max(p, q, r, s) - min(p, q, r, s))

print(min(griefs))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = [int(_) for _ in input().split()]

# my initial trial below ##############################
# from itertools import combinations
# INF = 10 ** 10
# combs = combinations(range(1, n), 3)
# grief = INF
# for comb in combs:
#     p = sum(a[:comb[0]])
#     q = sum(a[comb[0]:comb[1]])
#     r = sum(a[comb[1]:comb[2]])
#     s = sum(a[comb[2]:])

#     tmp = max(p, q, r, s) - min(p, q, r, s)
#     if tmp < grief:
#         grief = tmp

# print(grief)  # running time limit error

# solution below ######################################
INF = 10**10
cumul_sum = [0]
for i, ai in enumerate(a):
    cumul_sum.append(ai + cumul_sum[i])


def cal_sum(left, right):
    return cumul_sum[right] - cumul_sum[left]


def two_pointers(l, r, split, diff):
    for i in range(split, r):
        tmp_diff = abs(cal_sum(l, i) - cal_sum(i, r))
        if diff >= tmp_diff:
            diff = tmp_diff
        else:
            return i - 1, diff
    else:
        return r - 1, diff


l_split = 1
r_split = 3
griefs = []
for i in range(2, n - 1):
    # left
    l_split, l_diff = two_pointers(0, i, l_split, INF)
    # right
    r_split, r_diff = two_pointers(i, n, r_split, INF)

    p, q, r, s = cal_sum(0, l_split), cal_sum(l_split,
                                              i), cal_sum(i, r_split), cal_sum(
                                                  r_split, n)
    griefs.append(max(p, q, r, s) - min(p, q, r, s))

print(min(griefs))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N=int(input())
s=list(accumulate(map(int,input().split())))
ans=10**9
p=0
q=2
for i in range(2,N-1):
    print(p,abs(s[i-1]-2*s[p+1]),abs(s[i-1]-2*s[p]),s[i-1],s[p+1])
    while p<i-1 and abs(s[i-1]-2*s[p+1])<abs(s[i-1]-2*s[p]):
        p+=1
    print(N-i)
    if q<i:
        q+=1
    while q<N and abs(s[i-1]-2*s[q+1]+s[-1])<abs(s[i-1]-2*s[q]+s[-1]):   
        q+=1
    t=[s[q]-s[i-1],s[-1]-s[q],s[p],s[i-1]-s[p]]
    w=max(t)-min(t)
    ans=min(ans,w) 
print(ans)

Submission status: Wrong Answer

Solution code:
import statistics
import math

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


ureshimi = []
k = 0
l = 2

B = 0
C = 0
D = 0
E = 0

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

for i in range(2, N - 1):
    for j in range(k, i):
        if j == i - 1:
            k = j
            C = sumBC - B
            break
        elif B + A[j] >= sumBC / 2:
            if sumBC / 2 - B  > A[j] / 2:
                B += A[j]
                k = j + 1
                C = sumBC - B
                break
            else:
                k = j
                C = sumBC - B
                break
        B += A[j]
    for j in range(l, N):
        if j == N - 1:
            l = j
            E = sumDE - D
            break
        elif D + A[j] >= sumDE / 2:
            if sumDE / 2 - D > A[j] / 2:
                D += A[j]
                l = j + 1
                E = sumDE - D
                break
            else:
                l = j
                E = sumDE - D
                break
        D += A[j]
    print(B, C, D, E)
    ureshimi.append(max([B, C, D, E]) - min([B, C, D, E]))
    sumBC += A[i]
    sumDE -= A[i]
    D -= A[i]
        

print(min(ureshimi))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate


def run(n, a):
    # sum_a = [sum(a[0:i+1]) for i in range(n)]
    sum_a = list(accumulate(a))
    li = 0
    ri = 2
    t = sum_a[-1]
    diff = sum_a[-1]
    # 真ん中の切れ込みを順に変更
    # 左の切れ込みの位置はiに対して単調増加
    # 左の切れ込みで真ん中の項を移動するかどうかは、
    # 真ん中の項を除いて、小さい方に入れる
    # ただし単調増加なので、左の切れ込みの左側が
    # 小さいときに真ん中を左の切れ込みの左側に入れる
    # 右も同様に考える
    for i in range(1, n-2):
        while sum_a[i] > sum_a[li+1] + sum_a[li]:
            li += 1
        while t + sum_a[i] > sum_a[ri+1] + sum_a[ri]:
            ri += 1
        p = sum_a[li]
        q = sum_a[i] - p
        r = sum_a[ri] - q - p
        s = t - sum_a[ri]
        diff = min(diff, max(p, q, r, s) - min(p, q, r, s))
    return diff

Submission status: Wrong Answer

Solution code:
# 整数列A 
# 3箇所で切って、４つに
# それぞれの総和の最大値と最小値の差の絶対値の最小値

# 中央を固定することを考える(結局、その固定を全検索するが)
# 中央固定後、左側について、両方が同じくらいの値になるのが最適と考えて良いらしい

from itertools import accumulate

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

tmpP=tmpQ=tmpR=tmpS=0
P=Q=R=S=0
left = -1
ans=10e9

for mid in range(1,N-1):
	diffL=10e9
	diffR=10e9
	for l in range(mid):
		tmpP=SumA[l]
		tmpQ=SumA[mid] - tmpP
		if abs(tmpQ-tmpP) <= diffL:
			diffL = abs(tmpQ-tmpP)
		else:
			break
		P=tmpP
		Q=tmpQ

	for r in range(mid+1,N-1):

		tmpR=SumA[r] - SumA[mid]
		tmpS=SumA[N-1] - SumA[mid] - tmpR
		if abs(tmpS-tmpR) <= diffR:
			diffR = abs(tmpS-tmpR)
		else:
			break
		R=tmpR
		S=tmpS

	# print(P,Q,R,S)
	diff=max(P,Q,R,S)-min(P,Q,R,S)
	diff=abs(diff)
	ans = min(ans,diff)

print(ans)

Submission status: Wrong Answer

Solution code:
# 整数列A 
# 3箇所で切って、４つに
# それぞれの総和の最大値と最小値の差の絶対値の最小値

# 中央を固定することを考える(結局、その固定を全検索するが)
# 中央固定後、左側について、両方が同じくらいの値になるのが最適と考えて良いらしい

from itertools import accumulate

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

tmpP=tmpQ=tmpR=tmpS=0
P=Q=R=S=0
left = -1
ans=10e9

for mid in range(2,N-2):
	diffL=10e9
	diffR=10e9
	for l in range(mid):
		tmpP=SumA[l]
		tmpQ=SumA[mid] - SumA[l]
		if abs(tmpQ-tmpP) < diffL:
			diffL = abs(tmpQ-tmpP)
			left = l
			P=tmpP
			Q=tmpQ
		else:
			break

	for r in range(mid+1,N-1):

		tmpR=SumA[r] - SumA[mid]
		tmpS=SumA[N-1] - SumA[mid] - tmpR
		if abs(tmpS-tmpR) < diffR:
			diffR = abs(tmpS-tmpR)
			right = r
			R=tmpR
			S=tmpS
		else:
			break

	# print(P,Q,R,S)
	diff=max(P,Q,R,S)-min(P,Q,R,S)
	diff=abs(diff)
	ans = min(ans,diff)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
a = int(raw_input())
# スペース区切りの整数の入力
l = map(int, raw_input().split())

ret=sum(l)
for i in range(1, len(l)-3):
	for j in range(i, len(l)-2):
		b=sum(l[:i])
		c=sum(l[i:j])
		if c-b > ret:
			break
		elif b-c > ret:
			continue
			
		for k in range(j, len(l)-1):

			d=sum(l[j:k])
			e=sum(l[k:])
			mmax=max(b,c,d,e)
			mmin=min(b,c,d,e)
			temp = mmax-mmin
			ret=temp if (temp<ret) else ret
			
print ret