Problem:


Score : 600 points

Problem Statement

Snuke has an integer sequence A of length N.

He will make three cuts in A and divide it into four (non-empty) contiguous subsequences B, C, D and E.
The positions of the cuts can be freely chosen.

Let P,Q,R,S be the sums of the elements in B,C,D,E, respectively.
Snuke is happier when the absolute difference of the maximum and the minimum among P,Q,R,S is smaller.
Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.

Constraints

4 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.

Sample Input 1

5
3 2 4 1 2

Sample Output 1

2

If we divide A as B,C,D,E=(3),(2),(4),(1,2), then P=3,Q=2,R=4,S=1+2=3.
Here, the maximum and the minimum among P,Q,R,S are 4 and 2, with the absolute difference of 2.
We cannot make the absolute difference of the maximum and the minimum less than 2, so the answer is 2.

Sample Input 2

10
10 71 84 33 6 47 23 25 52 64

Sample Output 2

36

Sample Input 3

7
1 2 3 1000000000 4 5 6

Sample Output 3

999999994



Sample input:
5
3 2 4 1 2


Sample output:
2

Submission status: Wrong Answer

Solution code:
import 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 == 0 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(ans)

Submission status: Wrong Answer

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
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のbestな場所を探す
#  print("c_end",c_end)
  bc_best = 10 ** 10
  best_b_end = -1
  while b_end < c_end:
    B = A[b_end]
    C = A[c_end] - A[b_end]
#    print("b_end",b_end,"c_end",c_end,"B",B,"C",C)
    diff = abs(B - C)
    if bc_best > diff:
      bc_best = diff
      best_b_end = b_end
    else:
      break
    if b_end + 1 < c_end:
      b_end += 1
    else:
      break
  if best_b_end != -1:
    b_end = best_b_end
#  print("bc_best",bc_best,"b_end",b_end,"c_end",c_end)
  Bbest = A[b_end]
  Cbest = A[c_end] - A[b_end]
  de_best = 10 ** 10
  best_d_end = -1
  while d_end < len(A) - 1:
#    print("d_end",d_end)
    D = A[d_end] - A[c_end]
    E = A[-1] - A[d_end]
#    print("c_end",c_end,"d_end",d_end,"D",D,"E",E)
    score = max(Bbest,Cbest,D,E) - min(Bbest,Cbest,D,E)
    if de_best > score:
      de_best = score
      best_d_end = d_end
    else:
      break
    if d_end + 1 < N:
      d_end += 1
    else:
#      print("d_end + 1",d_end + 1,"なのでbreak")
      break
  if best_d_end == -1:
    continue
  d_end = best_d_end
  if b_end == c_end or c_end == d_end or d_end == N or b_end == 0:
    asfi0eiwo
  val = get_ans(b_end,c_end,d_end)
  if ans > val:
    ans = val
    
print(ans)

Submission status: Wrong Answer

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
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のbestな場所を探す
#  print("c_end",c_end)
  bc_best = 10 ** 10
  best_b_end = -1
  while b_end < c_end:
    B = A[b_end]
    C = A[c_end] - A[b_end]
#    print("b_end",b_end,"c_end",c_end,"B",B,"C",C)
    diff = abs(B - C)
    if bc_best > diff:
      bc_best = diff
      best_b_end = b_end
    else:
      break
    if b_end + 1 < c_end:
      b_end += 1
    else:
      break
  if best_b_end != -1:
    b_end = best_b_end
#  print("bc_best",bc_best,"b_end",b_end,"c_end",c_end)
  Bbest = A[b_end]
  Cbest = A[c_end] - A[b_end]
  de_best = 10 ** 10
  best_d_end = -1
  while d_end < len(A) - 1:
#    print("d_end",d_end)
    D = A[d_end] - A[c_end]
    E = A[-1] - A[d_end]
