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:
n = int(input())
a = list(map(int,input().split()))

l = 1
m = 1
r = 3

sumll = a[0]
suml = a[0]
sumrr = sum(a[3:])
sumr = a[1]+a[2]+sumrr

res = sumr + a[0]

for m in range(1,n-2):
    suml += a[m]
    sumr -= a[m]
    while sumll+a[l]<=suml/2 and l<m:
        sumll += a[l]
        l += 1
    while sumrr-a[r]>=sumr/2 and r<n-1:
        sumrr -= a[r]
        r += 1
    p1 = sumll
    q1 = suml - sumll
    r1 = sumr - sumrr
    s1 = sumrr
    # print(p1,q1,r1,s1)
    p2 = p1 + a[l]
    q2 = q1 - a[l]
    r2 = r1 + a[r]
    s2 = s1 - a[r]
    abs1 = max(p1,q1,r1,s1)-min(p1,q1,r1,s1)
    abs2 = max(p2,q2,r2,s2)-min(p2,q2,r2,s2)
    abs3 = max(p1,q1,r2,s2)-min(p1,q1,r2,s2)
    abs4 = max(p2,q2,r1,s1)-min(p1,q1,r2,s2)
    rest = min(abs1,abs2,abs3,abs4)
    if res > rest:
        res = rest

print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = []
b.append(a[0])
for i in range(1,len(a)):
  b.append(b[i-1] + a[i])
ans = 10**9

# 累積和から閉区間の合計を求める
def get_sum(l,r):
  res = b[r]
  if l != 0:
    res -= b[l-1]
  return res

# 番号の手前を区切りとす
for mid in range(2,n-1):
  # 左の区切りmid_lftの決定
  st_lft = 0
  fn_lft = mid - 1
  while st_lft + 1 != fn_lft:
    mid_lft = (st_lft + fn_lft) // 2
    # 左右の最大値
    left_sum = get_sum(0, mid_lft - 1)
    right_sum = get_sum(mid_lft, mid - 1)
    if left_sum < right_sum:
      st_lft = mid_lft
    elif left_sum > right_sum:
      fn_lft = mid_lft
    else:
      fn_lft = mid_lft
      break
  # 右の区切りmid_ritの決定
  st_rit = mid
  fn_rit = n - 1
  while st_rit + 1 != fn_rit:
    mid_rit = (st_rit + fn_rit) // 2
    left_sum = get_sum(mid, mid_rit - 1)
    right_sum = get_sum(mid_rit, n - 1)
    if left_sum < right_sum:
      st_rit = mid_rit
    elif left_sum > right_sum:
      fn_rit = mid_rit
    else:
      fn_rit = mid_rit
      break
  # 最大値、最小値の算出
  _max = max(get_sum(0,fn_lft-1), get_sum(fn_lft,mid-1), get_sum(mid, fn_rit-1), get_sum(fn_rit, n-1))
  _min = min(get_sum(0,fn_lft-1), get_sum(fn_lft,mid-1), get_sum(mid, fn_rit-1), get_sum(fn_rit, n-1))
  ans = min(ans, _max - _min)

print(ans)

Submission status: Wrong Answer

Solution code:
import random
from itertools import accumulate
N = int(input())
As = [int(i) for i in input().split(' ')]
As = list(accumulate(As))


def bsearch(l, ls, rs):
    n = int(len(l)/2)
    if n == 0:
        return [max(l[0]-ls , rs-l[0]), min(l[0]-ls , rs-l[0])]
    lsum = l[n] - ls
    rsum = rs - l[n]
    ll = l[:n]
    rl = l[n:]
    if lsum > rsum:
        return bsearch(ll, ls, rs)
    else:
        return bsearch(rl, ls, rs)

for i in range(N-3):
    cs = bsearch(As[:i+2], 0, As[i+1]) + bsearch(As[i+2:], As[i+1], As[-1])
    if i == 0:
        result = max(cs) - min(cs)
    else:
        if max(cs) - min(cs) < result:
            result = max(cs) - min(cs)
print(result)

Submission status: Wrong Answer

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

