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: Accepted

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


    # 右側処理（基本は左と同じ）
    Rmid = (cumsum[N] + cumsum[i]) / 2  # 3分探索に要領でcumsum[N]を加えてやる
    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: Accepted

Solution code:
from itertools import accumulate
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):
    #print(cumsum[:i], cumsum[i:])
    # 左の真ん中
    LC = cumsum[i] / 2

    LX = bisect_left(cumsum, LC)
    #print(LX)
    # 超えるべきか超えないべきか
    if abs(cumsum[LX-1] - LC) < abs(cumsum[LX] - LC):
        LX -= 1

    # 右の真ん中
    RC = (cumsum[N] + cumsum[i]) / 2
    RX = bisect_left(cumsum, RC)
    # 超えるべきか超えないべきか
    if abs(cumsum[RX-1] - RC) < abs(cumsum[RX] - RC):
        RX -= 1

    P, Q, R, S = cumsum[LX], cumsum[i]-cumsum[LX], cumsum[RX]-cumsum[i], cumsum[N]-cumsum[RX]
    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))

print(ans)

Submission status: Accepted

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

# 累積和を前計算
cumsum = list(accumulate(A))
cumsum.insert(0, 0)

#print(cumsum)
ans = float('inf')
# 真ん中を全探索
for i in range(2, N-1):
    #print(A[:i], A[i:])
    # 左の真ん中
    LC = cumsum[i] / 2

    LX = bisect_right(cumsum, LC)
    #print(LX)
    # 超えるべきか超えないべきか
    if abs(cumsum[LX-1] - LC) < abs(cumsum[LX] - LC):
        LX -= 1

    # 右の真ん中
    RC = (cumsum[N] + cumsum[i]) / 2
    RX = bisect_right(cumsum, RC)
    # 超えるべきか超えないべきか
    if abs(cumsum[RX-1] - RC) < abs(cumsum[RX] - RC):
        RX -= 1

    P, Q, R, S = cumsum[LX], cumsum[i]-cumsum[LX], cumsum[RX]-cumsum[i], cumsum[N]-cumsum[RX]
    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))

print(ans)

Submission status: Accepted

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

# 区間の和を高速に求めたいので累積和
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):
    # 前半部分,後半部分をそれぞれできるだけ均等になるように分割
    ax = S[i-1]/2
    ai = bisect(S,ax)
    if abs(S[ai-1]-ax) < abs(S[ai]-ax):
        ai -= 1
    bx = (S[N-1]+S[i-1])/2
    bi = bisect(S,bx)
    if abs(S[bi-1]-bx) < abs(S[bi]-bx):
        bi -= 1
    x1,x2,x3,x4 = S[ai],S[i-1]-S[ai],S[bi]-S[i-1],S[N-1]-S[bi]
    # 考慮した組み合わせで最小のものを記録
    Ans = min(Ans,max(x1,x2,x3,x4)-min(x1,x2,x3,x4))

print(Ans)

Submission status: Accepted

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 + 2):
    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: Accepted

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 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: Accepted

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:])
temp = right + 1
res_right = abs(s - r)
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
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: Accepted

Solution code:
import functools
N = int(input())
A = [int(x) for x in input().split()]
P = A[0]
Q = A[1]
R = A[2]
S = functools.reduce(lambda x, y: x + y, A[3:])
i = 1
k = 3
SR_pre = abs(S - R)
for m in range(k, N - 1):
  SR_post = abs(S - R - 2 * A[m])
  if SR_post <= SR_pre:
    SR_pre = SR_post
    R += A[m]
    S -= A[m]
    k = m + 1
  else:
    break