#    print("c_end",c_end,"d_end",d_end,"D",D,"E",E)
    score = max(Bbest,Cbest,D,E) - min(Bbest,Cbest,D,E)
    if de_best > score:
      de_best = score
      best_d_end = d_end
    else:
      break
    if d_end + 1 < N:
      d_end += 1
    else:
#      print("d_end + 1",d_end + 1,"なのでbreak")
      break
  if best_d_end == -1:
    continue
  d_end = best_d_end
  val = get_ans(b_end,c_end,d_end)
  if ans > val:
    ans = val
    
print(ans)

Submission status: Wrong Answer

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
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のbestな場所を探す
#  print("c_end",c_end)
  bc_best = 10 ** 10
  best_b_end = -1
  while b_end < c_end:
    B = A[b_end]
    C = A[c_end] - A[b_end]
#    print("b_end",b_end,"c_end",c_end,"B",B,"C",C)
    diff = abs(B - C)
    if bc_best > diff:
      bc_best = diff
      best_b_end = b_end
    else:
      break
    if b_end + 1 < c_end:
      b_end += 1
    else:
      break
  b_end = best_b_end
#  print("bc_best",bc_best,"b_end",b_end,"c_end",c_end)
  Bbest = A[b_end]
  Cbest = A[c_end] - A[b_end]
  de_best = 10 ** 10
  best_d_end = -1
  while d_end < len(A) - 1:
#    print("d_end",d_end)
    D = A[d_end] - A[c_end]
    E = A[-1] - A[d_end]
#    print("c_end",c_end,"d_end",d_end,"D",D,"E",E)
    score = max(Bbest,Cbest,D,E) - min(Bbest,Cbest,D,E)
    if de_best > score:
      de_best = score
      best_d_end = d_end
    else:
      break
    if d_end + 1 < N:
      d_end += 1
    else:
#      print("d_end + 1",d_end + 1,"なのでbreak")
      break
  if best_d_end == -1:
    continue
  d_end = best_d_end
  val = get_ans(b_end,c_end,d_end)
  if ans > val:
    ans = val
    
print(ans)

Submission status: Wrong Answer

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
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のbestな場所を探す
#  print("c_end",c_end)
  bc_best = 10 ** 10
  
  while b_end < c_end:
    B = A[b_end]
    C = A[c_end] - A[b_end]
#    print("b_end",b_end,"c_end",c_end,"B",B,"C",C)
    diff = abs(B - C)
    if bc_best > diff:
      bc_best = diff
    else:
      if b_end - 1 > 0:
        b_end -= 1
      break # 差が広がるようになったらいったんもとに戻す
    if b_end + 1 < c_end:
      b_end += 1
    else:
      break
#  print("bc_best",bc_best,"b_end",b_end,"c_end",c_end)
  Bbest = A[b_end]
  Cbest = A[c_end] - A[b_end]
  de_best = 10 ** 10
  best_d_end = -1
  while d_end < len(A) - 1:
#    print("d_end",d_end)
    D = A[d_end] - A[c_end]
    E = A[-1] - A[d_end]
#    print("c_end",c_end,"d_end",d_end,"D",D,"E",E)
    score = max(Bbest,Cbest,D,E) - min(Bbest,Cbest,D,E)
    if de_best > score:
      de_best = score
      best_d_end = d_end
    else:
      if d_end - 2 > c_end:
        d_end -= 1
#      print("ここでbreak",d_end)
      break
    if d_end + 1 < N:
      d_end += 1
    else:
#      print("d_end + 1",d_end + 1,"なのでbreak")
      break
  if best_d_end == -1:
    continue
  val = get_ans(b_end,c_end,best_d_end)
  if ans > val:
    ans = val
    
print(ans)

Submission status: Wrong Answer

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
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 - 2):
  # b_endのbestな場所を探す
#  print("c_end",c_end)
  bc_best = 10 ** 10
  while b_end < c_end:
    B = A[b_end]
    C = A[c_end] - A[b_end]
