Problem:


Score : 600 points

Problem Statement

Snuke has an integer sequence A of length N.

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

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

Constraints

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

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

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

Sample Input 1

5
3 2 4 1 2

Sample Output 1

2

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

Sample Input 2

10
10 71 84 33 6 47 23 25 52 64

Sample Output 2

36

Sample Input 3

7
1 2 3 1000000000 4 5 6

Sample Output 3

999999994



Sample input:
5
3 2 4 1 2


Sample output:
2

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=float('inf')
tmp=0
ca=[tmp]
for x in a:
  tmp+=x
  ca.append(tmp)
from bisect import bisect_left as bl
for i in range(2,n-1):
  bc=ca[:i+1]
  de=ca[i+1:]
  #de=[0]+[x-ca[i] for x in de]
  sumbc=bc[-1]
  bcidx=bl(bc,sumbc//2)
  p=bc[bcidx]
  q=bc[-1]-bc[bcidx]
  if bcidx>1:
    np=bc[bcidx-1]
    nq=bc[-1]-bc[bcidx-1]
    if abs(p-q)>abs(np-nq):p,q=np,nq

  sumde=de[-1]-bc[-1]
  deidx=bl(de,bc[-1]+sumde//2)
  r=de[deidx]-bc[-1]
  s=de[-1]-de[deidx]
  if deidx>1:
    nr=de[deidx-1]-bc[-1]
    ns=de[-1]-de[deidx-1]
    if abs(r-s)>abs(nr-ns):r,s=nr,ns
  ans=min(ans,max(p,q,r,s)-min(p,q,r,s))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

csum = list(accumulate(As, initial=0))

P_end = 1
R_end = 3
ans = 10 ** 18
for Q_end in range(2, N - 1):
    former_half = csum[Q_end] // 2
    latter_half = (csum[-1] - csum[Q_end]) // 2
    while P_end + 1 <= Q_end and csum[P_end + 1] < former_half:
        P_end += 1
    while R_end + 1 < N and csum[R_end + 1] - csum[Q_end] < latter_half:
        R_end += 1
    
    if abs(csum[P_end] - former_half) > abs(csum[P_end + 1] - former_half):
        P = csum[P_end + 1]
    else:
        P = csum[P_end]
    Q = csum[Q_end] - P

    if abs(csum[R_end] - csum[Q_end] - latter_half) > abs(csum[R_end + 1] - csum[Q_end] - latter_half):
        R = csum[R_end + 1] - csum[Q_end]
        S = csum[-1] - csum[R_end + 1]
    else:
        R = csum[R_end] - csum[Q_end]
        S = csum[-1] - csum[R_end]

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

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

csum = list(accumulate(As, initial=0))

P_end = 1
R_end = 3
ans = 1001001001
for Q_end in range(2, N - 1):
    former_half = csum[Q_end] // 2
    latter_half = (csum[-1] - csum[Q_end]) // 2
    while P_end + 1 <= Q_end and csum[P_end + 1] < former_half:
        P_end += 1
    while R_end + 1 < N and csum[R_end + 1] - csum[Q_end] < latter_half:
        R_end += 1
    
    if abs(csum[P_end] - former_half) > abs(csum[P_end + 1] - former_half):
        P = csum[P_end + 1]
    else:
        P = csum[P_end]
    Q = csum[Q_end] - P

    if abs(csum[R_end] - csum[Q_end] - latter_half) > abs(csum[R_end + 1] - csum[Q_end] - latter_half):
        R = csum[R_end + 1] - csum[Q_end]
        S = csum[-1] - csum[R_end + 1]
    else:
        R = csum[R_end] - csum[Q_end]
        S = csum[-1] - csum[R_end]

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

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

csum = list(accumulate(As, initial=0))

P_end = 1
R_end = 3
ans = 1001001001
for Q_end in range(2, N - 1):
    former_half = csum[Q_end] // 2
    latter_half = (csum[-1] - csum[Q_end]) // 2
    while P_end + 1 <= Q_end and csum[P_end + 1] < former_half:
        P_end += 1
    while R_end + 1 < N and csum[R_end + 1] - csum[Q_end] < latter_half:
        R_end += 1
    
    if abs(csum[P_end] - former_half) > abs(csum[P_end + 1] - former_half):
        P = csum[P_end + 1]
    else:
        P = csum[P_end]
    Q = csum[Q_end] - P

    if abs(csum[R_end] - csum[Q_end] - latter_half) > abs(csum[R_end + 1] - csum[Q_end] - latter_half):
        R = csum[R_end + 1] - csum[Q_end]
    else:
        R = csum[R_end] - csum[Q_end]
    S = csum[-1] - csum[R_end]

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

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
ren=[0]*n
ren[0]= A[0]
for i in range(n-1):
    ren[i+1]= ren[i]+ A[i+1]
import bisect as bi
ans=float("inf")
for cen in range(1, n-2):
    maru= ren[cen]
    a=ren[bi.bisect(ren, maru//2)-1]
    b=maru-a
    c=a+A[bi.bisect(ren, maru//2)]
    d=maru-c
    
    e=ren[bi.bisect(ren,(maru+ren[-1])//2)-1]-maru
    f=ren[-1]-e-maru
    g=e+A[bi.bisect(ren,(maru+ren[-1])//2)]
    h=ren[-1]-g-maru

    q=[max(a,b,e,f)-min(a,b,e,f), max(a,b,g,h)-min(a,b,g,h), max(c,d,e,f)-min(c,d,e,f), max(c,d,g,h)-min(c,d,g,h)]
    ans= min(ans, min(q))
    
    #print(ren)
    #if maru==204:
    #  print(a,b,c,d,e,f,g,h)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
from bisect import *
def solve():
  ans = float('inf')
  N = int(input())
  A = list(map(int, input().split()))
  cum = list(accumulate(A))
  for i in range(1,N-2):
    mae = cum[i]
    usiro = cum[-1]-cum[i]
    ind = bisect_right(cum,mae/2)
    mae_max = min(cum[ind+1],mae-cum[ind-1])
    if ind==0:
      mae_max = cum[ind]
    mae_min = mae - mae_max
    ind2 = bisect_right(cum,usiro/2+cum[i])
    usiro_max = min(cum[ind2]-cum[i],cum[-1]-cum[ind2-1])
    if ind2==i+1:
      usiro_max = cum[ind2]-cum[i]
    usiro_min = usiro - usiro_max
    lis = [mae_max,mae_min,usiro_max,usiro_min]
    ans = min(ans,max(lis)-min(lis))
  return ans
print(solve())

Submission status: Wrong Answer

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
from bisect import *
def solve():
  ans = float('inf')
  N = int(input())
  A = list(map(int, input().split()))
  cum = list(accumulate(A))
  for i in range(1,N-2):
    mae = cum[i]
    usiro = cum[-1]-cum[i]
    ind = bisect_right(cum,mae/2)
    mae_max = min(cum[ind+1],mae-cum[ind-1])
    if ind==0:
      mae_max = cum[ind]
    mae_min = mae - mae_max
    ind2 = bisect_right(cum,usiro/2+cum[i])
    usiro_max = min(cum[ind2]-cum[i],cum[-1]-cum[ind2-1])
    if ind2==i+1:
      usiro_max = cum[ind2]-cum[i]
    usiro_min = usiro - usiro_max
    lis = [mae_max,mae_min,usiro_max,usiro_min]
    ans = min([ans,max(lis)-min(lis)])
  return ans
print(solve())

Submission status: Wrong Answer

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
from bisect import *
def solve():
  ans = float('inf')
  N = int(input())
  A = list(map(int, input().split()))
  cum = list(accumulate(A))
  for i in range(1,N-1):
    mae = cum[i]
    usiro = cum[-1]-cum[i]
    ind = bisect_right(cum,mae/2)
    mae_max = min(cum[ind+1],mae-cum[ind-1])
    if ind==0:
      mae_max = cum[ind]
    mae_min = mae - mae_max
    ind2 = bisect_right(cum,usiro/2+cum[i])
    usiro_max = min(cum[ind2]-cum[i],cum[-1]-cum[ind2-1])
    if ind2==i+1:
      usiro_max = cum[ind2]-cum[i]
    usiro_min = usiro - usiro_max
    lis = [mae_max,mae_min,usiro_max,usiro_min]
    ans = min([ans,max(lis)-min(lis)])
  return ans
print(solve())

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
cs = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]

res = sum(a)
for m in range(1, N - 2):
  lsm = cs[m]
  rsm = cs[-1] - cs[m]
  l = bl(cs, lsm / 2)
  l -= l == m
  for i in range(l - 1, l + 2):
    if abs(cs[l] - (cs[m] - cs[l])) > abs(cs[i] - (cs[m] - cs[i])): l = i
  r = bl(cs, rsm // 2 + lsm)
  r -= r == N
  for i in range(r - 1, r + 2):
    if abs(cs[-1] - cs[r] - (cs[r] - cs[m])) > abs(cs[-1] - cs[i] - (cs[i] - cs[m])): r = i
  mx = max(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r])
  mn = min(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r])
  res = min(res, mx - mn)
  #print(l, m, r, res)
print(res)

Submission status: Wrong Answer

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)

# # # # AVL class # # # #

# NOTE multi_mode not well tested 2020-08-02

DBG_TEST_AVL = False
AVL_INF = 10**12

class Node(object):

    def __init__(self, data):
        self.data = data
        self.left_child = None
        self.right_child = None
        self.height = 0


class AVL(object):

    def __init__(self,multi=False):
        self.root = None
        self.multi_mode = multi

    def get_height(self, node):
        if not node:
            return -1
        return node.height

    def get_balance(self, node):
        '''
        返り値が1より大きい場合、左の部分木が重い　→　右回転
        返り値が-1より小さい場合、右の部分木が重い　→　左回転
        '''
        if not node:
            return 0
        return self.get_height(node.left_child) - self.get_height(node.right_child)

    def rotate_right(self, node):
        temp_left_child = node.left_child
        temp_left_right_child = temp_left_child.right_child

        temp_left_child.right_child = node
        node.left_child = temp_left_right_child

        node.height = max(self.get_height(node.left_child), self.get_height(node.right_child)) + 1
        temp_left_child.height = max(self.get_height(temp_left_child.left_child), self.get_height(temp_left_child.right_child)) + 1

        return temp_left_child

    def rotate_left(self, node):
        temp_right_child = node.right_child
        temp_right_left_child = temp_right_child.left_child

        temp_right_child.left_child = node
        node.right_child = temp_right_left_child

        node.height = max(self.get_height(node.left_child), self.get_height(node.right_child)) + 1
        temp_right_child.height = max(self.get_height(temp_right_child.left_child), self.get_height(temp_right_child.right_child)) + 1

        return temp_right_child

    def insert(self, data):
        self.root = self._insert(data, self.root)

    def _insert(self, data, node):
        if not node:
            return Node(data)

        if data < node.data:
            node.left_child = self._insert(data, node.left_child)
        else:
            if not self.multi_mode and data==node.data:
                return node
            node.right_child = self._insert(data, node.right_child)

        node.height = max(self.get_height(node.left_child), self.get_height(node.right_child)) + 1
        return self.settle_unbalance(data, node)

    def settle_unbalance(self, data, node):

        balance = self.get_balance(node)

        # balace >1 -> 左の方が重い
        # data < node.left_child.data 左の子より左側にデータが挿入されたので、左の子の左の子の方が重い
        # つまり、left-left heavy　右回転を行う
        if balance > 1 and data < node.left_child.data:
            return self.rotate_right(node)

        # balace > -1 -> 右の方が重い
        # data > node.right_child.data 右の子より右側にデータが挿入されたので、右の子の右の子の方が重い
        # つまり、right-right heavy　左回転を行う
        if balance < -1 and data > node.right_child.data:
            return self.rotate_left(node)

        # balace >1 -> 左の方が重い
        # data > node.left_child.data 左の子より右側にデータが挿入されたので、左の子の右の子の方が重い
        # つまり、left-right heavy　左回転を行い右回転を行う
        if balance > 1 and data > node.left_child.data:
            node.left_child = self.rotate_left(node.left_child)
            return self.rotate_right(node)

        # balace > -1 -> 右の方が重い
        # data < node.right_child.data 右の子より左側にデータが挿入されたので、右の子の左の子の方が重い
        # つまり、right-left heavy　右回転を行い左回転を行う
        if balance < -1 and data < node.right_child.data:
            node.right_child = self.rotate_right(node.right_child)
            return self.rotate_left(node)

        return node

    def traverse_inorder(self):
        if self.root:
            self._traverse_inorder(self.root)
            # 改行対策
            print()
        else:
            print('木は空です。')

    def _traverse_inorder(self, node):
        if node.left_child:
            self._traverse_inorder(node.left_child)

        print(node.data, end=' ')

        if node.right_child:
            self._traverse_inorder(node.right_child)

    def remove(self, data):
        if self.root:
            self.root = self._remove(data, self.root)

    def _remove(self, data, node):
        # 単体の木の場合
        if not node:
            return node

        if data < node.data:
            node.left_child = self._remove(data, node.left_child)
        elif data > node.data:
            node.right_child = self._remove(data, node.right_child)
        else:
            # 削除ノードが子を持たない場合は、ノードを削除する。
            if not node.right_child and not node.left_child:
                del node
                # None を返すことで、親ノードの削除子ノードへのポインタを None に変更
                return None

            # 削除ノードが左の子だけを持つ場合、ノードを削除し、左の子のノードを返す
            if not node.right_child:
                temp = node.left_child
                del node
                # 左の子のノードを返すことで、親ノードの削除子ノードへのポインタを新しい子ノードに変更
                return temp

            # 削除ノードが右の子だけを持つ場合、左の子だけの場合の逆の操作を行う
            if not node.left_child:
                temp = node.right_child
                del node
                return temp
            # 削除ノードが左右の子を持つ場合、ここでは、左側のsubtreeの最大のノードを代わりのノードにすることにする。
            #  subtreeの最大のノードを取得するヘルパー関数
            def _get_max_node(node):
                if node.right_child:
                    return _get_max_node(node.right_child)
                return node
            temp = _get_max_node(node.left_child)
            node.data = temp.data
            # 左側のsubtreeから削除ノードと入れ替えたノードを削除
            node.left_child = self._remove(temp.data, node.left_child)

        node.height = max(self.get_height(node.left_child), self.get_height(node.right_child)) + 1
        balance = self.get_balance(node)

        if balance > 1 and self.get_balance(node.left_child) >= 0:
            print('left-left heavy')
            return self.rotate_right(node)

        if balance < -1 and self.get_balance(node.left_child) <= 0:
            print('right-right heavy')
            return self.rotate_left(node)

        if balance > 1 and self.get_balance(node.left_child) < 0:
            print('left-right heavy')
            node.left_child = self.rotate_left(node.left_child)
            return self.rotate_right(node)

        if balance < -1 and self.get_balance(node.left_child) > 0:
            node.right_child = self.rotate_right(node.right_child)
            print('right-left heavy')
            return self.rotate_left(node)

        return node

    def find_bounds(self,d):
        return self._find(self.root,d,-AVL_INF,AVL_INF)

    def _find(self,nd,d,l,r):
        if not nd:
            return (l,r)
        elif nd.data==d:
            return (d,d)
        elif nd.data<d:
            return self._find(nd.right_child,d,max(l,nd.data),r)
        else:
            return self._find(nd.left_child,d,l,min(r,nd.data))

#if __name__ == '__main__':
def test_avl_alone():
    avl = AVL()

    avl.insert(2)
    avl.insert(4)
    avl.insert(8)
    avl.insert(16)
    avl.insert(16)
    avl.insert(32)
    avl.insert(64)
    avl.insert(128)
    avl.insert(256)
    avl.insert(512)
    # 2 4 8 16 32 64 128 256 512
    avl.traverse_inorder()
    avl.remove(2)
    # right-right heavy
    avl.remove(4)
    print(avl.find_bounds(3))
    avl.remove(512)
    avl.remove(256)
    # left-left heavy
    avl.remove(64)
    print(avl.find_bounds(37))
    print(avl.find_bounds(128))
    avl.remove(128)
    # 8 16 32
    avl.traverse_inorder()
    # height 1
    print('height', avl.get_height(avl.root))

if DBG_TEST_AVL:
    test_avl_alone()

# # # # AVL class end # # # #


n = inn()
a = inl()
mnl = [0]*n
mnr = [0]*n
mxl = [0]*n
mxr = [0]*n

lacc = a[0]
av = AVL()
av.insert(lacc)
for i in range(1,n-2):
    lacc += a[i]
    r1 = av.find_bounds(lacc//2)
    r2 = av.find_bounds(lacc//2+1)
    mnl[i+1] = max([ \
     min(r1[0],lacc-r1[0]),
     min(r1[1],lacc-r1[1]),
     min(r2[0],lacc-r2[0]),
     min(r2[1],lacc-r2[1]) ])
    mxl[i+1] = min([ \
     max(r1[0],lacc-r1[0]),
     max(r1[1],lacc-r1[1]),
     max(r2[0],lacc-r2[0]),
     max(r2[1],lacc-r2[1]) ])
    av.insert(lacc)

racc = a[n-1]
av = AVL()
av.insert(racc)
for i in range(n-2,1,-1):
    racc += a[i]
    r1 = av.find_bounds(racc//2)
    r2 = av.find_bounds(racc//2+1)
    mnr[i] = max([ \
     min(r1[0],racc-r1[0]),
     min(r1[1],racc-r1[1]),
     min(r2[0],racc-r2[0]),
     min(r2[1],racc-r2[1]) ])
    mxr[i] = min([ \
     max(r1[0],racc-r1[0]),
     max(r1[1],racc-r1[1]),
     max(r2[0],racc-r2[0]),
     max(r2[1],racc-r2[1]) ])
    av.insert(racc)

print(min( \
 [max(mxr[i],mxl[i])-min(mnr[i],mnl[i]) for i in range(2,n-1)]))

Submission status: Wrong Answer

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)

# # # # AVL class # # # #

# NOTE multi_mode not well tested 2020-08-02

DBG_TEST_AVL = False
AVL_INF = 10**12

class Node(object):

    def __init__(self, data):
        self.data = data
        self.left_child = None
        self.right_child = None
        self.height = 0


class AVL(object):

    def __init__(self,multi=False):
        self.root = None
        self.multi_mode = multi

    def get_height(self, node):
        if not node:
            return -1
        return node.height

    def get_balance(self, node):
        '''
        返り値が1より大きい場合、左の部分木が重い　→　右回転
        返り値が-1より小さい場合、右の部分木が重い　→　左回転
        '''
        if not node:
            return 0
        return self.get_height(node.left_child) - self.get_height(node.right_child)

    def rotate_right(self, node):
        temp_left_child = node.left_child
        temp_left_right_child = temp_left_child.right_child

        temp_left_child.right_child = node
        node.left_child = temp_left_right_child

        node.height = max(self.get_height(node.left_child), self.get_height(node.right_child)) + 1
        temp_left_child.height = max(self.get_height(temp_left_child.left_child), self.get_height(temp_left_child.right_child)) + 1

        return temp_left_child

    def rotate_left(self, node):
        temp_right_child = node.right_child
        temp_right_left_child = temp_right_child.left_child

        temp_right_child.left_child = node
        node.right_child = temp_right_left_child

        node.height = max(self.get_height(node.left_child), self.get_height(node.right_child)) + 1
        temp_right_child.height = max(self.get_height(temp_right_child.left_child), self.get_height(temp_right_child.right_child)) + 1

        return temp_right_child

    def insert(self, data):
        self.root = self._insert(data, self.root)

    def _insert(self, data, node):
        if not node:
            return Node(data)

        if data < node.data:
            node.left_child = self._insert(data, node.left_child)
        else:
            if not self.multi_mode and data==node.data:
                return node
            node.right_child = self._insert(data, node.right_child)

        node.height = max(self.get_height(node.left_child), self.get_height(node.right_child)) + 1
        return self.settle_unbalance(data, node)

    def settle_unbalance(self, data, node):

        balance = self.get_balance(node)

        # balace >1 -> 左の方が重い
        # data < node.left_child.data 左の子より左側にデータが挿入されたので、左の子の左の子の方が重い
        # つまり、left-left heavy　右回転を行う
        if balance > 1 and data < node.left_child.data:
            return self.rotate_right(node)

        # balace > -1 -> 右の方が重い
        # data > node.right_child.data 右の子より右側にデータが挿入されたので、右の子の右の子の方が重い
        # つまり、right-right heavy　左回転を行う
        if balance < -1 and data > node.right_child.data:
            return self.rotate_left(node)

        # balace >1 -> 左の方が重い
        # data > node.left_child.data 左の子より右側にデータが挿入されたので、左の子の右の子の方が重い
        # つまり、left-right heavy　左回転を行い右回転を行う
        if balance > 1 and data > node.left_child.data:
            node.left_child = self.rotate_left(node.left_child)
            return self.rotate_right(node)

        # balace > -1 -> 右の方が重い
        # data < node.right_child.data 右の子より左側にデータが挿入されたので、右の子の左の子の方が重い
        # つまり、right-left heavy　右回転を行い左回転を行う
        if balance < -1 and data < node.right_child.data:
            node.right_child = self.rotate_right(node.right_child)
            return self.rotate_left(node)

        return node

    def traverse_inorder(self):
        if self.root:
            self._traverse_inorder(self.root)
            # 改行対策
            print()
        else:
            print('木は空です。')

    def _traverse_inorder(self, node):
        if node.left_child:
            self._traverse_inorder(node.left_child)

        print(node.data, end=' ')

        if node.right_child:
            self._traverse_inorder(node.right_child)

    def remove(self, data):
        if self.root:
            self.root = self._remove(data, self.root)

    def _remove(self, data, node):
        # 単体の木の場合
        if not node:
            return node

        if data < node.data:
            node.left_child = self._remove(data, node.left_child)
        elif data > node.data:
            node.right_child = self._remove(data, node.right_child)
        else:
            # 削除ノードが子を持たない場合は、ノードを削除する。
            if not node.right_child and not node.left_child:
                del node
                # None を返すことで、親ノードの削除子ノードへのポインタを None に変更
                return None

            # 削除ノードが左の子だけを持つ場合、ノードを削除し、左の子のノードを返す
            if not node.right_child:
                temp = node.left_child
                del node
                # 左の子のノードを返すことで、親ノードの削除子ノードへのポインタを新しい子ノードに変更
                return temp

            # 削除ノードが右の子だけを持つ場合、左の子だけの場合の逆の操作を行う
            if not node.left_child:
                temp = node.right_child
                del node
                return temp
            # 削除ノードが左右の子を持つ場合、ここでは、左側のsubtreeの最大のノードを代わりのノードにすることにする。
            #  subtreeの最大のノードを取得するヘルパー関数
            def _get_max_node(node):
                if node.right_child:
                    return _get_max_node(node.right_child)
                return node
            temp = _get_max_node(node.left_child)
            node.data = temp.data
            # 左側のsubtreeから削除ノードと入れ替えたノードを削除
            node.left_child = self._remove(temp.data, node.left_child)

        node.height = max(self.get_height(node.left_child), self.get_height(node.right_child)) + 1
        balance = self.get_balance(node)

        if balance > 1 and self.get_balance(node.left_child) >= 0:
            print('left-left heavy')
            return self.rotate_right(node)

        if balance < -1 and self.get_balance(node.left_child) <= 0:
            print('right-right heavy')
            return self.rotate_left(node)

        if balance > 1 and self.get_balance(node.left_child) < 0:
            print('left-right heavy')
            node.left_child = self.rotate_left(node.left_child)
            return self.rotate_right(node)

        if balance < -1 and self.get_balance(node.left_child) > 0:
            node.right_child = self.rotate_right(node.right_child)
            print('right-left heavy')
            return self.rotate_left(node)

        return node

    def find_bounds(self,d):
        return self._find(self.root,d,-AVL_INF,AVL_INF)

    def _find(self,nd,d,l,r):
        if not nd:
            return (l,r)
        elif nd.data==d:
            return (d,d)
        elif nd.data<d:
            return self._find(nd.right_child,d,max(l,nd.data),r)
        else:
            return self._find(nd.left_child,d,l,min(r,nd.data))

#if __name__ == '__main__':
def test_avl_alone():
    avl = AVL()

    avl.insert(2)
    avl.insert(4)
    avl.insert(8)
    avl.insert(16)
    avl.insert(16)
    avl.insert(32)
    avl.insert(64)
    avl.insert(128)
    avl.insert(256)
    avl.insert(512)
    # 2 4 8 16 32 64 128 256 512
    avl.traverse_inorder()
    avl.remove(2)
    # right-right heavy
    avl.remove(4)
    print(avl.find_bounds(3))
    avl.remove(512)
    avl.remove(256)
    # left-left heavy
    avl.remove(64)
    print(avl.find_bounds(37))
    print(avl.find_bounds(128))
    avl.remove(128)
    # 8 16 32
    avl.traverse_inorder()
    # height 1
    print('height', avl.get_height(avl.root))

if DBG_TEST_AVL:
    test_avl_alone()

# # # # AVL class end # # # #


n = inn()
a = inl()
mnl = [0]*n
mnr = [0]*n
mxl = [0]*n
mxr = [0]*n

lacc = a[0]
av = AVL()
av.insert(lacc)
for i in range(1,n-1):
    lacc += a[i]
    r1 = av.find_bounds(lacc//2)
    r2 = av.find_bounds(lacc//2+1)
    mnl[i+1] = max([ \
     min(r1[0],lacc-r1[0]),
     min(r1[1],lacc-r1[1]),
     min(r2[0],lacc-r2[0]),
     min(r2[1],lacc-r2[1]) ])
    mxl[i+1] = min([ \
     max(r1[0],lacc-r1[0]),
     max(r1[1],lacc-r1[1]),
     max(r2[0],lacc-r2[0]),
     max(r2[1],lacc-r2[1]) ])
    av.insert(lacc)

racc = a[n-1]
av = AVL()
av.insert(racc)
for i in range(n-2,1,-1):
    racc += a[i]
    r1 = av.find_bounds(racc//2)
    r2 = av.find_bounds(racc//2+1)
    mnr[i] = max([ \
     min(r1[0],racc-r1[0]),
     min(r1[1],racc-r1[1]),
     min(r2[0],racc-r2[0]),
     min(r2[1],racc-r2[1]) ])
    mxr[i] = min([ \
     max(r1[0],racc-r1[0]),
     max(r1[1],racc-r1[1]),
     max(r2[0],racc-r2[0]),
     max(r2[1],racc-r2[1]) ])
    av.insert(racc)

print(min( \
 [max(mxr[i],mxl[i])-min(mnr[i],mnl[i]) for i in range(2,n-1)]))

Submission status: Wrong Answer

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()
cms = itertools.combinations(list(range(1,20)),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: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect_left, bisect_right

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

csum = list(accumulate(As, initial = 0))

#find lower_bound
l = 1
r = 10 ** 9 + 10
while r - l > 1:
    mid = (l + r) // 2
    PQRS_sum = 0
    for i in range(4):
        index = bisect_left(csum,  PQRS_sum + mid)
        if index == N+1:
            r = mid
            break
        PQRS_sum = csum[index]
    else:
        l = mid

lower_bound = l

#find upper_bound
l = 1
r = 10 ** 9 + 10
while r - l > 1:
    mid = (l + r) // 2
    PQRS_sum = 0
    for i in range(4):
        index = bisect_right(csum,  PQRS_sum + mid) - 1
        if index == N:
            r = mid
            break
        PQRS_sum = csum[index]
    else:
        l = mid

upper_bound = r

print(upper_bound - lower_bound)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect_left, bisect_right

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

csum = list(accumulate(As, initial = 0))

#Let T = sum(As) / 4
#You can easily find best (P, Q, R, S) if you know whether each one is larger or smaller than T.

T = csum[-1] / 4
ans = 10 ** 9 + 10
for cond in range(8):
    PQRS = [0] * 4
    for i in range(3):
        if cond & (1 << i): #PQRS[i] >= T
            index = bisect_left(csum,  sum(PQRS)+T) #This works even if i == 0.
            if index == N+1:
                break
            PQRS[i] = csum[index] - sum(PQRS)
        else:
            index = bisect_left(csum, sum(PQRS)+T) - 1
            PQRS[i] = csum[index] - sum(PQRS)
    else:
        PQRS[-1] = csum[-1] - sum(PQRS)
        if 0 not in PQRS:
            ans = min(ans, max(PQRS) - min(PQRS))

if ans != 10 ** 9 + 10:
    print(ans)
else:
    max_A = max(As)
    if max_A > T:
        l = 1
        r = 10 ** 9 + 10
        while r - l > 1:
            mid = (l + r) // 2
            PQRS = [0] * 4
            for i in range(4):
                index = bisect_left(csum,  sum(PQRS)+mid) #This works even if i == 0.
                if index == N+1:
                    r = mid
                    break
                PQRS[i] = csum[index] - sum(PQRS)
            else:
                if max(PQRS) == max_A:
                    l = mid
                else:
                    r = mid
        print(max_A - l)
    else:
        raise ValueError

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect_left, bisect_right

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

csum = list(accumulate(As, initial = 0))

#Let T = sum(As) / 4
#You can easily find best (P, Q, R, S) if you know whether each one is larger or smaller than T.

T = csum[-1] / 4
ans = 10 ** 9 + 10
for cond in range(8):
    PQRS = [0] * 4
    for i in range(3):
        if cond & (1 << i): #PQRS[i] >= T
            index = bisect_left(csum,  sum(PQRS)+T) #This works even if i == 0.
            if index == N+1:
                break
            PQRS[i] = csum[index] - sum(PQRS)
        else:
            index = bisect_left(csum, sum(PQRS)+T) - 1
            PQRS[i] = csum[index] - sum(PQRS)
    else:
        PQRS[-1] = csum[-1] - sum(PQRS)
        if 0 not in PQRS:
            ans = min(ans, max(PQRS) - min(PQRS))

if ans != 10 ** 9 + 10:
    print(ans)
else:
    if max(As) > T:
        l = 1
        r = 10 ** 9 + 10
        while r - l > 1:
            mid = (l + r) // 2
            PQRS = [0] * 4
            for i in range(4):
                index = bisect_left(csum,  sum(PQRS)+mid) #This works even if i == 0.
                if index == N+1:
                    r = mid
                    break
                PQRS[i] = csum[index] - sum(PQRS)
            else:
                l = mid
        print(max(As) - l)
    else:
        raise ValueError