import numpy as np
ans = float("inf")
for i in range(2, N-2):
    left_cs = list(np.cumsum(A[:i]))
    right_cs = list(np.cumsum(A[i:]))
    for l, v in enumerate(left_cs):
        if v + left_cs[l+1] >= left_cs[-1]:
            P = left_cs[l]
            Q = left_cs[-1] - P
            break
    for r, v in enumerate(right_cs):
        if v + right_cs[r+1] >= right_cs[-1]:
            R = right_cs[r]
            S = right_cs[-1] - R
            break
    ans = min(ans, (max(P, Q, R, S) - min(P, Q, R, S)))


print(ans)

Submission status: Wrong Answer

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

l, r = a[:2]
m = 1
b = [(l,r)]
for i in range(2, n-2):
    r += a[i]
    for j in range(m, i):
        nl, nr = l+a[j], r-a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m = j
    else:
        m += 1
    b.append((l,r))

l, r = a[-2:]
m = n-2
c = [(l,r)]
for i in range(2, n-2)[::-1]:
    l += a[i]
    for j in range(i+1, m+1)[::-1]:
        nl, nr = l-a[j], r+a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m = j
    else:
        m -= 1
    c.append((l,r))

r = 10**9
for i in range(n-4):
    x = max(b[i]+c[-i-1])
    y = min(b[i]+c[-i-1])
    r = min(r, x-y)

print(r)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
from itertools import accumulate
from bisect import bisect_left


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


def QuatroCut(mid):
    leftidx = bisect_left(CumA, CumA[mid] / 2) 
    p, q = CumA[leftidx], CumA[mid] - CumA[leftidx]
    if np.abs(p - q) > np.abs(p - q - 2 * A[leftidx]):
        p, q = p - A[leftidx], q + A[leftidx]

    rightidx = bisect_left(CumA, (CumA[-1] + CumA[mid]) / 2)
    r, s = CumA[rightidx] - CumA[mid], CumA[-1] - CumA[rightidx]
    if np.abs(r - s) > np.abs(r - s - 2 * A[rightidx]):
        r, s = r - A[rightidx], s + A[rightidx]
    return max([p, q, r, s]) - min([p, q, r, s])


# Golden Search
golden = (3-5**0.5)/2
min_i, max_i = 1, N-3
left_i = min_i + int((max_i - min_i) * golden)
right_i = max_i - (left_i - min_i)
while True:
    if (left_i - min_i) < 1.1:
        print(min([QuatroCut(i) for i in range(min_i, max_i + 1)]))
        exit()
    elif (max_i - right_i) < 1.1:
        print(min([QuatroCut(i) for i in range(min_i, max_i + 1)]))
        exit()
    else:
        if QuatroCut(left_i) < QuatroCut(right_i):
            right_i, max_i = left_i, right_i
            left_i = min_i + int((right_i - min_i) * golden / (1-golden))
        else:
            min_i, left_i = left_i, right_i
            right_i = max_i - int((max_i - left_i) * golden / (1-golden))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
from itertools import accumulate
from bisect import bisect_left


N = int(input())
A = np.array(list(map(int, input().split())))
CumA = list(accumulate(A))
res = 10 ** 16


def QuatroCut(mid):
    leftidx = bisect_left(CumA, CumA[mid] / 2) 
    p, q = CumA[leftidx], CumA[mid] - CumA[leftidx]
    if np.abs(p - q) > np.abs(p - q - 2 * A[leftidx]):
        p, q = p - A[leftidx], q + A[leftidx]

    rightidx = bisect_left(CumA, (CumA[-1] + CumA[mid]) / 2)
    r, s = CumA[rightidx] - CumA[mid], CumA[-1] - CumA[rightidx]
    if np.abs(r - s) > np.abs(r - s - 2 * A[rightidx]):
        r, s = r - A[rightidx], s + A[rightidx]

    return max([p, q, r, s]) - min([p, q, r, s])