#    print("b_end",b_end,"c_end",c_end,"B",B,"C",C)
    diff = abs(B - C)
    if bc_best > diff:
      bc_best = diff
    else:
      if b_end - 1 > 0:
        b_end -= 1
      break # 差が広がるようになったらいったんもとに戻す
    if b_end + 1 < c_end:
      b_end += 1
    else:
      break
#  print("bc_best",bc_best,"b_end",b_end,"c_end",c_end)
  Bbest = A[b_end]
  Cbest = A[c_end] - A[b_end]
  de_best = 10 ** 10
  best_d_end = -1
  while d_end < len(A) - 1:
#    print("d_end",d_end)
    D = A[d_end] - A[c_end]
    E = A[-1] - A[d_end]
#    print("c_end",c_end,"d_end",d_end,"D",D,"E",E)
    score = max(Bbest,Cbest,D,E) - min(Bbest,Cbest,D,E)
    if de_best > score:
      de_best = score
      best_d_end = d_end
    else:
      if d_end - 2 > c_end:
        d_end -= 1
#      print("ここでbreak",d_end)
      break
    if d_end + 1 < N:
      d_end += 1
    else:
#      print("d_end + 1",d_end + 1,"なのでbreak")
      break
  if best_d_end == -1:
    continue
  val = get_ans(b_end,c_end,best_d_end)
  if ans > val:
    ans = val
    
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# 全体の和を求めて平均を出す。
# 左から順に要素を見ていき、平均との差の絶対値が最小になった時点で確定
# ただし、残りN個作る必要があるときに残数がN未満だったらその時点で確定する

import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int,readline().split()))
ave = sum(A) / 4
#print(ave)
# aveが目指す数字
ind = 0
data = [0] * 4
for i in range(1, 5):
  #print("i",i,"ind",ind)
  # i個目のブロックについて探索する
  
  # これが最終ブロックの場合は、すべて採用する
  if i == 4:
    data[i - 1] = sum(A[ind:])
    break
  cur = 0
  diff = 0
  for j in range(ind, len(A) - (4 - i)):
    cur += A[j]
    #print("cur",cur)
    if cur == ave:
      # そのまま採用する
      ind = j + 1
      break
    if cur < ave:
      diff = abs(cur - ave)
      ind = j
      #print("diff",diff)
    else:
      # curがaveを追い抜いたとき
      #print("cur",cur,"がave",ave,"を追い抜いた")
      new_diff = abs(cur - ave)
      #print("new_diff",new_diff,"diff",diff)
      if j == ind:
        # 最初は巻き戻せないのでそのまま採用
        ind = j + 1
      elif new_diff <= diff:# 新規の差分のほうが小さいので、そのまま採用
        ind = j + 1
        #print("採用")
      else: # 巻き戻す
        #print("巻き戻すcur",cur,"A[j]",A[j])
        ind = j
        cur -= A[j]
        #print("cur",cur)
      break
  else:
    # breakしなかったときはそのまま採用
    ind = j + 1
  data[i - 1] = cur
  #print("data",data,"ind",ind)
#print(data)
print(max(data) - min(data))

Submission status: Wrong Answer

Solution code:
import heapq
n=int(input())
a= list(map(int,input().split()))
imos = [0]*(n+1)
for i in range(1,n+1):imos[i]=imos[i-1]+a[i-1]
def mindiff(first,last):
    rl=first
    sr=last
    l=first
    r=last-1
    m=-1
    rsdiff = []
    heapq.heapify(rsdiff)
    while r-l>1:
        m=(l+r)//2
        rr = imos[m]-imos[rl]
        ss = imos[sr+1]-imos[m]
        if rr==ss:break
        elif rr>ss:r=m
        elif rr<ss:l=m
    rsdiff = []
    heapq.heapify(rsdiff)
    if m==-1:
        if l==r:return (min(a[first:last+1]),max(a[first:last+1]))
        else:
            for i in range(l,r+1):
                rr = imos[i+1]-imos[rl]
                ss = imos[sr+1]-imos[i+1]
                heapq.heappush(rsdiff,(abs(rr-ss),rr,ss))
            ret = rsdiff[0]
            return (min(ret[1:]),max(ret[1:]))
    else:
        for i in range(m-1,m+2):
            rr = imos[i+1]-imos[rl]
            ss = imos[sr+1]-imos[i+1]
            heapq.heappush(rsdiff,(abs(rr-ss),rr,ss))
        ret = rsdiff[0]
        return (min(ret[1:]),max(ret[1:]))