ans = max(P, Q, R, S) - min(P, Q, R, S)
for j in range(2, N - 2):
  Q += A[j]
  QP_pre = abs(Q - P)
  for l in range(i, j):
    QP_post = abs(Q - P - 2 * A[l])
    if QP_post <= QP_pre:
      QP_pre = QP_post
      P += A[l]
      Q -= A[l]
      i = l + 1
    else:
      break
  R -= A[j]
  SR_pre = abs(S - R)
  for m in range(k, N - 1):
    SR_post = abs(S - R - 2 * A[m])
    if SR_post <= SR_pre:
      SR_pre = SR_post
      R += A[m]
      S -= A[m]
      k = m + 1
    else:
      break
  ans = min(ans, max(P,Q, R, S) - min(P, Q, R, S))
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect
N = int(input())
A = list(map(int,input().split()))
#N = 10
#A = list(map(int,"10 71 84 33 6 47 23 25 52 64".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-1):
    med = AA[i] / 2
    j = bisect(AA, med)
    if abs(AA[j-1] - med) < abs(AA[j] - med):
        j = j-1
    rmed = (AA[-1] + AA[i]) / 2
    k = bisect(AA, rmed)
    if abs(AA[k-1] - rmed) < abs(AA[k] - rmed):
        k = k-1
    m = min(AA[j], AA[i] - AA[j], AA[k] - AA[i], AA[-1] - AA[k])
    M = max(AA[j], AA[i] - AA[j], AA[k] - AA[i], AA[-1] - AA[k])
    ans = min(ans, M - m)
print(ans)

Submission status: Accepted

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

pre = [0]
for i in range(1,N+1):
    pre.append(pre[i-1] + A[i-1])

L = 1
r = 3
ans = 10**18
        
for i in range(2,N-1):
    while L + 1 < i and abs(pre[L+1] - pre[i] + pre[L+1]) < abs(pre[L] - pre[i] + pre[L]):
        L += 1

    while r <= i or (r + 1 < N and abs(pre[r+1] - pre[i] - pre[N] + pre[r+1]) < abs(pre[r] - pre[i] - pre[N] + pre[r])):
        r += 1

    ans = min(ans,max(pre[L],pre[i]-pre[L],pre[r]-pre[i],pre[N]-pre[r]) - \
          min(pre[L],pre[i]-pre[L],pre[r]-pre[i],pre[N]-pre[r]))

print(ans)

Submission status: Accepted

Solution code:
# D
n = int(input())
A_list = list(map(int, input().split()))

# cumsum from left
a = 0
A_left = []
for i in range(n):
    a += A_list[i]
    A_left.append(a)
    
res = A_left[n-1]
i = 0
j = 1
k = 2
while j <= n - 3:
    while True:
        if abs(A_left[j] / 2 - A_left[i]) > abs(A_left[j] / 2 - A_left[i+1]):
            i += 1
        else:
            break
            
    while True:
        if abs((A_left[n-1] - A_left[j]) / 2 - (A_left[n-1] - A_left[k])) > abs((A_left[n-1] - A_left[j]) / 2 - (A_left[n-1] - A_left[k+1])):
            k += 1
        else:
            break
    # print(i, j, k)
    a, b, c, d = A_left[i], A_left[j]-A_left[i], A_left[k]-A_left[j], A_left[n-1]-A_left[k]
    r = max([a,b,c,d]) - min([a,b,c,d])
    if r < res:
        res = r
    j += 1
    
print(res)

Submission status: Accepted

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

ans = float('inf')
i1, i3 = 1, 3
s = [aaa[0], aaa[1], aaa[2], sum(aaa[3:])]
for i2 in range(2, n - 1):
    if i2 == i3:
        s[2] += aaa[i3]
        s[3] -= aaa[i3]
        i3 += 1
    while i1 < i2 - 1 and abs(s[0] - s[1]) > abs(s[0] - s[1] + 2 * aaa[i1]):
        s[0] += aaa[i1]
        s[1] -= aaa[i1]
        i1 += 1
    while i3 < n - 1 and abs(s[2] - s[3]) > abs(s[2] - s[3] + 2 * aaa[i3]):
        s[2] += aaa[i3]
        s[3] -= aaa[i3]
        i3 += 1
    ans = min(ans, max(s) - min(s))
    s[1] += aaa[i2]
    s[2] -= aaa[i2]

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect

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