# Golden Search
r = (3-5**0.5)/2
min_i, max_i = 1, N-3
left_i = min_i + int((max_i - min_i) * r)
right_i = max_i - (left_i - min_i)
while True:
    if (left_i - min_i) < 1.1:
        print(min([QuatroCut(i) for i in range(min_i, max_i + 1)]))
        exit()
    elif (max_i - right_i) < 1.1:
        print(min([QuatroCut(i) for i in range(min_i, max_i + 1)]))
        exit()
    else:
        if QuatroCut(left_i) < QuatroCut(right_i):
            right_i, max_i = left_i, right_i
            left_i = min_i + int((right_i - min_i) * r / (1-r))
        else:
            min_i, left_i = left_i, right_i
            right_i = max_i - int((max_i - left_i) * r / (1-r))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
from itertools import accumulate
from bisect import bisect_left


N = int(input())
A = np.array(list(map(int, input().split())))
CumA = list(accumulate(A))
res = 10 ** 16


def QuatroCut(mid):
    leftidx = bisect_left(CumA, CumA[mid] / 2) 
    p, q = CumA[leftidx], CumA[mid] - CumA[leftidx]
    if np.abs(p - q) > np.abs(p - q - 2 * A[leftidx]):
        p, q = p - A[leftidx], q + A[leftidx]

    rightidx = bisect_left(CumA, (CumA[-1] + CumA[mid]) / 2)
    r, s = CumA[rightidx] - CumA[mid], CumA[-1] - CumA[rightidx]
    if np.abs(r - s) > np.abs(r - s - 2 * A[rightidx]):
        r, s = r - A[rightidx], s + A[rightidx]

    return max([p, q, r, s]) - min([p, q, r, s])


# Golden Search
golden = (3-5**0.5)/2
min_i, max_i = 1, N-3
left_i = min_i + int((max_i - min_i) * golden)
right_i = max_i - (left_i - min_i)
while True:
    if (left_i - min_i) < 1.1:
        print(min([QuatroCut(i) for i in range(min_i, max_i + 1)]))
        exit()
    elif (max_i - right_i) < 1.1:
        print(min([QuatroCut(i) for i in range(min_i, max_i + 1)]))
        exit()
    else:
        if QuatroCut(left_i) < QuatroCut(right_i):
            left_i, right_i, max_i = min_i + (right_i - left_i), left_i, right_i
        else:
            min_i, left_i, right_i = left_i, right_i, max_i - (right_i - left_i)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
from itertools import accumulate
from bisect import bisect_left


N = int(input())
A = np.array(list(map(int, input().split())))
CumA = list(accumulate(A))
res = 10 ** 16


def QuatroCut(mid):
    leftidx = bisect_left(CumA, CumA[mid] / 2) 
    p, q = CumA[leftidx], CumA[mid] - CumA[leftidx]
    if np.abs(p - q) > np.abs(p - q - 2 * A[leftidx]):
        p, q = p - A[leftidx], q + A[leftidx]

    rightidx = bisect_left(CumA, (CumA[-1] + CumA[mid]) / 2)
    r, s = CumA[rightidx] - CumA[mid], CumA[-1] - CumA[rightidx]
    if np.abs(r - s) > np.abs(r - s - 2 * A[rightidx]):
        r, s = r - A[rightidx], s + A[rightidx]

    return max([p, q, r, s]) - min([p, q, r, s])


# Binary Search
if N == 4:
    print(QuatroCut(1))
    exit()

min_i, mid_i, max_i = 1, int((N-2)/2), N-3
while True:
    if min_i == (mid_i-1):
        if (mid_i+1) == max_i:
            print(min([QuatroCut(i) for i in range(min_i, max_i + 1)]))
            exit()
        else:
            print(min([QuatroCut(i) for i in range(min_i, max_i + 2)]))
            exit()
    elif (mid_i+1) == max_i:
            print(min([QuatroCut(i) for i in range(min_i, max_i + 1)]))
            exit()
    else:
        leftidx = int((min_i + mid_i)/2)
        rightidx = int((mid_i + max_i)/2)
        if QuatroCut(leftidx) < QuatroCut(rightidx):
            mid_i, max_i = leftidx, mid_i
        else:
            min_i, mid_i = mid_i, rightidx

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
from itertools import accumulate
from bisect import bisect_left


N = int(input())
A = np.array(list(map(int, input().split())))
CumA = list(accumulate(A))
res = 10 ** 16

def Calcmin(p, q, r, s):
    return max([p, q, r, s] - min([p, q, r, s]))

