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: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = pow(10,10)
for i in range(1, N - 2):
	for j in range(i + 1, N - 1):
		for k in range(j + 1, N):
			B = list(A[:i])
			C = list(A[i:j])
			D = list(A[j:k])
			E = list(A[k:])
			P = sum(B)
			Q = sum(C)
			R = sum(D)
			S = sum(E)
			ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
while(True):
    a = 0

Submission status: Time Limit Exceeded

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

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

ans = float('infinity')
for i in range(1, len(A) - 2):
    B = sum(A[0:i])
    for j in range(i, len(A) - 1):
        C = sum(A[i:j])
        for k in range(j, len(A)):
            D = sum(A[j:k])
            E = sum(A[k:len(A) + 1])
            ans = min(ans, max(B, C, D, E) - min(B, C, D, E))
            if max(B, C, D, E) == D:
                break
        if max(B, C, D, E) == C:
            break
    if max(B, C, D, E) == B:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = pow(10,10)
for i in range(1, N):
	for j in range(i + 1, N):
		for k in range(j + 1, N):
			B = list(A[:i])
			C = list(A[i:j])
			D = list(A[j:k])
			E = list(A[k:])
			P = sum(B)
			Q = sum(C)
			R = sum(D)
			S = sum(E)
			temp = max(P, Q, R, S) - min(P, Q, R, S)
			if temp < ans:
				ans = temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations

n = int(input())
a = [int(_) for _ in input().split()]

combs = combinations(range(1, n), 3)

grief = 10**10
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)

Submission status: Time Limit Exceeded

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

ans=10000000000
for i in range(0,N-3):
  alis=nums[0:i+1]
  for j in range(i+1,N-2):
    blis=nums[i+1:j+1]
    for k in range(j+1,N-1):
      clis=nums[j+1:k+1]
      dlis=nums[k+1:]
      lislis=[alis,blis,clis,dlis]
      anslis=[sum(x) for x in lislis]
      preans=max(anslis)-min(anslis)
      if preans<ans:
        ans=preans
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import *
n = int(input())
a = [int(i) for i in input().split()]
ans = 999999999999999
for t in list(combinations(range(1, n), 3)):
    b = a[0:t[0]]
    c = a[t[0]:t[1]]
    d = a[t[1]:t[2]]
    e = a[t[2]:]
    p = sum(b)
    q = sum(c)
    r = sum(d)
    s = sum(e)
    ans = min(ans, abs(max(p,q,r,s) - min(p,q,r,s)))
print(ans)

Submission status: Time Limit Exceeded

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

ans = float('infinity')
for i in range(1, len(A) - 2):
    for j in range(i, len(A) - 1):
        for k in range(j, len(A)):
            B = sum(A[0:i])
            C = sum(A[i:j])
            D = sum(A[j:k])
            E = sum(A[k:len(A) + 1])
            ans = min(ans, max(B, C, D, E) - min(B, C, D, E))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from inspect import currentframe