def h(i,j):
  ci,cj = C[i],C[j]
  k = bisect(C, (ci+cj)//2, lo=i+1,hi=j)
  _,a,b = min((abs(ci+cj-2*c),cj-c,c-ci) for c in (C[k-1],C[k]))
  return a,b

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

print(min(solve(i) for i in range(2,N-1)))

Submission status: Accepted

Solution code:
# D
N = int(input())
A_list = list(map(int, input().split()))

# cumsum from left
a = 0
A_left = []
for i in range(N):
    a += A_list[i]
    A_left.append(a)
    
# cumsum from right
a = 0
A_right = []
for i in range(N):
    a += A_list[N-1-i]
    A_right.append(a)

def binary_search_left(s):
    m = 0
    l = 0
    r = N - 1
    
    if A_left[0] > s:
        return 0
    
    while True:
        m = (l + r) // 2
        
        if A_left[m] <= s and A_left[m+1] > s:
            break
        elif A_left[m] <= s:
            l = m
        else:
            r = m
    if s - A_left[m] <= A_left[m+1] - s:
        return m
    else:
        return m+1
    
def binary_search_right(s):
    m = 0
    l = 0
    r = N - 1
    
    if A_right[0] > s:
        return 0
    
    while True:
        m = (l + r) // 2
        
        if A_right[m] <= s and A_right[m+1] > s:
            break
        elif A_right[m] <= s:
            l = m
        else:
            r = m
    if s - A_right[m] <= A_right[m+1] - s:
        return m
    else:
        return m+1
    
# B | C split
res = A_left[N-1]
for s in range(2, N-1):
    
    m_l = binary_search_left(A_left[s-1]/2)
    a, b = A_left[m_l], A_left[s-1] - A_left[m_l]
    r = N - s 
    m_r = binary_search_right(A_right[r-1]/2)
    c, d = A_right[m_r], A_right[r-1] - A_right[m_r]
    
    r = max([a,b,c,d]) - min([a,b,c,d])
    if r < res:
        res = r
if N == 4:
    res = max(A_list) - min(A_list)
print(res)

Submission status: Accepted

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


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


def check(mid, base): # b is max-value
    if mid < base:
        l = imos[mid-1]
        r = imos[base-1] - imos[mid-1]
        return abs(r-l)
    else:
        l = imos[mid] - imos[base-1]
        r = imos[N] - imos[mid]
        return abs(r-l)
        
        

def ternarySearchInt(small, big, i):
    if big - small <= 2:  # 終了条件
        mid = (big + small) // 2
        if check(big, i) <= check(mid, i):
            return big
        else:
            return small if check(small, i) <= check(mid, i) else mid
    else:
        midl = (big + small) // 2
        midr = midl + 1
        if check(midl, i) >= check(midr, i):
            return ternarySearchInt(midl, big, i)
        else:
            return ternarySearchInt(small, midr, i)



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

ans = int(1e18)
for i in range(3, N):
    l = ternarySearchInt(1, i-1, i)
    r = ternarySearchInt(i, N, i)
    P = imos[l-1]
    Q = imos[i-1] - P
    R = imos[r] - imos[i-1]
    S = imos[N] - imos[r]
    hoge = [P,Q,R,S]
    ans = min(ans, max(hoge) - min(hoge))


print(ans)

Submission status: Accepted

Solution code:

def section_sum(a, b):
    return acc[b] - acc[a]


def minimize(s1, s2, s3):
    lsum = float("inf")
    for i in range(s1, s2):
        if abs(section_sum(0, i) - section_sum(i, s2)) < lsum:
            q = section_sum(0, i)
            r = section_sum(i, s2)
            s1 = i
            lsum = abs(q - r)
        else:
            break

    rsum = float("inf")
    for i in range(s3, len(a)):
        if abs(section_sum(s2, i) - section_sum(i, len(a))) < rsum:
            s = section_sum(s2, i)
            t = section_sum(i, len(a))
            s3 = i
            rsum = abs(s - t)
        else:
            break

    cut = [q, r, s, t]
    return abs(min(cut) - max(cut)), s1, s2, s3


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

acc = [0]
for x in a:
    acc.append(acc[-1] + x)

s1, s2, s3 = 1, 2, 3
ans = float("inf")
for s2 in range(2, len(a) - 1):
    x, s1, s2, s3 = minimize(s1, s2, s3)
    ans = min(ans, x)

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_right

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

accAs = [0] + list(accumulate(As))

# As[iFr]～As[iTo]の和を求める
def getSum(iFr, iTo):
    return accAs[iTo+1] - accAs[iFr]


# As[iFr]～As[iTo]を前後半の総和の差が最小となるように分解する
def getDivision(iFr, iTo):
    sumB = getSum(iFr, iTo)
    iMid = bisect_right(accAs, accAs[iFr]+sumB/2, iFr+1, iTo+2) - 1

    diff1, diff2 = float('inf'), float('inf')
    if iMid != iFr:
        sum1L = getSum(iFr, iMid-1)
        sum1R = getSum(iMid, iTo)
        diff1 = abs(sum1L - sum1R)
    if iMid != iTo:
        sum2L = getSum(iFr, iMid)
        sum2R = getSum(iMid+1, iTo)
        diff2 = abs(sum2L - sum2R)

    return [sum1L, sum1R] if diff1 <= diff2 else [sum2L, sum2R]


# 真ん中の区切りを全通り試す
ans = float('inf')
for iMid in range(1, N-3+1):
    sumD = []
    sumD += getDivision(0, iMid)
    sumD += getDivision(iMid+1, N-1)

    ans = min(ans, max(sumD) - min(sumD))

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect
n = int(input())
a = [int(x) for x in input().split()]
 
r = 0
s = []
for i in a:
  r += i
  s.append(r)

def bs(x,y):
  b = bisect(x, y)
  if abs(x[b-1] - y) < abs(x[b] - y):
    b = b-1
  return b
 
m = 10**20
for i in range(1, n-1):
  k = bs(s, s[i] / 2)
  l = bs(s, (s[n-1] + s[i]) / 2)
  s4 = [s[k],s[i]-s[k],s[l]-s[i],s[n-1]-s[l]]
  m = min(m, max(s4) - min(s4))

print(m)

Submission status: Accepted

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


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


def check(mid, base): # b is max-value
    if mid < base:
        l = imos[mid-1]
        r = imos[base-1] - imos[mid-1]
        return abs(r-l)
    else:
        l = imos[mid] - imos[base-1]
        r = imos[N] - imos[mid]
        return abs(r-l)
        
        

def ternarySearchInt(small, big, i):
    # 初期条件
    if small == big:
        return small
    elif big - small == 1:
        if check(small, i) <= check(big, i):
            return small
        else:
            return big

    def func(small, big):
        midl = (big + small) // 2
        midr = midl + 1
        if big - small == 2:  # 終了条件
            mid = midl
            if check(small, i) <= check(mid, i):
                if check(small, i) <= check(big, i):
                    return small
                else:
                    return big
            else:
                if check(mid, i) <= check(big, i):
                    return mid
                else:
                    return big
        else:
            if check(midl, i) > check(midr, i):
                return func(midl, big)
            else:
                return func(small, midr)
    return func(small, big)



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

ans = int(1e18)
for i in range(3, N):
    l = ternarySearchInt(1, i-1, i)
    r = ternarySearchInt(i, N, i)
    P = imos[l-1]
    Q = imos[i-1] - P
    R = imos[r] - imos[i-1]
    S = imos[N] - imos[r]
    hoge = [P,Q,R,S]
    ans = min(ans, max(hoge) - min(hoge))


print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)

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