def QuatroCut(mid):
    leftidx = bisect_left(CumA, CumA[mid] / 2) 
    p, q = CumA[leftidx], CumA[mid] - CumA[leftidx]
    if np.abs(p - q) > np.abs(p - q - 2 * A[leftidx]):
        p, q = p - A[leftidx], q + A[leftidx]

    rightidx = bisect_left(CumA, (CumA[-1] + CumA[mid]) / 2)
    r, s = CumA[rightidx] - CumA[mid], CumA[-1] - CumA[rightidx]
    if np.abs(r - s) > np.abs(r - s - 2 * A[rightidx]):
        r, s = r - A[rightidx], s + A[rightidx]
    return int(Calcmin(p, q, r, s))



# Binary Search
min_i, mid_i, max_i = 1, int((N-2)/2), N-3
while True:
    if min_i == (mid_i-1):
        if (mid_i+1) == max_i:
            print(min([QuatroCut(i) for i in range(min_i, max_i + 1)]))
            exit()
        else:
            print(min([QuatroCut(i) for i in range(min_i, max_i + 2)]))
            exit()
    elif (mid_i+1) == max_i:
            print(min([QuatroCut(i) for i in range(min_i, max_i + 1)]))
            exit()
    else:
        leftidx = int((min_i + mid_i)/2)
        rightidx = int((mid_i + max_i)/2)
        if QuatroCut(leftidx) < QuatroCut(rightidx):
            mid_i, max_i = leftidx, mid_i
        else:
            min_i, mid_i = mid_i, rightidx

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
from itertools import accumulate
from bisect import bisect_left

# TLE !!!

N = int(input())
A = np.array(list(map(int, input().split())))
CumA = list(accumulate(A))
res = 10 ** 16

def Calcmin(p, q, r, s):
    return max([p, q, r, s] - min([p, q, r, s]))

def QuatroCut(mid):
    leftidx = bisect_left(CumA, CumA[mid] / 2) 
    p, q = CumA[leftidx], CumA[mid] - CumA[leftidx]
    if np.abs(p - q) > np.abs(p - q - 2 * A[leftidx]):
        p, q = p - A[leftidx], q + A[leftidx]

    rightidx = bisect_left(CumA, (CumA[-1] + CumA[mid]) / 2)
    r, s = CumA[rightidx] - CumA[mid], CumA[-1] - CumA[rightidx]
    if np.abs(r - s) > np.abs(r - s - 2 * A[rightidx]):
        r, s = r - A[rightidx], s + A[rightidx]
    return int(Calcmin(p, q, r, s))



# Binary Search
min_i, mid_i, max_i = 1, int((N-2)/2), N-3
while True:
    print(mid_i)
    if min_i == (mid_i-1):
        if (mid_i+1) == max_i:
            print(min([QuatroCut(i) for i in range(min_i, max_i + 1)]))
            exit()
        else:
            print(min([QuatroCut(i) for i in range(min_i, max_i + 2)]))
            exit()
    elif (mid_i+1) == max_i:
            print(min([QuatroCut(i) for i in range(min_i, max_i + 1)]))
            exit()
    else:
        leftidx = int((min_i + mid_i)/2)
        rightidx = int((mid_i + max_i)/2)
        if QuatroCut(leftidx) < QuatroCut(rightidx):
            mid_i, max_i = leftidx, mid_i
        else:
            min_i, mid_i = mid_i, rightidx

Submission status: Wrong Answer

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

def half(A):
    ave = sum(A) / 2
    buf = 0
    for i in range(N):
        buf += A[i]
        if buf >= ave:
            break
    dif = int((buf - ave) * 2)
    if A[i] > dif:
        i += 1
    return A[:i], A[i:]

ans = pow(10, 9) * 2 * pow(10, 5)
for i in range(2, N - 2):
    B, C = half(A[:i])
    D, E = half(A[i:])
    b = sum(B)
    c = sum(C)
    d = sum(D)
    e = sum(E)
    x = max(b, c, d, e) - min(b, c, d, e)
    if x < ans:
        ans = x
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

# bisectはどっちでも（どちらに等号をつけても）うまくいくっぽい
from bisect import bisect_right, bisect_left

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