def chkprint(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

from functools import reduce
from math import floor, ceil

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

left = 1
center = 2
right = 3

res = 10**16



p = sum(A[0:left])
q = sum(A[left:center])
r = sum(A[center:right])
s = sum(A[right:])

# print(A)

while center <= N - 2:
  while True:
    p = sum(A[0:left])
    q = sum(A[left:center])

    if abs(p-q) < abs(p-q+2*A[left]):
      break

    if left == center-1:
      break

    left += 1

  while True:
    r = sum(A[center:right])
    s = sum(A[right:])

    if abs(r-s) < abs(r-s+2*A[right]):
      break

    if right == N-1:
      break

    right += 1

  res = min(max(p,q,r,s)-min(p,q,r,s),res)

  # print(A[0:left], A[left:center], A[center:right], A[right:], res)
  center += 1

print(res)

Submission status: Time Limit Exceeded

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

ans=100000000000

for i in range(0,len(a_list)-3):
  for j in range(i+1,len(a_list)-2):
    for k in range(j+1,len(a_list)-1):
      p_list=a_list[0:i+1]
      q_list=a_list[i+1:j+1]
      r_list=a_list[j+1:k+1]
      s_list=a_list[k+1:]
      sum_list=[]
      sum_list.append(sum(p_list))
      sum_list.append(sum(q_list))
      sum_list.append(sum(r_list))
      sum_list.append(sum(s_list))
      ans_koho=max(sum_list)-min(sum_list)
      if (ans_koho<ans):
        ans=ans_koho

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
ni=0
nj=0
nk=0
ans=10**15
t=sum(a)
for i in range(n-3):
    ni+=a[i]
    for j in range(i+1,n-2):
        nj+=a[j]
        for k in range (j+1,n-1):
            nk+=a[k]
            nl=t-ni-nj-nk
            ans=min(ans,(max(nk,ni,nj,nl)-min(nk,nj,ni,nl)))
        nk=0
    nj=0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import numpy as np

#line = input().split()
#N = int(line[0])
N = int(input())
line = input().split()
A = np.array([int(a) for a in line])
cumsum = A.cumsum()

n = cumsum.shape[0]

min_abs = sys.maxsize

for p in range(n-1):
    sumP = cumsum[p]
    for q in range(p+1, n-1):
        sumQ = cumsum[q] - sumP
        for r in range(q+1, n-1):
            sumR = cumsum[r] - cumsum[q]
            sumS = cumsum[-1] - cumsum[r]
            abs = max(sumP, sumQ, sumR, sumS) - min(sumP, sumQ, sumR, sumS)
            min_abs = min(min_abs, abs)

print(min_abs)

Submission status: Time Limit Exceeded

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

ans = 1000000000000000000000000000000000000
pair = [0,0,0,0]
for i in range(n-3):
	for j in range(i,n-2):
		for k in range(j,n-1):
			p = sum(a[0:i+1])
			q = sum(a[i+1:j+1])
			r = sum(a[j+1:k+1])
			s = sum(a[k+1:n])
			M = max(p,q,r,s)
			m = min(p,q,r,s)
			if ans > M-m:
				ans =  M-m
				
			
		
	
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def split_list(b,N):
	min_value=100000000000
	for i in range(1,N-2):
		for j in range(i+1,N-1):
			for k in range(j+1,N):
				a1=0
				a2=0
				a3=0
				a4=0

				for a in range(0,i):
					a1+=b[a]
				for a in range(i,j):
					a2+=b[a]
				for a in range(j,k):
					a3+=b[a]
				for a in range(k,N):
					a4+=b[a]

				l=[a1,a2,a3,a4]
				lmin=max(l)-min(l)
				if min_value>lmin:
					min_value=lmin

	print(min_value)


N=int(input())
a=input().split()
b=[int(i) for i in a]

split_list(b,N)

Submission status: Time Limit Exceeded

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

ans=sum(A)
for a in range(3,N):
  for b in range(2,a):
    for c in range(1,b):
      sum1=sum(A[:c])
      sum2=sum(A[c:b])
      sum3=sum(A[b:a])
      sum4=sum(A[a:])
      dif=max(sum1,sum2,sum3,sum4)-min(sum1,sum2,sum3,sum4)
      if dif<ans:
        ans=dif
      if sum2<=sum1:
        break
    if min(sum1,sum2,sum3)==sum3:
      break
  if min(sum1,sum2,sum3,sum4)==sum4:
    break

print(ans)

Submission status: Time Limit Exceeded

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

ans=sum(A)
for a in range(3,N):
  for b in range(2,a):
    for c in range(1,b):
      sum1=sum(A[:c])
      sum2=sum(A[c:b])
      sum3=sum(A[b:a])
      sum4=sum(A[a:])
      dif=max(sum1,sum2,sum3,sum4)-min(sum1,sum2,sum3,sum4)
      if dif<ans:
        ans=dif

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    ai = [int(i) for i in input().split()]

    vs = []
    for i in range(1,n):
        p = sum(ai[0:i])
        for j in range(i+1,n):
            q = sum(ai[i:j])
            for k in range(j+1,n):
                r = sum(ai[j:k])
                s = sum(ai[k:])
                vs.append(abs(max(p,q,r,s) - min(p,q,r,s)))

    print(min(vs))
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
b = [int(i) for i in input().split()]
n = float("inf")
for i in range(a):
     for j in range(i+1,a):
         for k in range(j+1,a):
             m = [sum(b[:i]),sum(b[i:j]),sum(b[j:k]),sum(b[k:])]
             t = max(m) - min(m)
             if t < n:
                 n = t
print(n)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = input().strip().split(' ')
A = [int(x) for x in A]

def returnsub(p,q,r,s):
    ls = [sum(p),sum(q),sum(r),sum(s)]
    return max(ls) - min(ls)

def bfs():
    minsub = -1
    for i1 in range(1,N-2):
        for i2 in range(i1+1,N-1):
            for i3 in range(i2+1,N):
                P = A[0:i1]
                Q = A[i1:i2]
                R = A[i2:i3]
                S = A[i3:]

                tmpsub =returnsub(P,Q,R,S)
                if minsub == -1:
                    minsub = tmpsub
                else:
                    if tmpsub < minsub:
                        minsub = tmpsub
    return minsub
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
mn = float('inf')
for a in range(1,N-2):
    for b in range(a+1,N-1):
        for c in range(b+1,N):
            #print(A[:a],A[a:b],A[b:c],A[c:])
            P = sum(A[:a])
            Q = sum(A[a:b])
            R = sum(A[b:c])
            S = sum(A[c:])
            s_max = max(P,Q,R,S)
            s_min = min(P,Q,R,S)
            dif = abs(s_max - s_min)
            mn = min(mn, dif)
print(mn)

Submission status: Time Limit Exceeded

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

ans=999999999
for a in range(1,N-2):
    for b in range(a+1,N-1):
        for c in range(b+1,N):
            num=[sum(A[:a]),sum(A[a:b]),sum(A[b:c]),sum(A[c:])]
            n=max(num)-min(num)
            if n<ans: ans=n
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n = int(input())
a = list(map(int, input().split()))
c = list(accumulate(a))
ans = float("inf")
x, y = 0, 2
for i in range(1, n - 2):
    while c[x] < c[i] - c[x + 1]:
        x += 1
    y = max(y, i + 1)
    while c[y] - c[i] < c[-1] - c[y + 1]:
        y += 1
    ma = max(c[x], c[i] - c[x], c[y] - c[i], c[-1] - c[y])
    mi = min(c[x], c[i] - c[x], c[y] - c[i], c[-1] - c[y])
    ans = min(ans, ma - mi)
print(ans)

Submission status: Accepted

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

A_sum = []
tmp = 0
for a in A:
  tmp += a
  A_sum.append(tmp)

ans = 10**10
for part_mid in range(1,N-2):
  sum_l = A_sum[part_mid]
  part_lft = bisect.bisect_right(A_sum, (A_sum[part_mid]+0)//2)-1
  if part_lft == -1 or abs(2*A_sum[part_lft+1] - A_sum[part_mid]) < abs(2*A_sum[part_lft] - A_sum[part_mid]):
    part_lft += 1
  
  part_rgt = bisect.bisect_right(A_sum, (A_sum[N-1]+A_sum[part_mid])//2)-1
  if part_rgt < part_mid or abs(2*A_sum[part_rgt+1] - (A_sum[N-1]+A_sum[part_mid])) < abs(2*A_sum[part_rgt] - (A_sum[N-1]+A_sum[part_mid])):
    part_rgt += 1
  s = [A_sum[part_lft], A_sum[part_mid] - A_sum[part_lft], A_sum[part_rgt]-A_sum[part_mid], A_sum[N-1] - A_sum[part_rgt]]
  ans = min(ans, max(s) - min(s))
  #print(s, part_mid, A_sum)
  
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

# 累積和によって、各区間の和をO(1)で求められるようにしておく
# B,C,D,Eに分けたときに、CとDの切れ目を固定する
# Cの終わりが決まったとき、Bを先頭から探索していくとB,Cを切るベストな点が分かる
# （BとCの絶対値の差が最小になる点）
# 同様に、CとDを切るベストな点が分かる
# これらのindexを覚えておくと、CとDの切れ目を移動したときにこの点から開始することが出来て
# O(N)の定数倍で解くことが出来る

N = int(readline())
A = [0] + list(map(int,readline().split()))
for i in range(1, len(A)):
  A[i] += A[i - 1]

#print(A)

b_end = 1
c_end = 2
d_end = 3
e_end = len(A) - 1
bc_best = 10 ** 10
de_best = 10 ** 10
ans = 10 ** 10
def get_ans(b_end,c_end,d_end):
  B = A[b_end]
  C = A[c_end] - A[b_end]
  D = A[d_end] - A[c_end]
  E = A[-1] - A[d_end]
#  print("get_ans b_end",b_end,"c_end",c_end,"d_end",d_end)
#  print("get_ans B",B,"C",C,"D",D,"E",E)
  return max(B,C,D,E) - min(B,C,D,E)

for c_end in range(2, N - 1):
  # b_endを右に進める条件は、今BよりCのほうが大きいこと 且つ c_endに追いつかないこと
  # Bのほうが大きくなったら、その直前と比べてどっちのほうが絶対値が小さいかを確認する
  B = A[b_end]
  C = A[c_end] - A[b_end]
  best_b_end = b_end
  if B != C:
    while b_end + 1 < c_end and B < C:
      b_end += 1
      tempB = B
      tempC = C
      B = A[b_end]
      C = A[c_end] - A[b_end]
      if B == C:
        best_b_end = b_end
        break
      if B > C:
        # ここでBのほうが大きくなったら有利なほうを採用する
        if abs(tempB - tempC) > abs(B - C):
          best_b_end = b_end
        break
      else:
        best_b_end = b_end
  b_end = best_b_end
  
  D = A[d_end] - A[c_end]
  E = A[e_end] - A[d_end]
  best_d_end = d_end
  if D != E:
    while d_end + 1 < e_end and D < E:
      d_end += 1
      tempD = D
      tempE = E
      D = A[d_end] - A[c_end]
      E = A[e_end] - A[d_end]
      if D == E:
        best_d_end = d_end
        break
      if D > E:
        if abs(tempD - tempE) > abs(D - E):
          best_d_end = d_end
        break
      else:
        best_d_end = d_end
  d_end = best_d_end
    
  val = get_ans(b_end,c_end,d_end)
  if val < ans:
    ans = val
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = [0]*N

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

X = [0]*N
Y = [0]*N

p = 0
# i番目とi+1番目の間で切る
for i in range(1,N-2):
    # p番目とp+1番目の間で切る
    while S[p] * 2 < S[i] and p < i-1:
        p += 1
    
    if p == 0:
        X[i] = p
    elif abs(S[i]-2*S[p]) < abs(S[i]-2*S[p-1]):
        X[i] = p
    else:
        X[i] = p-1
    
    # print('LEFT',i,p,X[i],abs(S[i]-2*S[X[i]]))

q = 2
# i番目とi+1番目の間で切る
for i in range(1,N-2):
    if q <= i:
        q = i+1
    # q番目とq+1番目の間で切る
    while (S[q]-S[i])*2 < S[N-1]-S[i] and q < N-2:
        q += 1
    
    if q == i+1:
        Y[i] = q
    elif abs((S[N-1]-S[q])-(S[q]-S[i])) < abs((S[N-1]-S[q-1])-(S[q-1]-S[i])):
        Y[i] = q
    else:
        Y[i] = q-1
    
    # print('RIGHT',i,q,Y[i],abs((S[N-1]-S[Y[i]])-(S[Y[i]]-S[i])))

# print(S)
# print(X)
# print(Y)

ans = 10**15
for i in range(1,N-2):
    cut = (S[X[i]],S[i]-S[X[i]],S[Y[i]]-S[i],S[N-1]-S[Y[i]])
    ans = min(ans,max(cut)-min(cut))
    # print(i,ans)

print(ans)

Submission status: Accepted

Solution code:
from itertools import *
N = int(input())
A = list(accumulate(map(int,input().split())))
l = 0
r = 2
t = A[-1]
a = t

for m in A[1:-2]:
  while abs(t-2*A[r]+m)>abs(t-2*A[r+1]+m):
    r+=1
  while abs(m-2*A[l])>abs(m-2*A[l+1]):
    l+=1
  x = sorted([A[l],m-A[l],A[r]-m,t-A[r]])
  a = min(a,x[3]-x[0])

print(a)

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_left

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

    # cumulative sum
    # cs[i] = sum(a[:i+1])
    cs = [0] * n
    for i in range(n):
        cs[i] = cs[i-1] + a[i]

    # search all possible indexes of middle split
    ans = 10**15
    for middle in range(2, n-1):
        # first_half = a[:middle]
        first = bisect_left(cs, cs[middle-1]//2, lo=1, hi=middle)
        if abs((cs[middle-1] - cs[first-1]) - cs[first-1]) < abs((cs[middle-1] - cs[first]) - cs[first]):
            p = cs[first-1]
            q = cs[middle-1] - cs[first-1]
        else:
            p = cs[first]
            q = cs[middle-1] - cs[first]

        # latter_half = a[middle:]
        last = bisect_left(cs, (cs[-1] + cs[middle-1])//2, lo=middle+1, hi=n)
        if abs((cs[-1] - cs[last-1]) - (cs[last-1] - cs[middle-1])) < abs((cs[-1] - cs[last]) - (cs[last] - cs[middle-1])):
            r = cs[last-1] - cs[middle-1]
            s = cs[-1] - cs[last-1]
        else:
            r = cs[last] - cs[middle-1]
            s = cs[-1] - cs[last]
        
        diff = max(p, q, r, s) - min(p, q, r, s)
        if diff < ans:
            ans = diff
    
    print(ans)

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = IL()

def ACC1(l):
  N = len(l)
  ret = [0]*(N+1)
  for i in range(N):
    ret[i+1] = ret[i]+l[i]
  return ret
def calc_half(l,r):
  start = ACC[l]
  end = ACC[r+1]
  p = bisect.bisect(ACC,-((-(start+end))//2))
  P1,Q1 = ACC[p]-ACC[l],ACC[r+1]-ACC[p]
  P2,Q2 = ACC[p-1]-ACC[l],ACC[r+1]-ACC[p-1]
  #print(l,r,p,q,P1,Q1,P2,Q2)
  if abs(P1-Q1)<abs(P2-Q2):
    return P1,Q1
  else:
    return P2,Q2
ans = INF
ACC = ACC1(A)
#print(ACC)
for i in range(1,N-2):
  P,Q = calc_half(0,i)
  R,S = calc_half(i+1,N-1)
  #print(P,Q,R,S)
  ans = min(ans,max(P,Q,R,S)-min(P,Q,R,S))
print(ans)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
A = [0] + LI()

from itertools import accumulate

S = list(accumulate(A))

ans = 10**18
for i in range(2,N-1):  # AをA_1~A_i,A_(i+1)~A_Nに分割
    left = S[i]
    right = S[N]-S[i]
    # 更に各々を、和が近くなるように2分割する
    low1,high1 = 0,i
    while low1 + 1 < high1:
        mid1 = (low1+high1)//2
        if S[mid1] >= (left+1)//2:
            high1 = mid1
        else:
            low1 = mid1
    low2,high2 = i,N
    while low2 + 1 < high2:
        mid2 = (low2+high2)//2
        if S[mid2]-S[i] >= (right+1)//2:
            high2 = mid2
        else:
            low2 = mid2
    x1 = max(S[high1],S[high2]-left) - min(left-S[high1],right-S[high2]+left)
    x2 = max(S[high1],right-S[high2-1]+left) - min(left-S[high1],S[high2-1]-left)
    x3 = max(left-S[high1-1],S[high2]-left) - min(S[high1-1],right-S[high2]+left)
    x4 = max(left-S[high1-1],right-S[high2-1]+left) - min(S[high1-1],S[high2-1]-left)
    ans = min(ans,x1,x2,x3,x4)

print(ans)

Submission status: Accepted

Solution code:
from bisect import *
from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
S = [0] + list(accumulate(A))
res = float("inf")
for i in range(2,N-1):
    j = bisect_left(S,S[i]//2)
    if abs(S[i]-2*S[j]) >= abs(S[i]-2*S[j-1]):
        P =[S[j-1], S[i]-S[j-1]]
    else: P = [S[j], S[i]-S[j]]
    T = S[-1] - S[i]
    j = bisect_left(S,S[-1]-T//2)
    U1, U2 = S[j]-S[i],S[j-1]-S[i]
    if abs(T-2*U1) >= abs(T-2*U2):
        P += [U2, T-U2]
    else: P += [U1, T-U1]
    tmp = max(P)-min(P)
    res = min(res, tmp)
print(res)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
acc=[0]*N
acc[0]=A[0]
for i in range(1,N):
  acc[i]=acc[i-1]+A[i]
def f(x,y):
  if x==0:
    return acc[y]
  else:
    return acc[y]-acc[x-1]
left=0
right=2

import math
ans=math.inf
for mid in range(1,N-2):

  while abs(f(0,left)-f(left+1,mid))>=abs(f(0,left+1)-f(left+2,mid)):
    left+=1
    if left==mid-1:
      break
  while abs(f(mid+1,right)-f(right+1,N-1))>=abs(f(mid+1,right+1)-f(right+2,N-1)):
    right+=1
    if right==N-2:
      break
  list=[f(0,left),f(left+1,mid),f(mid+1,right),f(right+1,N-1)]
  tans=max(list)-min(list)
  ans=min(tans,ans)
print(ans)

Submission status: Accepted

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

from itertools import accumulate
ac=list(accumulate(a))

ans=float("inf")
l=0
r=1
for i in range(1, n-2):
    while abs(ac[i]-2*ac[l+1]) < abs(ac[i]-2*ac[l]) and l < i+1:
        l+=1
    while abs(ac[-1]-2*ac[r+1]+ac[i]) < abs(ac[-1]-2*ac[r]+ac[i]) and r < n-2:
        r+=1
    t=[ac[l], ac[i]-ac[l], ac[r]-ac[i], ac[-1]-ac[r]]
    ans=min(ans, max(t)-min(t))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
tmp = 0
lr = [0]
for a in A:
    tmp += a
    lr.append(tmp)

ans = float('inf')

f=1
g=3
for i in range(2, N - 1):

    while abs(lr[i] - lr[f] - lr[f]) > abs(lr[i] - lr[f + 1] - lr[f + 1]):
        f += 1
    while abs((lr[-1] - lr[g]) - (lr[g] - lr[i])) > abs((lr[-1] - lr[g + 1]) - (lr[g + 1] - lr[i])):
        g += 1
    l = (lr[f], lr[i] - lr[f], lr[-1] - lr[g], lr[g] - lr[i])
    ans = min(ans, max(l) - min(l))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from itertools import accumulate, islice
from bisect import bisect_left

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

ys = list(accumulate(xs))
zs, total = ys[:-1], ys[-1]

res = max(xs) - min(xs)
for i, z in islice(enumerate(zs), 1, n-1):
    j = bisect_left(zs, z//2)
    splits = ((zs[j+k], z - zs[j+k]) for k in (-1, 0, 1) if 0 <= j+k <= i)
    a, b = min(splits, key=lambda s: abs(s[0]-s[1]))

    j = bisect_left(zs, (total - z)//2 + z)
    splits = ((zs[j+k] - z, total - zs[j+k])
              for k in (-1, 0, 1) if i <= j+k <= n-2)
    c, d = min(splits, key=lambda s: abs(s[0]-s[1]))

    minn, _, _, maxx = sorted((a, b, c, d))
    if maxx - minn < res:
        res = maxx - minn

print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = b[i] + a[i]
x = [[0, 0] for _ in range(n - 3)]
j = 1
for i in range(2, n - 1):
    while True:
        if i == j + 1:
            x[i - 2][0] = b[j]
            break
        if abs(b[i] - 2 * b[j]) > abs(b[i] - 2 * b[j + 1]):
            j += 1
        else:
            x[i - 2][0] = b[j]
            break
j = n - 1
for i in range(n - 2, 1, -1):
    while True:
        if i == j - 1:
            x[i - 2][1] = b[j]
            break
        if abs(b[n] + b[i] - 2 * b[j]) > abs(b[n] + b[i] - 2 * b[j - 1]):
            j -= 1
        else:
            x[i - 2][1] = b[j]
            break
ans = 1145141919810
for i in range(n - 3):
    s = [x[i][0], b[i + 2] - x[i][0], x[i][1] - b[i + 2], b[n] - x[i][1]]
    ans = min(ans, max(s) - min(s))
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n=int(input())
a=list(map(int,input().split()))
bl=[0]
for i in a:bl.append(bl[-1]+i)
br=[0]
for i in a[::-1]:br.append(br[-1]+i)
def fl(r):
  suma=bl[r+1]
  ir=bisect_left(bl,suma//2)
  ans11,ans12=bl[ir],suma-bl[ir]
  ans21,ans22=bl[ir-1],suma-bl[ir-1]
  if abs(ans11-ans12)<abs(ans21-ans22):return[ans11,ans12]
  else:return[ans21,ans22]
def fr(l):
  r=(n-1)-l
  suma=br[r+1]
  ir=bisect_left(br,suma//2)
  ans11,ans12=br[ir],suma-br[ir]
  ans21,ans22=br[ir-1],suma-br[ir-1]
  if abs(ans11-ans12)<abs(ans21-ans22):return[ans11,ans12]
  else:return[ans21,ans22]
ans=10**20
for i in range(1,n-1):
  l=i
  r=i+1
  ll,lr=fl(i)
  rl,rr=fr(i+1)
  ans=min(ans,max(ll,lr,rl,rr)-min(ll,lr,rl,rr))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
R = [0] * (N + 1)
for i in range(N):
  R[i + 1] += R[i] + A[i]
#print(R)  

ans = 10 ** 15
l, r = 2, 4
for i in range(3, N):#R[:i]とR[i:]に切る
  #R[:l], R[l:i], R[i:r], R[r:]
  #R[l - 1] と R[i - 1] - R[l - 1] の差を考える
  
  while abs(R[i - 1] - 2 * R[l]) <= abs(R[i - 1] - 2 * R[l - 1]):
    l += 1
    
  #R[r - 1] - R [i - 1] と R[N] - R[r - 1] の差を考える  
  while abs(R[N] - 2 * R[r] + R[i - 1]) <= abs(R[N] - 2 * R[r - 1] + R[i - 1]):
    r += 1  
  
  now_max = max(max(R[l - 1], R[i - 1] - R[l - 1]), max(R[r - 1] - R[i - 1], R[N] - R[r - 1]))
  now_min = min(min(R[l - 1], R[i - 1] - R[l - 1]), min(R[r - 1] - R[i - 1], R[N] - R[r - 1]))
  ans = min(ans, now_max - now_min)
  #print(R[l - 1], R[i - 1] - R[l - 1],R[r - 1] - R[i - 1], R[N] - R[r - 1], ans)
print(ans)

Submission status: Accepted

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

ans = 10 ** 18


A = tuple(accumulate(A, initial=0))
i = 1
j = 3


for mid in range(2, N - 1):
    # 左側をできるだけ等分
    b = A[i] - A[0]
    c = A[mid] - A[i]
    while i + 1 < mid and abs(b - c) > abs(A[mid] + A[0] - 2 * A[i+1]):
        i += 1
        b = A[i] - A[0]
        c = A[mid] - A[i]
    # 右側をできるだけ等分
    j = max(j, mid + 1)
    d = A[j] - A[mid]
    e = A[N] - A[j]
    while j + 1 < N and abs(d - e) > abs(A[N] + A[mid] - 2 * A[j+1]):
        j += 1
        d = A[j] - A[mid]
        e = A[N] - A[j]

    res = max(b, c, d, e) - min(b, c, d, e)
    ans = min(ans, res)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
tmp=0
lr=[0]
for a in A:
  tmp+=a
  lr.append(tmp)

ans=float('inf')

f,g=1,3
for i in range(2,N-1):
  while abs(lr[i]-lr[f]-lr[f])>abs(lr[i]-lr[f+1]-lr[f+1]):
    f+=1
  while abs((lr[-1]-lr[g])-(lr[g]-lr[i]))>abs((lr[-1]-lr[g+1])-(lr[g+1]-lr[i])):
    g+=1
  l=(lr[f],lr[i]-lr[f],lr[-1]-lr[g],lr[g]-lr[i])
  ans=min(ans,max(l)-min(l))

print(ans)

Submission status: Accepted

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

class Accumulation:
    def __init__(self,X,accumfunc,init_val=0):
        self.X = X
        self.accumfunc = accumfunc

        N = len(X)
        v1 = [0] * (N+1)
        v1[0] = init_val

        for i in range(N):
            v1[i+1] = accumfunc(v1[i],X[i])

        self.v1 = v1
    
    # 0-index
    def query(self,l,r):
        return self.v1[r+1] - self.v1[l]
    
    def get_array(self):
        return self.v1

INF=10**20
def main():
    N=ii()
    A=list(mi())
    B = []
    for a in A:
        B.append(a*2)

    def add(x,y): return x+y

    acc = Accumulation(A,add)
    accB = Accumulation(B,add)

    vA = acc.get_array()
    vB = accB.get_array()

    ans = INF
    for j in range(N):
        i1 = bisect.bisect_left(vB,vA[j+1]) - 1 

        Q,P=0,INF
        for di in [-1,0,1]:
            if not 0<= i1+di < N: continue
            q,p = acc.query(i1+di+1,j), acc.query(0,i1+di)
            if abs(p-q) < abs(P-Q):
                Q,P = q,p

        S,R = 0,INF
        i2 = bisect.bisect_left(vB,vA[N]+vA[j+1]) - 1
        for di in [-1,0,1]:
            if not 0<= i2+di < N: continue
            s,r = acc.query(i2+di+1,N-1), acc.query(j+1,i2+di)
            if abs(s-r) < abs(S-R):
                S,R=s,r



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


    print(ans)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
S = [0]

for i in range(N):
    S.append(S[-1] + A[i])

res = 10**18

for i in range(2, N - 1):
    hi = i
    lo = 0
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if S[mid] - S[0] >= S[i] - S[mid]:
            hi = mid
        else:
            lo = mid
    p = S[hi] - S[0]
    q = S[i] - S[hi]
    if p - q > (q + A[hi - 1]) - (p - A[hi - 1]):
        p -= A[hi - 1]
        q += A[hi - 1]

    hi = N
    lo = i
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if S[mid] - S[i] >= S[N] - S[mid]:
            hi = mid
        else:
            lo = mid
    s = S[hi] - S[i]
    t = S[N] - S[hi]
    if s - t > (t + A[hi - 1]) - (s - A[hi - 1]):
        s -= A[hi - 1]
        t += A[hi - 1]

    res = min(res, max(p, q, s, t) - min(p, q, s, t))

print(res)