S = []
sum_ = 0
for i in range(N):
    sum_ += A[i]
    S.append(sum_)

def search(s, prev_S, l=0, r=N):
    # return maximum i with (S[i]-prev_S <= s) and (l <= i < r)
    if r-l <= 1:
        return l
    m = l + (r-l)//2
    if S[m] - prev_S > s:
        return search(s, prev_S, l, m)
    else:
        return search(s, prev_S, m, r)


min_ = 10**20
for i in range(1, N-2):
    if i == 3:
        flag = True
    else:
        flag = False
    li = search(S[i]/2, 0, 0, i+1)
    ri = search((S[N-1]-S[i])/2, S[i], i+1, N)
    candidates = [(li, i, ri),   (li+1, i, ri),
                  (li, i, ri+1), (li+1, i, ri+1)]
    for p, q, r in candidates:
        # debug(p, q, r)
        if r >= N:
            continue
        P = S[p]
        Q = S[q] - S[p]
        R = S[r] - S[q]
        S_ = S[N-1] - S[r]
        cur_min = min(P, Q, R, S_)
        cur_max = max(P, Q, R, S_)
        min_ = min(min_, cur_max-cur_min)
    # debug(li, i, ri, min_)

print(min_)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
A = reads()

psum = [0] * (N + 1)
for i in range(N):
  psum[i+1] = psum[i] + A[i]