# 累積和を前計算
cumsum = list(accumulate(A))
cumsum.insert(0, 0)  # out of index 対策


ans = float('inf')
# 真ん中を全探索
for i in range(2, N-1):  # 左側は最低2つ残さなきゃいけないから2から(0もあるので）、右も同じ理由でN-1
    # 左の真ん中
    Lmid = cumsum[i] / 2

    # 左真ん中がどこに入るべきか
    Lx = bisect_left(cumsum, Lmid)

    # Lxまで取るのか、Lx-1まで取るのか（どこまで取ると望ましい値Lmidに近づくのか）
    # 左側がLmidに近づくと右側もLmidに近づく→差の絶対値が0に近づく
    if abs(cumsum[Lx-1] - Lmid) < abs(cumsum[Lx] - Lmid):
        Lmid -= 1


    # 右側処理（基本は左と同じ）
    Rmid = (cumsum[N] + cumsum[i]) / 2  # 3分探索に要領でcumsum[i]を加えてやる
    Rx = bisect_left(cumsum, Rmid)
    # 超えるべきか超えないべきか
    if abs(cumsum[Rx-1] - Rmid) < abs(cumsum[Rx] - Rmid):
        Rx -= 1


    # 左からLx個の和
    P = cumsum[Lx]

    # Lx番目+1から真ん中区切りiまでの和
    Q = cumsum[i]-cumsum[Lx]

    # 真ん中区切りのi+1番目からRx番目までの和
    R = cumsum[Rx]-cumsum[i]

    # Rx+1番目から最後まで
    S = cumsum[N]-cumsum[Rx]
    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
from bisect import bisect_left

# 区間の和を高速に求めたいので累積和
S = [0]*N
S[0] = A[0]
for i in range(1,N):
    S[i] = S[i-1]+A[i]

Ans = 10**15
# 真ん中の分割位置を全探索
for i in range(2,N-1):
    # 前半と後半に分離
    A,B = S[:i],S[i:]
    sumA,sumB = S[i-1],S[N-1]-S[i-1]
    canA,canB = [],[]
    # 前半部分,後半部分をそれぞれできるだけ均等になるように分割
    ai = bisect_left(A,sumA/2)
    bi = bisect_left(B,sumB/2+A[-1])
    # 2分探索で分割位置を求め、その次の要素を含める・含めないの2通り考慮する
    x1,x2,x3,x4 = 0,0,0,0
    a0,a1 = A[ai],A[ai-1]
    a2 = A[i-1]
    b0,b1 = B[bi],B[bi-1]
    b2 = B[-1]
    if abs(a0-sumA/2) < abs(a1-sumA/2):
        x1,x2 = a0,a2
    else:
        x1,x2 = a1,a2    
    if abs(b0-(sumB/2+A[-1])) > abs(b1-(sumB/2+A[-1])):
        x3,x4 = b0,b2
    else:
        x3,x4 = b1,b2
    # 考慮した組み合わせで最小のものを記録
    Ans = min(Ans,max(x1,x2-x1,x3-x2,x4-x3)-min(x1,x2-x1,x3-x2,x4-x3))