gmin = 999999999999999999999
for i in range(1,n-2):
    left = mindiff(0,i)
    right = mindiff(i+1,n-1)
    four = list(left)+list(right)
    gmin=min(gmin,max(four)-min(four))
print(gmin)

Submission status: Wrong Answer

Solution code:
# D - Equal Cut
import bisect

N = int(input())
A = list(int(a) for a in input().split())

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

splt = Acum[-1]//4
#print(splt)
B = bisect.bisect_left(Acum, splt)
if abs(Acum[B]-splt) > abs(Acum[B-1]-splt):
    B -= 1
splt = Acum[B] + (Acum[-1] - Acum[B])//3
#print(splt)
C = bisect.bisect_left(Acum, splt)
if abs(Acum[C] - splt) > abs(Acum[C-1] - splt):
    C -= 1
    if C == B:
        C += 1
splt = Acum[C] + (Acum[-1] - Acum[C])//2
#print(splt)
D = bisect.bisect_left(Acum, splt)
if abs(Acum[D] - splt) > abs(Acum[D-1] - splt):
    D -= 1
    if D == C:
        D += 1
#print(splt)
#print(B, C, D)
#print(Acum)
ans = list((Acum[B], Acum[C]-Acum[B], Acum[D]-Acum[C],Acum[-1]-Acum[D]))
print(abs(min(ans) - max(ans)))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
n = int(input())
a = [int(x) for x in input().split()]

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