# print(psum, file=stderr)

ans = 10**20
for i in range(2, N-1):
  lmid = psum[i] / 2
  k = bisect(psum, lmid)
  if abs(psum[k-1] - lmid) < abs(psum[k] - lmid):
    k = k-1

  rmid = (psum[N] + psum[i]) / 2
  l = bisect(psum, rmid)
  if abs(psum[l-1] - rmid) < abs(psum[l] - rmid):
    l = l-1

  m = min(psum[k], psum[i] - psum[k], psum[l] - psum[i], psum[N] - psum[l])
  M = max(psum[k], psum[i] - psum[k], psum[l] - psum[i], psum[N] - psum[l])
  ans = min(ans, M - m)

print(ans)

Submission status: Runtime Error

Solution code:
from libc.stdio cimport scanf
cdef:
    long long N, i
    long long A[202020], a

scanf("%lld", &N)
A[0] = 0
for i in range(N):
    scanf("%lld", & A[i+1])
    A[i+1] += A[i]

cdef long long ans = 10 ** 18
cdef long long mid, l = 1, r = 3
cdef long long Ldif, Rdif, mx, mn
for mid in range(2, N - 1):
    Ldif = abs(A[mid] + A[0] - 2 * A[l])
    while l + 1 < mid and abs(A[mid] + A[0] - 2 * A[l+1]) <= Ldif:
        Ldif = abs(A[mid] + A[0] - 2 * A[l+1])
        l += 1
    r = max(r, mid + 1)
    Rdif = abs(A[N] + A[mid] - 2 * A[r])
    while r + 1 < N and abs(A[N] + A[mid] - 2 * A[r+1]) <= Rdif:
        Rdif = abs(A[N] + A[mid] - 2 * A[r+1])
        r += 1

    mx = max(A[l] - A[0], A[mid] - A[l], A[r] - A[mid], A[N] - A[r])
    mn = min(A[l] - A[0], A[mid] - A[l], A[r] - A[mid], A[N] - A[r])
    ans = min(ans, mx - mn)

print(ans)

Submission status: Runtime Error

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

import itertools
n = inn()
a = inl()
if n>300:
    3/0
cms = itertools.combinations(list(range(1,n)),3)
ans = BIG
for cm in cms:
    v = []
    v.append(sum(a[:cm[0]]))
    v.append(sum(a[cm[0]:cm[1]]))
    v.append(sum(a[cm[1]:cm[2]]))
    v.append(sum(a[cm[2]:]))
    ans = min(ans,max(v)-min(v))
print(ans)

Submission status: Runtime Error

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    import itertools
    import math
    B = list(itertools.accumulate(A))
    C = [i*A[i] for i in range(N)]
    D = list(itertools.accumulate(C))

    g = math.floor(D[-1]/B[-1])
    g1 = math.floor(D[g_s]/B[g_s])
    g2 = math.floor((D[-1]-D[g_s])/(B[-1]-B[g_s]))

    answer = pow(10, 10)
    for i in range(-2, 3):
        for j in range(-2, 3):
            for k in range(-2, 3):
                if 0 <= g1+i and g1+i < g+j and g+j < g2+k and g2+k < N:
                    m = min(B[g1+i], B[g+j]-B[g1+i], B[g2+k]-B[g+j], B[-1]-B[g2+k])
                    M = max(B[g1+i], B[g+j]-B[g1+i], B[g2+k]-B[g+j], B[-1]-B[g2+k])
                    answer = min(answer, M-m)

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
L=list(map(int,input().split()))
T=sum(L)//4
i=0
while K<=T:
  K=K+L[i]
  i=i+1
X=K-L[i-1]
a=min(abs(X-T),abs(T-K))
if a==abs(X-T):
  i=i-1
While K<=T:
  K=K+L[i]
  i=i+1
X=K-L[i-1]
b=min(abs(X-T),abs(T-K))
if b==abs(X-T):
  i=i-1
While K<=T:
  K=K+L[i]
  i=i+1
X=K-L[i-1]
c=min(abs(X-T),abs(T-K))
if c==abs(X-T):
  i=i-1