print(Ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
from itertools import accumulate
INF = 10 ** 20

def get_score(acc, head, end):
  sec_head = acc[head - 1]
  sec_end = acc[end]
  sec_sum = sec_end - sec_head
  cut = bl(acc, sec_head + sec_sum // 2) - 1
  score = INF
  reta, retb = None, None
  for i in range(cut - 1, cut + 1):
    if head <= i < end: 
      a = acc[i] - sec_head
      b = sec_end - acc[i]
      if score > abs(a - b):
        score = abs(a - b)
        reta, retb = a, b
  return (reta, retb)

n = int(input())
acc = [0]
acc += accumulate(map(int, input().split()))

ans = INF
for i in range(2, n - 1):
  p, q = get_score(acc, 1, i)
  r, s = get_score(acc, i + 1, n)
  if not None in (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_left as bl
from itertools import accumulate
INF = 10 ** 20

def get_score(acc, head, end):
  sec_head = acc[head - 1]
  sec_end = acc[end]
  sec_sum = sec_end - sec_head
  cut = bl(acc, sec_head + sec_sum // 2) - 1
  score = INF
  reta, retb = None, None
  for i in range(cut - 2, cut + 3):
    if head <= i <= end: 
      a = acc[i] - sec_head
      b = sec_end - acc[i]
      if not (a == 0 or b == 0):
        if score > abs(a - b):
          score = abs(a - b)
          reta, retb = a, b
  return (reta, retb)

n = int(input())
acc = [0]
acc += accumulate(map(int, input().split()))

ans = INF
for i in range(2, n - 2):
  p, q = get_score(acc, 1, i)
  r, s = get_score(acc, i + 1, n)
  if not None in (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
from time import time

st_time = time()
N = int(input())
src = list(map(int,input().split()))

cums = [0]
for a in src:
    cums.append(cums[-1] + a)

ans = cums[-1] * 999
c = bisect(cums, cums[-1]//2)
d = 1
while time() - st_time < 1.9:
    if abs(d) >= N: break
    if 2 <= c <= N-2:
        b1 = bisect(cums[:c], cums[c]//2)
        b2 = bisect(cums[c:], (cums[c]+cums[-1])//2) + c
        pq_cands = []
        for i in (b1,b1-1):
            if not 0 < i < c: continue
            p = cums[i]
            q = cums[c] - cums[i]
            pq_cands.append((p,q))
        rs_cands = []
        for i in (b2,b2-1):
            if not c < i < N: continue
            r = cums[i] - cums[c]
            s = cums[-1] - cums[i]
            rs_cands.append((r,s))
        for p,q in pq_cands:
            for r,s in rs_cands:
                mn = min(p,q,r,s)
                mx = max(p,q,r,s)
                ans = min(ans, mx-mn)
    c += d
    d = (abs(d)+1) * [1,-1][d%2]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n + 1)]
for i in range(n):
	b[i + 1] = b[i] + a[i]
# b[i] = sum(a[:i])

suma = sum(a)
border = suma / 4

def func1(start_index, bit, seq_num):
	# bit: 0 -> border を超えない, 1 -> border を超える
	end_index = start_index + 1
	
	if bit == 0:
		while b[end_index] - b[start_index] < border and end_index < n - 3 + seq_num:
			end_index += 1
		if end_index == start_index + 1:
			return end_index, b[end_index] - b[start_index]
		else:
			return end_index - 1, b[end_index - 1] - b[start_index]

	elif bit == 1:
		while b[end_index] - b[start_index] < border and end_index < n - 3 + seq_num:
			end_index += 1
		return end_index, b[end_index] - b[start_index]

def func2(bits):
	# bits: 0~7
	starts = [0]
	sums = []

	for i in range(3):
		f = func1(starts[-1], bits % 2, i)
		bits = bits // 2
		starts.append(f[0])
		sums.append(f[1])

	sums.append(b[n] - b[f[0]])

	return max(sums) - min(sums)

candidates = []

for i in range(8):
	candidates.append(func2(i))

print(min(candidates))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 20

def get_score(section):
  section_min = section[0]
  section_max = section[-1]
  section_sum = section_max - section_min
  section_len = len(section)
  cut = bl(section, section_min + section_sum // 2)
  diff = INF
  ans = (None, None)
  for i in range(cut - 2, cut + 3):
    if 0 <= i <= section_len - 1:
      div = section[i]
      a, b = div - section_min, section_max - div
      if a == 0 or b == 0:
        continue
      score = abs(b - a)
      if score < diff:
        ans = (a, b)
        diff = score
  return ans

def main():
  n = int(input())
  alst = list(map(int, input().split()))
  cums = [0]
  acc = 0
  for a in alst:
    acc += a
    cums.append(acc)
  
  ans = INF
  for i in range(2, n - 1):
    left = cums[:i]
    right = cums[i - 1:]
    p, q = get_score(left)
    r, s = get_score(right)
    if None in (p, q, r, s):
      continue
    tmp = max(p, q, r, s) - min(p, q, r, s)
    if tmp < ans:
      ans = tmp
  
  print(ans)

main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 20

def get_score(section):
  section_min = section[0]
  section_max = section[-1]
  section_sum = section_max - section_min
  section_len = len(section)
  cut = bl(section, section_min + section_sum // 2)
  diff = INF
  ans = (None, None)
  for i in range(cut - 1, cut + 2):
    if 0 <= i <= section_len - 1:
      a, b = section[i] - section_min, section_max - section[i]
      if a == 0 or b == 0:
        continue
      if abs(b - a) < diff:
        ans = (a, b)
        diff = abs(b - a)
  return ans

def main():
  n = int(input())
  alst = list(map(int, input().split()))
  cums = [0]
  acc = 0
  for a in alst:
    acc += a
    cums.append(acc)
  
  ans = INF
  for i in range(2, n - 1):
    left = cums[:i]
    right = cums[i - 1:]
    p, q = get_score(left)
    r, s = get_score(right)
    if None in (p, q, r, s):
      continue
    ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
  
  print(ans)

main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 20

def get_score(section):
  section_min = section[0]
  section_max = section[-1]
  section_sum = section_max - section_min
  section_len = len(section)
  cut = bl(section, section_min + section_sum // 2)
  diff = INF
  ans = (INF, INF)
  for i in range(cut - 1, cut + 2):
    if 0 <= i <= section_len - 1:
      a, b = section[i] - section_min, section_max - section[i]
      if a == 0 or b == 0:
        continue
      if abs(b - a) < diff:
        ans = (a, b)
        diff = abs(b - a)
  return ans

def main():
  n = int(input())
  alst = list(map(int, input().split()))
  cums = [0]
  acc = 0
  for a in alst:
    acc += a
    cums.append(acc)
  
  ans = INF
  for i in range(2, n - 1):
    left = cums[:i]
    right = cums[i - 1:]
    p, q = get_score(left)
    r, s = get_score(right)
    ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
  
  print(ans)

main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 20

def get_score(section):
  section_min = section[0]
  section_max = section[-1]
  section_sum = section_max - section_min
  section_len = len(section)
  cut = bl(section, section_min + section_sum // 2)
  diff = INF
  ans = (None, None)
  for i in range(cut - 1, cut + 2):
    if 0 <= i <= section_len - 1:
      a, b = section[i] - section_min, section_max - section[i]
      if abs(b - a) < diff:
        ans = (a, b)
        diff = abs(b - a)
  return ans

def main():
  n = int(input())
  alst = list(map(int, input().split()))
  cums = [0]
  acc = 0
  for a in alst:
    acc += a
    cums.append(acc)
  
  ans = INF
  for i in range(2, n - 1):
    left = cums[:i]
    right = cums[i - 1:]
    p, q = get_score(left)
    r, s = get_score(right)
    ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
  
  print(ans)

main()

Submission status: Wrong Answer

Solution code:
from functools import reduce

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

left = 0
right = 2
p = a[0]
q = a[1]
r = a[2]
s = reduce(lambda x, y: x + y, a[3:])
result = max(p,q,r,s) - min(p,q,r,s)

for i in range(2, n - 2):
    q += a[i]
    r -= a[i]
    if i == right:
        right += 1
        r += a[i + 1]
        s -= a[i + 1]
    res_left = abs(p - q)
    res_right = abs(r - s)
    temp = left + 1
    x = p
    y = q
    while temp < i:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_left:
            left = temp
            p = x
            q = y
            res_left = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp = right + 1
    x = r
    y = s
    while temp < n - 1:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_right:
            right = temp
            r = x
            s = y
            res_right = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp_res = max(p, q, r, s) - min(p, q, r, s)
    if temp_res < result:
        result = temp_res

print(result)

Submission status: Wrong Answer

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

left = 0
right = 2
p = a[0]
q = a[1]
r = a[2]
s = sum(a[3:])
result = max(p,q,r,s) - min(p,q,r,s)

for i in range(2, n - 2):
    q += a[i]
    r -= a[i]
    if i == right:
        right += 1
        r += a[i + 1]
        s -= a[i + 1]
    res_left = abs(p - q)
    res_right = abs(r - s)
    temp = left + 1
    x = p
    y = q
    while temp < i:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_left:
            left = temp
            p = x
            q = y
            res_left = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp = right + 1
    x = r
    y = s
    while temp < n - 1:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_right:
            right = temp
            r = x
            s = y
            res_right = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp_res = max(p, q, r, s) - min(p, q, r, s)
    if temp_res < result:
        result = temp_res

print(result)

Submission status: Wrong Answer

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

left = 0
right = 2
p = a[0]
q = a[1]
r = a[2]
s = sum(a[3:])
result = max(p,q,r,s) - min(p,q,r,s)

for i in range(2, n - 2):
    q += a[i]
    r -= a[i]
    if i == right:
        right += 1
        r += a[i + 1]
        s -= a[i + 1]
    res_left = abs(p - q)
    res_right = abs(r - s)
    temp = left + 1
    x = p
    y = q
    while temp < i:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_left:
            left = temp
            p = x
            q = y
            res_left = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp = right + 1
    x = r
    y = s
    while temp < n - 1:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_right:
            right = temp
            r = x
            s = y
            res_right = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp_res = max(p, q, r, s) - min(p, q, r, s)
    print(temp_res,p,q,r,s,left,i,right)
    if temp_res < result:
        result = temp_res

print(result)

Submission status: Wrong Answer

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

left = 0
right = 2
p = a[0]
q = a[1]
res_left = abs(p - q)
r = a[2]
s = int(sum(a[3:]))
res_right = abs(r - s)
result = max(p,q,r,s) - min(p,q,r,s)

for i in range(2, n - 2):
    q += a[i]
    r -= a[i]
    if i == right:
        right += 1
        r += a[i + 1]
        s -= a[i + 1]
    res_left = abs(p - q)
    res_right = abs(r - s)
    temp = left + 1
    x = p
    y = q
    while temp < i:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_left:
            left = temp
            p = x
            q = y
            res_left = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp = right + 1
    x = r
    y = s
    while temp < n - 1:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_right:
            right = temp
            r = x
            s = y
            res_right = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp_res = max(p, q, r, s) - min(p, q, r, s)
    if temp_res < result:
        result = temp_res

print(result)

Submission status: Wrong Answer

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

left = 0
right = 2
p = a[0]
q = a[1]
res_left = abs(p - q)
r = a[2]
s = sum(a[3:])
res_right = abs(r - s)
result = max(p,q,r,s) - min(p,q,r,s)

for i in range(2, n - 2):
    q += a[i]
    r -= a[i]
    if i == right:
        right += 1
        r += a[i + 1]
        s -= a[i + 1]
    res_left = abs(p - q)
    res_right = abs(r - s)
    temp = left + 1
    x = p
    y = q
    while temp < i:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_left:
            left = temp
            p = x
            q = y
            res_left = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp = right + 1
    x = r
    y = s
    while temp < n - 1:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_right:
            right = temp
            r = x
            s = y
            res_right = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp_res = max(p, q, r, s) - min(p, q, r, s)
    if temp_res < result:
        result = temp_res

print(result)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
#N = 5
#A = list(map(int,"3 2 4 1 2".split()))
AA = [0  for x in range(N)]
for i,a in enumerate(A):
    AA[i] = AA[i-1] + a
ans = 99999999999999999
ed = 2
st = 0
_bc = AA[-1]
_de = AA[-1]
for i in range(1,N-2):
    for j in range(st,i):
        B = AA[j]
        C = AA[i] - AA[j]
        if abs(B -C) <= _bc:
            _bc = abs(B -C)
        else:
            st = j -1
            _bc = abs(2 * AA[j-1] - AA[i+1])
            B = AA[j-1]
            C = AA[i] - AA[j-1]
            break
    for k in range(ed,N-1):
        D = AA[k] - AA[i]
        E = AA[-1] - AA[k]
        if _de >= abs(D-E):
            _de = abs(D-E)
        else:
            ed = k 
            _de = abs(2 * AA[k-1] - AA[i+1] -AA[-1])
            D = AA[k-1] - AA[i]
            E = AA[-1] - AA[k-1]
            break
    sample = max([abs(B-C),abs(B-D),abs(B-E),abs(C-D),abs(C-E),abs(D-E)])
    if ans > sample:
        ans = sample
        #print(ans)
print(ans)