ans = 10**30
for i in range(2,n-1):
  b = cum[bisect_left(cum, cum[i]//2)-1]
  c = cum[i]-b
  d = cum[bisect_left(cum, (cum[n]-cum[i])//2+cum[i])] - cum[i]
  e = cum[n] - (b+c+d)
  ans = min(ans, max(b,c,d,e) - min(b,c,d,e))
  
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
n = int(input())
a = [int(x) for x in input().split()]

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

ans = 10**30
for i in range(2,n-1):
  b = cum[bisect_left(cum[:i+1], cum[i]//2)-1]
  c = cum[i]-b
  d = cum[i+bisect_left(cum[i+1:], (cum[n]-cum[i])//2+cum[i])] - cum[i]
  e = cum[n] - (b+c+d)
  ans = min(ans, max(b,c,d,e) - min(b,c,d,e))
  
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
tmp=0
ca=[tmp]
for ai in a:
  tmp+=ai
  ca.append(tmp)
from bisect import bisect_right,bisect_left
ans=float('inf')

# 数列をまず半分に区切る。左i個と右n-i個
for i in range(2,n-1):
  # 左の数列の総和の半分
  tmp=ca[i]//2
  l=bisect_left(ca,tmp)
  r=l-1
  k=l+1

  if abs(ca[l]-(ca[i]-ca[l]))<=abs(ca[r]-(ca[i]-ca[r])) and abs(ca[l]-(ca[i]-ca[l]))<=abs(ca[k]-(ca[i]-ca[k])):
    b,c=ca[l],ca[i]-ca[l]
  elif abs(ca[r]-(ca[i]-ca[r]))<=abs(ca[l]-(ca[i]-ca[l])) and abs(ca[r]-(ca[i]-ca[r]))<=abs(ca[k]-(ca[i]-ca[k])):
    b,c=ca[r],ca[i]-ca[r]
  else:
    b,c=ca[k],ca[i]-ca[k]

  # 右の数列の総和の半分
  tmp=(ca[-1]+ca[i+1])//2
  l=bisect_left(ca,tmp)
  r=l-1
  k=min(l+1,n)
  if abs(ca[-1]-ca[l]-(ca[l]-ca[i]))<=abs(ca[-1]-ca[r]-(ca[r]-ca[i])) and abs(ca[-1]-ca[l]-(ca[l]-ca[i]))<=abs(ca[-1]-ca[k]-(ca[k]-ca[i])):
    d,e=ca[-1]-ca[l],ca[l]-ca[i]
  elif abs(ca[-1]-ca[r]-(ca[r]-ca[i]))<=abs(ca[-1]-ca[l]-(ca[l]-ca[i])) and abs(ca[-1]-ca[r]-(ca[r]-ca[i]))<=abs(ca[-1]-ca[k]-(ca[k]-ca[i])):
    d,e=ca[-1]-ca[r],ca[r]-ca[i]
  else:
    d,e=ca[-1]-ca[k],ca[k]-ca[i]

  ans=min(ans,max(b,c,d,e)-min(b,c,d,e))
  #print(left,right)
  #print(b,c,d,e)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
tmp=0
ca=[tmp]
for ai in a:
  tmp+=ai
  ca.append(tmp)
from bisect import bisect_right,bisect_left
ans=float('inf')

# 数列をまず半分に区切る。左i個と右n-i個
for i in range(2,n-1):
  # 左の数列の総和の半分
  tmp=ca[i]/2
  l=bisect_left(ca,tmp)
  r=l-1
  k=l+1

  if abs(ca[l]-(ca[i]-ca[l]))<=abs(ca[r]-(ca[i]-ca[r])) and abs(ca[l]-(ca[i]-ca[l]))<=abs(ca[k]-(ca[i]-ca[k])):
    b,c=ca[l],ca[i]-ca[l]
  elif abs(ca[r]-(ca[i]-ca[r]))<=abs(ca[l]-(ca[i]-ca[l])) and abs(ca[r]-(ca[i]-ca[r]))<=abs(ca[k]-(ca[i]-ca[k])):
    b,c=ca[r],ca[i]-ca[r]
  else:
    b,c=ca[k],ca[i]-ca[k]

  # 右の数列の総和の半分
  tmp=(ca[-1]+ca[i+1])/2
  l=bisect_left(ca,tmp)
  r=l-1
  k=min(l+1,n)
  if abs(ca[-1]-ca[l]-(ca[l]-ca[i]))<=abs(ca[-1]-ca[r]-(ca[r]-ca[i])) and abs(ca[-1]-ca[l]-(ca[l]-ca[i]))<=abs(ca[-1]-ca[k]-(ca[k]-ca[i])):
    d,e=ca[-1]-ca[l],ca[l]-ca[i]
  elif abs(ca[-1]-ca[r]-(ca[r]-ca[i]))<=abs(ca[-1]-ca[l]-(ca[l]-ca[i])) and abs(ca[-1]-ca[r]-(ca[r]-ca[i]))<=abs(ca[-1]-ca[k]-(ca[k]-ca[i])):
    d,e=ca[-1]-ca[r],ca[r]-ca[i]
  else:
    d,e=ca[-1]-ca[k],ca[k]-ca[i]

  ans=min(ans,max(b,c,d,e)-min(b,c,d,e))
  #print(left,right)
  #print(b,c,d,e)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
tmp=0
ca=[tmp]
for ai in a:
  tmp+=ai
  ca.append(tmp)
from bisect import bisect_right,bisect_left
ans=float('inf')

# 数列をまず半分に区切る。左i個と右n-i個
for i in range(2,n-1):
  # 左の数列の総和の半分
  tmp=ca[i]/2
  l=bisect_left(ca,tmp)
  r=l-1

  if abs(ca[l]-(ca[i]-ca[l]))<=abs(ca[r]-(ca[i]-ca[r])):
    b,c=ca[l],ca[i]-ca[l]
  else:
    b,c=ca[r],ca[i]-ca[r]

  # 右の数列の総和の半分
  tmp=(ca[-1]+ca[i+1])/2
  l=bisect_left(ca,tmp)
  r=l-1
  if abs(ca[-1]-ca[l]-(ca[l]-ca[i]))<=abs(ca[-1]-ca[r]-(ca[r]-ca[i])):
    d,e=ca[-1]-ca[l],ca[l]-ca[i]
  else:
    d,e=ca[-1]-ca[r],ca[r]-ca[i]
  ans=min(ans,max(b,c,d,e)-min(b,c,d,e))
  #print(left,right)
  #print(b,c,d,e)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
tmp=0
ca=[tmp]
for ai in a:
  tmp+=ai
  ca.append(tmp)
from bisect import bisect_right,bisect_left
ans=float('inf')

# 数列をまず半分に区切る
for i in range(2,n-1):
  left=ca[i]
  right=ca[-1]-ca[i]
  # 左の数列の総和の半分
  tmp=left//2
  l=bisect_left(ca,tmp)
  r=l-1
  if abs(ca[l]-(left-ca[l]))<=abs(ca[r]-(left-ca[r])):
    b,c=ca[l],left-ca[l]
  else:
    b,c=ca[r],left-ca[r]
  # 右の数列の総和の半分
  tmp=(ca[-1]+ca[i+1])//2
  l=bisect_left(ca,tmp)
  r=l-1
  if abs(ca[-1]-ca[l]-(ca[l]-ca[i]))<=abs(ca[-1]-ca[r]-(ca[r]-ca[i])):
    d,e=ca[-1]-ca[l],ca[l]-ca[i]
  else:
    d,e=ca[-1]-ca[r],ca[r]-ca[i]
  ans=min(ans,max(b,c,d,e)-min(b,c,d,e))
  #print(left,right)
  #print(b,c,d,e)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    """
    まず２分して左右をさらにそれぞれ２分するときこれらはなるべく差が小さい方がよさそう
    """
    # m = 1で切った時で初期化
    s = sum(A[2:])
    partial_s = 0
    init_r = N - 2
    for r in range(2, N - 1):
        partial_s += A[r]
        if partial_s * 2 > s:
            init_r = r
            break
    l = 0
    r = init_r
    sums = [A[0], A[1], partial_s, s - partial_s]
    ans = max(sums) - min(sums)
    temp = [sums[0], sums[1], sums[2] - A[r], sums[3] + A[r]]
    ans = min(ans, max(temp) - min(temp))
    #print("l={}, m=1, r={}, sums={}, ans={}".format(l, r, sums, ans))


    # m >= 2で動かしたとき
    for m in range(2, N - 2):
        # lの移動
        sums[1] += A[m]
        while sums[0] <= sums[1] and l < m - 1:
            l += 1
            sums[0] += A[l]
            sums[1] -= A[l]
        # rの移動
        sums[2] -= A[m]
        while sums[2] <= sums[3] and r < N - 2:
            r += 1
            sums[2] += A[r]
            sums[3] -= A[r]
        # ansの更新
        ans = min(ans, max(temp) - min(temp))
        temp = [sums[0] - A[l], sums[1] + A[l], sums[2], sums[3]]
        ans = min(ans, max(temp) - min(temp))
        temp = [sums[0], sums[1], sums[2] - A[r], sums[3] + A[r]]
        ans = min(ans, max(temp) - min(temp))
        temp = [sums[0] - A[l], sums[1] + A[l], sums[2] - A[r], sums[3] + A[r]]
        ans = min(ans, max(temp) - min(temp))
        #print("l={}, m={}, r={}, sums={}, ans={}".format(l, m, r, sums, ans))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    """
    まず２分して左右をさらにそれぞれ２分するときこれらはなるべく差が小さい方がよさそう
    """
    # m = 1で切った時で初期化
    s = sum(A[2:])
    partial_s = 0
    init_r = 2
    for r in range(2, N - 1):
        partial_s += A[r]
        if partial_s * 2 > s:
            init_r = r
            break
    l = 0
    r = max(2, init_r)
    sums = [A[0], A[1], partial_s, s - partial_s]
    ans = max(sums) - min(sums)
    temp = [sums[0], sums[1], sums[2] - A[r], sums[3] + A[r]]
    ans = min(ans, max(temp) - min(temp))
    #print("l={}, m=1, r={}, sums={}, ans={}".format(l, r, sums, ans))


    # m >= 2で動かしたとき
    for m in range(2, N - 2):
        # lの移動
        sums[1] += A[m]
        while sums[0] <= sums[1] and l < m - 1:
            l += 1
            sums[0] += A[l]
            sums[1] -= A[l]
        # rの移動
        sums[2] -= A[m]
        while sums[2] <= sums[3] and r < N - 2:
            r += 1
            sums[2] += A[r]
            sums[3] -= A[r]
        # ansの更新
        ans = min(ans, max(temp) - min(temp))
        temp = [sums[0] - A[l], sums[1] + A[l], sums[2], sums[3]]
        ans = min(ans, max(temp) - min(temp))
        temp = [sums[0], sums[1], sums[2] - A[r], sums[3] + A[r]]
        ans = min(ans, max(temp) - min(temp))
        temp = [sums[0] - A[l], sums[1] + A[l], sums[2] - A[r], sums[3] + A[r]]
        ans = min(ans, max(temp) - min(temp))
        #print("l={}, m={}, r={}, sums={}, ans={}".format(l, m, r, sums, ans))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    """
    まず２分して左右をさらにそれぞれ２分するときこれらはなるべく差が小さい方がよさそう
    """
    # m = 1で切った時で初期化
    s = sum(A[2:])
    partial_s = 0
    init_r = 2
    for r in range(2, N - 1):
        partial_s += A[r]
        if partial_s * 2 > s:
            init_r = r
            break
    l = 0
    r = max(2, init_r)
    sums = [A[0], A[1], partial_s, s - partial_s]
    ans = max(sums) - min(sums)
    temp = [sums[0], sums[1], sums[2] - A[r], sums[3] + A[r]]
    ans = min(ans, max(temp) - min(temp))
    #print("l={}, m=1, r={}, sums={}, ans={}".format(l, r, sums, ans))


    # m >= 2で動かしたとき
    for m in range(2, N - 2):
        # lの移動
        sums[1] += A[m]
        while sums[0] <= sums[1] and l < m:
            l += 1
            sums[0] += A[l]
            sums[1] -= A[l]
        # rの移動
        sums[2] -= A[m]
        while sums[2] <= sums[3] and r < N - 2:
            r += 1
            sums[2] += A[r]
            sums[3] -= A[r]
        # ansの更新
        ans = min(ans, max(temp) - min(temp))
        temp = [sums[0] - A[l], sums[1] + A[l], sums[2], sums[3]]
        ans = min(ans, max(temp) - min(temp))
        temp = [sums[0], sums[1], sums[2] - A[r], sums[3] + A[r]]
        ans = min(ans, max(temp) - min(temp))
        temp = [sums[0] - A[l], sums[1] + A[l], sums[2] - A[r], sums[3] + A[r]]
        ans = min(ans, max(temp) - min(temp))
        #print("l={}, m={}, r={}, sums={}, ans={}".format(l, m, r, sums, ans))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    answer = pow(10, 10)
    for i in range(1, N-1):
        g1 = 0
        g2 = 0
        g1s = math.floor(D[i]/B[i])
        g1l = math.ceil(D[i]/B[i])
        g2s = math.floor((D[-1]-D[i])/(B[-1]-B[i]))
        g2l = math.ceil((D[-1]-D[i])/(B[-1]-B[i]))
        if abs(B[i]-2*B[g1s]) < abs(B[i]-2*B[g1l]):
            g1 = g1s
        else:
            g1 = g1l
        if abs(B[-1]-B[g2s] - (B[g2s]-B[i])) < abs(B[-1]-B[g2l] - (B[g2l]-B[i])):
            g2 = g2s
        else:
            g2 = g2l
        m = min(B[g1], B[i]-B[g1], B[g2]-B[i], B[-1]-B[g2])
        M = max(B[g1], B[i]-B[g1], B[g2]-B[i], B[-1]-B[g2])
        answer = min(answer, M-m)
    print(answer)

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

Submission status: Wrong Answer

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

    answer = pow(10, 10)
    for i in range(1, N-2):
        g1 = 0
        g2 = 0
        g1s = math.floor(D[i]/B[i])
        g1l = math.ceil(D[i]/B[i])
        g2s = math.floor((D[-1]-D[i])/(B[-1]-B[i]))
        g2l = math.ceil((D[-1]-D[i])/(B[-1]-B[i]))
        if abs(B[i]-2*B[g1s]) < abs(B[i]-2*B[g1l]):
            g1 = g1s
        else:
            g1 = g1l
        if abs(B[-1]-B[g2s] - (B[g2s]-B[i])) < abs(B[-1]-B[g2l] - (B[g2l]-B[i])):
            g2 = g2s
        else:
            g2 = g2l
        m = min(B[g1], B[i]-B[g1], B[g2]-B[i], B[-1]-B[g2])
        M = max(B[g1], B[i]-B[g1], B[g2]-B[i], B[-1]-B[g2])
        answer = min(answer, M-m)
    print(answer)

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

Submission status: Wrong Answer

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]/B[g])
    g2 = math.floor((D[-1]-D[g])/(B[-1]-B[g]))

    answer = pow(10, 10)
    for i in range(1, N-2):
        g1 = math.floor(D[i]/B[i])
        g2 = math.floor(((D[-1]-D[i])/(B[-1]-B[i])))
        m = min(B[g1], B[i]-B[g1], B[g2]-B[i], B[-1]-B[g2])
        M = max(B[g1], B[i]-B[g1], B[g2]-B[i], B[-1]-B[g2])
        answer = min(answer, M-m)

    print(answer)

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

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]"):
    cums = [0]
    for v in A:
        cums.append(cums[-1] + v)

    ret = float('inf')
    i, j, k = 1, 2, 3
    while j < N - 1:
        lm = cums[j]
        while i < j and cums[i] < lm / 2:
            i += 1
        if abs(lm - 2 * cums[i]) > abs(lm - 2 * cums[i - 1]):
            i -= 1

        rm = cums[N] - cums[j]
        while k < N and cums[k] - cums[j] < rm / 2:
            k += 1
        if k > j and abs(rm - 2 * (cums[k] - cums[j])) > abs(lm - 2 * (cums[k - 1] - cums[j])):
            k -= 1

        a, b, c, d = cums[i], cums[j] - cums[i], cums[k] - cums[j], cums[N] - cums[k]
        tmp = max(a, b, c, d) - min(a, b, c, d)
        ret = min(ret, tmp)
        j += 1
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]"):
    cums = [0]
    for v in A:
        cums.append(cums[-1] + v)

    ret = float('inf')
    i, j, k = 1, 2, 3
    while j < N - 1:
        lm = cums[j]
        while i < j - 1 and cums[i] < lm / 2:
            i += 1
        if i > 2 and abs(lm - 2 * cums[i]) > abs(lm - 2 * cums[i - 1]):
            i -= 1

        rm = cums[N] - cums[j]
        while k < N - 1 and cums[k] - cums[j] < rm / 2:
            k += 1
        if k > j + 1 and abs(rm - 2 * (cums[k] - cums[j])) > abs(lm - 2 * (cums[k - 1] - cums[j])):
            k -= 1

        a, b, c, d = cums[i], cums[j] - cums[i], cums[k] - cums[j], cums[N] - cums[k]
        tmp = max(a, b, c, d) - min(a, b, c, d)
        ret = min(ret, tmp)
        j += 1
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()