While K<=T:
  K=K+L[i]
  i=i+1
X=K-L[i-1]
d=min(abs(X-T),abs(T-K))
if d==abs(X-T):
  i=i-1
N=[a,b,c,d]
print(max(N)-min(N))

Submission status: Runtime Error

Solution code:
N,*A = map(int, open(0).read().split())
a = A[0]
b = A[1]
c = A[2]
d = sum(A[3:])
x = 0
m = c
n = d
df2 = max(m,n)-min(m,n)
for i in range(3,N-1):
  m += A[i]
  n -= A[i]
  if df2>max(m,n)-min(m,n):
    df2 = max(m,n)-min(m,n)
    c,d = m,n
    y = i
ans = max(a,b,c,d)-min(a,b,c,d)
for i in range(2,N-2):
  b += A[i]
  c -= A[i]
  df1 = max(a,b)-min(a,b)
  df2 = max(c,d)-min(c,d)
  while True:
    na = a+A[x+1]
    nb = b-A[x+1]
    if df1<max(na,nb)-min(na,nb):
      break
    df1 = max(na,nb)-min(na,nb)
    a,b = na,nb
    x += 1
  while True:
    nc = c+A[y+1]
    nd = d-A[y+1]
    if df2<max(nc,nd)-min(nc,nd):
      break
    df2 = max(nc,nd)-min(nc,nd)
    c,d = nc,nd
    y += 1
  ans = min(ans,max(a,b,c,d)-min(a,b,c,d))
print(ans)

Submission status: Runtime Error

Solution code:
# ARC100D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


n = int(input())
a = list(map(int, input().split()))
ca = [None] * n #ca[i] = a0~aiの和
s = 0
for i,num in enumerate(a):
    s += a[i]
    ca[i] = s

diff = [None] * n

s = 0
t = 1
v1 = 0 # a[:s]
v2 = a[0] # sum(a[s:t])
diff[t-1] = (v1,v2)
while t<n:
#     print(t, v1-v2)
    t += 1
    v2 += a[t-1]
    while v1<v2 and s<t:
        if diff[t-1] is None or abs(v1-v2)<abs(diff[t-1][0] - diff[t-1][1]):
            diff[t-1] = (v1,v2)
        s += 1
        v1 += a[s-1]
        v2 -= a[s-1]
    if diff[t-1] is None or abs(v1-v2)<abs(diff[t-1][0] - diff[t-1][1]):
        diff[t-1] = (v1,v2)        
    if v1>v2 and s>=1:
        v1 -= a[s-1]
        v2 += a[s-1]
        s -= 1

diff2 = [None] * n

s = n
t = n-1
v1 = 0 # sum(a[s:])
v2 = a[-1] # sum(a[t:s])
diff2[t] = (v1,v2)
while t>=1:
    # print(t, v1, v2)
    t -= 1
    v2 += a[t]
    while v1<v2 and s>t:
        if diff2[t] is None or abs(v1-v2)<abs(diff2[t][0] - diff2[t][1]):
            diff2[t] = (v1,v2)
        s -= 1
        v1 += a[s]
        v2 -= a[s]
    if diff2[t] is None or abs(v1-v2)<abs(diff2[t][0] - diff2[t][1]):
        diff2[t] = (v1,v2)        
    if v1>v2 and s<=n-2:
        v1 -= a[s]
        v2 += a[s]
        s += 1
print(min((max(*diff[i],*diff2[i+1]) - min(*diff[i],*diff2[i+1])) for i in range(n-1)))

Submission status: Runtime Error

Solution code:
n=int(input())
l=[0]+list(map(int,input().split()))
from itertools import accumulate
l=list(accumulate(l))
from bisect import bisect, bisect_left, bisect_right
ans=10**15
for i in range(2,n-1):
  	x=bisect_left(l,l[i]//2)
    p1=l[x]
    p2=l[x-1]
    if abs(l[i]-p1*2)>=abs(l[i]-p2*2):
        p=p2
    else:
        p=p1
    q=l[i]-p
    x=bisect_left(l,(l[n]-l[i])//2+l[i])
    r1=l[x]-l[i]
    r2=l[x-1]-l[i]
    if abs(l[n]-l[i]-r1*2)>=abs(l[n]-l[i]-r2*2):
        r=r2
    else:
        r=r1
    s=l[n]-l[i]-r
    ans=min(ans,max(p,q,r,s)-min(p,q,r,s))
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()

def min_max(arr):
    """リストの中を二つに分けて、総和の小さい方と大きい方を返す"""
    left = 0; right = len(arr)-1
    l_total = arr[left]
    r_total = arr[right]
    while left + 1 < right:
        if l_total <= r_total:
            left += 1
            l_total += arr[left]
        else:
            right -= 1
            r_total += arr[right]
    mi, ma = min(l_total, r_total), max(l_total, r_total)
    return mi, ma

answer = 10 ** 15
mid = N // 2
used = set()

def F(l, mid, r):
    global answer, used
    used.add(mid)
    l_min, l_max = min_max(A[:mid])
    r_min, r_max = min_max(A[mid:])
    temp = max(l_max, r_max) - min(l_min, r_min)
    if temp < answer:
        answer = temp
    if l_min <= r_min:
        m = (mid+r)//2
        if m not in used:
            F(mid, m, r)
    else:
        m = (mid+l)//2
        if m not in used:
            F(l, m, mid)
    if l_max >= r_max:
        m = (mid+l)//2
        if m not in used:
            F(l, m, mid)
    else:
        m = (mid+r)//2
        if m not in used:
            F(mid, m, r)

F(0, mid, N-1)
print(answer)
# 08

Submission status: Runtime Error

Solution code:
import bisect

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	B = [0]
	for i in range(N):
		B.append(B[-1] + A[i])
	#print(B)
	ans = float("inf")
	for i in range(2, N - 1):
		Q = B[i]
		x = bisect.bisect_left(B, Q // 2)
		P = max(B[x], B[1])
		P2 = max(B[x - 1], B[1])
		Q3 = max(B[i] - B[i - 1], B[i] - B[x + 1])
		P3 = Q - Q3
		Q2 = Q - P2
		Q -= P
		S = B[N] - B[i]
		y = bisect.bisect_left(B, (B[i] + B[N]) // 2)
		R = max(B[y] - B[i] , B[i + 1] - B[i])
		R2 = max(B[y - 1] - B[i] , B[i + 1] - B[i])
		S3 = max(B[N] - B[N - 1], B[N] - B[y + 1])
		R3 = S - S3
		S2 = S - R2
		S -= R
		#print(P, Q, R, S)
		#print(sum([P, Q, R, S]))
		ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
		ans = min(ans, max(P2, Q2, R2, S2) - min(P2, Q2, R2, S2))
		ans = min(ans, max(P3, Q3, R3, S3) - min(P3, Q3, R3, S3))
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import bisect

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	B = [0]
	for i in range(N):
		B.append(B[-1] + A[i])
	#print(B)
	ans = float("inf")
	for i in range(2, N - 2):
		Q = B[i]
		x = bisect.bisect_left(B, Q // 2)
		P = max(B[x], B[1])
		P2 = max(B[x - 1], B[1])
		Q3 = max(B[i] - B[i - 1], B[i] - B[x + 1])
		P3 = Q - Q3
		Q2 = Q - P2
		Q -= P
		S = B[N] - B[i]
		y = bisect.bisect_left(B, (B[i] + B[N]) // 2)
		R = max(B[y] - B[i] , B[i + 1] - B[i])
		R2 = max(B[y - 1] - B[i] , B[i + 1] - B[i])
		S3 = max(B[N] - B[N - 1], B[N] - B[y + 1])
		R3 = S - S3
		S2 = S - R2
		S -= R
		#print(P, Q, R, S)
		#print(sum([P, Q, R, S]))
		ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
		ans = min(ans, max(P2, Q2, R2, S2) - min(P2, Q2, R2, S2))
		ans = min(ans, max(P3, Q3, R3, S3) - min(P3, Q3, R3, S3))
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Runtime Error

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 = separate_seq(ruiseki[first_separator:N-1])
        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-1)
        diff = max(s1,s2,s3,s4) - min(s1,s2,s3,s4)
        ans = diff if ans > diff else ans
    print(ans)
        
        


def calc(num, seq):
    pass

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




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

main()