TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: 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.

Submission attempts (in order):
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):
  
  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)


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


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


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


Verdicts: Wrong Answer

Wrong Answer

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

Submission attempts (in order):
import sys
input = sys.stdin.readline
import numpy as np

N = int(input())
A = np.array(input().split(), np.int64)
A_cum = [0] + np.cumsum(A)

ans = 10**10
l = 0
r = 2
for i in range(1, N - 1):
    while A[l] < A[i] - A[l + 1]:
        l += 1
    while A[r] - A[i] < A[-1] - A[r + 1]:
        r += 1
    P = A[l]
    Q = A[i] - A[l]
    R = A[r] - A[i]
    S = A[-1] - A[r]
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    ans = min(ans, tmp)
print(ans)


import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
S = [0]
for a in A:
    S += [S[-1] + a]

ans = float("inf")
l = 0
r = 2
for i in range(1, N - 1):
    while S[l] < S[i] - S[l + 1]:
        l += 1
    while S[r] - S[i] < S[N] - S[r + 1]:
        r += 1

    a = S[l]
    b = S[i] - S[l]
    c = S[r] - S[i]
    d = S[N] - S[r]

    ans = min(ans, max(a, b, c, d) - min(a, b, c, d))
print(ans)

Verdicts: Runtime Error

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

Submission attempts (in order):
#!/usr/bin/env python
from itertools import accumulate as ac
N = int(input())
A = list(ac(map(int, input().split())))
l, r, t = 0, 2, A[-1]
c = t
print(A)
print(A[1:-2])
for m in A[1:-2]:
    while t+m > A[r]+A[r+1]:
        r += 1
    while m > A[l]+A[l+1]:
        l += 1
    x = sorted([A[l],m-A[l],A[r]-m,t-A[r]])
    c = min(c,x[-1]-x[0])
print(c)


#!/usr/bin/env python
from itertools import accumulate as ac
N = int(input())
A = list(ac(map(int, input().split())))
l, r, t = 0, 2, A[-1]
c = t

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


Verdicts: Wrong Answer

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

Submission attempts (in order):
from itertools import accumulate
from bisect import bisect_left

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

ans = float("inf")

for j in range(2,n-1):
    i_list = []
    i_left = bisect_left(s, s[j-1]//2)-1
    if i_left != -1:
        i_list.append([s[i_left], s[j-1]-s[i_left]])
    if i_left != j-2:
        i_list.append([s[i_left+1], s[j-1]-s[i_left+1]])

    k_list = []
    k_left = bisect_left(s, s[j-1]+(s[-1]-s[j-1])//2)-1
    if k_left != j-1:
        k_list.append([s[k_left] - s[j-1], s[-1]-s[k_left]])
    if k_left != n-2:
        k_list.append([s[k_left+1] - s[j-1], s[-1]-s[k_left+1]])
    for i in i_list:
        for k in k_list:
            tmp = max(i+k)-min(i+k)
            ans = min(ans, tmp)


from itertools import accumulate
from bisect import bisect_left

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

ans = float("inf")

for j in range(2,n-1):
    i_list = []
    i_left = bisect_left(s, s[j-1]//2)-1
    if i_left != -1:
        i_list.append([s[i_left], s[j-1]-s[i_left]])
    if i_left != j-2:
        i_list.append([s[i_left+1], s[j-1]-s[i_left+1]])

    k_list = []
    k_left = bisect_left(s, s[j-1]+(s[-1]-s[j-1])//2)-1
    if k_left != j-1:
        k_list.append([s[k_left] - s[j-1], s[-1]-s[k_left]])
    if k_left != n-2:
        k_list.append([s[k_left+1] - s[j-1], s[-1]-s[k_left+1]])
    for i in i_list:
        for k in k_list:
            tmp = max(i+k)-min(i+k)
            ans = min(ans, tmp)
print(ans)

Verdicts: Wrong Answer

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

Submission attempts (in order):
# coding: utf-8

from itertools import accumulate

def getAccumulate(A):
    return list(accumulate(A))

def solve(A):
    accum = getAccumulate(A)
    l_index = 0
    r_index = 2
    accum_max = accum[-1]

    diff = accum_max
    for i in range(1, len(A)-2):
        while accum[i] > accum[l_index] + accum[l_index + 1]:
            l_index += 1
        while accum_max + accum[i] > accum[r_index] + accum[r_index + 1]:
            r_index += 1
        
        print(i)
        print(accum)
        left = accum[l_index]
        center = accum[i] - accum[l_index]
        right = accum[r_index] - accum[i]
        last = accum_max - accum[r_index]
        print(accum[l_index], accum[i], accum[r_index], accum[-1])
        diff = min(diff, max(left, center, right, last) - min(left, center, right, last))
        
    return diff

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
	print(solve(A))


# coding: utf-8

from itertools import accumulate

def getAccumulate(A):
    return list(accumulate(A))

def solve(A):
    accum = getAccumulate(A)
    l_index = 0
    r_index = 2
    accum_max = accum[-1]

    diff = accum_max
    for i in range(1, len(A)-2):
        while accum[i] > accum[l_index] + accum[l_index + 1]:
            l_index += 1
        while accum_max + accum[i] > accum[r_index] + accum[r_index + 1]:
            r_index += 1
        
        left = accum[l_index]
        center = accum[i] - accum[l_index]
        right = accum[r_index] - accum[i]
        last = accum_max - accum[r_index]
        diff = min(diff, max(left, center, right, last) - min(left, center, right, last))
        
    return diff

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    print(solve(A))



Verdicts: Runtime Error

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

Submission attempts (in order):
import bisect
n = int(input())
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + a[i]
cum.append(10**10)
mincost = 10 ** 10
#print(cum)
for mid in range(2,n-1):
    ll = bisect.bisect_left(cum[:mid], cum[mid]//2)
    rl = bisect.bisect_left(cum[mid:], cum[mid+1] + (cum[n] - cum[mid+1])//2) + mid
    s = [0] * 4
    for i in range(4):
        s[0] = cum[ll - (i&1)]
        s[1] = cum[mid] - cum[ll - (i&1)]
        s[2] = cum[rl - (i&2 >> 1)] - cum[mid]
        s[3] = cum[n] - cum[rl - (i&2 >> 1)]
#        print(ll - (i&1), mid, rl - (i&2 >> 1), s)
        mincost = min(mincost, max(s) - min(s))
print(mincost)


n = int(input())
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + a[i]
llsum = a[0]
lrsum = a[1]
l = [0] * n
l[2] = 1
for mid in range(3, n-1):
    new = a[mid-1]
    lrsum += new
    l[mid] = l[mid-1]
    unk = a[l[mid]]
    while(abs(lrsum - llsum) > abs(lrsum - llsum - 2 * unk)):
        llsum += unk
        lrsum -= unk
        l[mid] += 1
        unk = a[l[mid]]
rrsum = a[n-1]
rlsum = a[n-2]
r = [0] * n
r[n-2] = n-1
for mid in reversed(range(2, n-2)):
    new = a[mid]
    rlsum += new
    r[mid] = r[mid+1]
    unk = a[r[mid] - 1]
    while(abs(rlsum - rrsum) > abs(rlsum - rrsum - 2 * unk)):
        rrsum += unk
        rlsum -= unk
        r[mid] -= 1
        unk = a[r[mid] - 1]
minabs = 10 ** 20
for mid in range(2, n-1):
    c0 = cum[l[mid]]
    c1 = cum[mid]
    c2 = cum[r[mid]]
    sums = (c0, c1 - c0, c2 - c1, cum[n] - c2)
    minabs = min(minabs, max(sums) - min(sums))
print(minabs)


Verdicts: Wrong Answer

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

Submission attempts (in order):
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)

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]
    if a==ren[-1]: a=float("inf")
    b=maru-a
    c=ren[bi.bisect(ren, maru//2)]
    if c==maru: c=float("inf")
    d=maru-c
    
    e=ren[bi.bisect(ren,(maru+ren[-1])//2)-1]-maru 
    if e==0: e= float("inf")
    f=ren[-1]-e-maru
    g=ren[bi.bisect(ren,(maru+ren[-1])//2)]-maru
    if g==ren[-1]-maru: g=float("INF")
    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)
    
    #print(a,b,c,d,e,f,g,h)
print(ans)

Verdicts: Wrong Answer

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

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

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

Verdicts: Runtime Error

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

Submission attempts (in order):
from itertools import accumulate


from bisect import bisect_right, bisect_left

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


cumsum = list(accumulate(A))
cumsum.insert(0, 0)  


ans = float('inf')

for i in range(2, N-1):  
    
    Lmid = cumsum[i] / 2
    
    
    Lx = bisect_left(cumsum, Lx)
    
    
    
    if abs(cumsum[Lx-1] - Lmid) < abs(cumsum[Lx] - Lmid):
        Lmid -= 1


    
    Rmid = (cumsum[N] + cumsum[i]) / 2  
    Rx = bisect_left(cumsum, Rmid)
    
    if abs(cumsum[Rx-1] - Rmid) < abs(cumsum[Rx] - Rmid):
        Rx -= 1
    
    
    
    P = cumsum[Lx]
    
    
    Q = cumsum[i]-cumsum[Lx]
    
    
    R = cumsum[Rx]-cumsum[i]
    
    
    S = cumsum[N]-cumsum[Rx]
    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))

print(ans)


from itertools import accumulate
from bisect import bisect_left

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

P = list(accumulate(A))
P.insert(0, 0)

ans = float('inf')
for i in range(2, N-1):
    
    Lmid = P[i] / 2
    Lx = bisect_left(P, Lmid)
    if abs(P[Lx] - Lmid) > abs(P[Lx-1] - Lmid):
        Lx -= 1

    
    Rmid = (P[i] + P[N]) / 2
    Rx = bisect_left(P, Rmid)
    if abs(P[Rx] - Rmid) > abs(P[Rx-1] - Rmid):
        Rx -= 1

    M = max(P[Lx], P[i]-P[Lx], P[Rx]-P[i], P[N]-P[Rx])
    m = min(P[Lx], P[i]-P[Lx], P[Rx]-P[i], P[N]-P[Rx])

    ans = min(ans, M-m)

print(ans)


Verdicts: Runtime Error

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

Submission attempts (in order):
from bisect import bisect_left as bl
from itertools import accumulate
INF = 10 ** 20

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

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

ans = INF
for i in range(2, n - 1):
  p, q = get_score(acc, 1, i)
  r, s = get_score(acc, i + 1, n)
  if not None in (p, q, r, s):
    ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
print(ans)

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

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

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

ans = INF
for i in range(2, n - 1):
  p, q = get_score(acc, 1, i)
  r, s = get_score(acc, i + 1, n)
  if not None in (p, q, r, s):
    ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
print(ans)

Verdicts: Wrong Answer

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

Submission attempts (in order):
N = int(input())
A = list(map(int,input().split()))
from bisect import bisect_left


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

Ans = 10**15

for i in range(2,N-1):
    
    A,B = S[:i],S[i:]
    sumA,sumB = S[i-1],S[N-1]-S[i-1]
    canA,canB = [],[]
    
    ai = bisect_left(A,sumA/2)
    bi = bisect_left(B,sumB/2+A[-1])
    
    x1,x2,x3,x4 = 0,0,0,0
    a0,a1 = A[ai],A[ai-1]
    a2 = A[i-1]
    b0,b1 = B[bi],B[bi-1]
    b2 = B[-1]
    if abs(a0-sumA/2) < abs(a1-sumA/2):
        x1,x2 = a0,a2
    else:
        x1,x2 = a1,a2    
    if abs(b0-(sumB/2+A[-1])) > abs(b1-(sumB/2+A[-1])):
        x3,x4 = b0,b2
    else:
        x3,x4 = b1,b2
    
    Ans = min(Ans,max(x1,x2-x1,x3-x2,x4-x3)-min(x1,x2-x1,x3-x2,x4-x3))

print(Ans)

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


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

Ans = 10**15

for i in range(2,N-1):
    
    ax = S[i-1]/2
    ai = bisect(S,ax)
    if abs(S[ai-1]-ax) < abs(S[ai]-ax):
        ai -= 1
    bx = (S[N-1]+S[i-1])/2
    bi = bisect(S,bx)
    if abs(S[bi-1]-bx) < abs(S[bi]-bx):
        bi -= 1
    x1,x2,x3,x4 = S[ai],S[i-1]-S[ai],S[bi]-S[i-1],S[N-1]-S[bi]
    
    Ans = min(Ans,max(x1,x2,x3,x4)-min(x1,x2,x3,x4))

print(Ans)

Verdicts: Wrong Answer

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

Submission attempts (in order):
import bisect

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

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

ans = 1e18
for i in range(2, N-1):
    left = S[:i]
    m = bisect.bisect(left, left[-1]//2)

    if m == 0:
        L = [left[0], left[-1]-left[0]]
    else:
        L = [left[m], left[-1]-left[m]]
        L2 = [left[m-1], left[-1]-left[m-1]]

        if(abs(L[0]-L[1]) > abs(L2[0]-L2[1])): L = L2

    right = S[i:]
    m = bisect.bisect(right, (right[-1]+left[-1])//2)
    if m == 0:
        R = [right[0]-left[-1], right[-1]-right[0]]
    else:
        R = [right[m]-left[-1], right[-1]-right[m]]
        R2 = [right[m-1]-left[-1], right[-1]-right[m-1]]

        if(abs(R[0]-R[1]) > abs(R2[0]-R2[1])): R = R2

    print(L, end="")
    print(R)

    ans = min(ans, max(L[0],L[1],R[0],R[1]) - min(L[0],L[1],R[0],R[1]))

print(ans)

import bisect

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

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

ans = 1e18
for i in range(2, N-1):
    
    left_sum = S[i-1]
    m = bisect.bisect(S, left_sum/2)

    L = [S[m], left_sum-S[m]]

    if m != 0:
        L2 = [S[m-1], left_sum - S[m-1]]
        if(abs(L[0]-L[1]) > abs(L2[0]-L2[1])): L = L2

    
    m = bisect.bisect(S, (S[-1]+left_sum)/2)
    R = [S[m]-left_sum, S[-1]-S[m]]

    if m != i:
        R2 = [S[m-1]-left_sum, S[-1]-S[m-1]]
        if(abs(R[0]-R[1]) > abs(R2[0]-R2[1])): R = R2


    ans = min(ans, max(L[0],L[1],R[0],R[1]) - min(L[0],L[1],R[0],R[1]))

print(ans)


Verdicts: Wrong Answer

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

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

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

Verdicts: Runtime Error

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

Submission attempts (in order):
N=int(input())
A=list(map(int,input().split()))
from itertools import accumulate
C=list(accumulate(A))
from bisect import bisect_left
x=bisect_left(C,C[-1]//2)
r=10**16
for i in range(x-2,x+3):
    if not 1<i<N-1:continue
    D=10**16
    for j in range(i):
        if abs(C[i-1]-C[j]*2)<D:
            a,b=C[j],C[i-1]-C[j]
            D=abs(a-b)
    D=10**16
    for k in range(i,N):
        if abs(C[N-1]-C[k]*2+C[i-1])<D:
            c,d=C[k]-C[i-1],C[N-1]-C[k]
            D=abs(c-d)
    print(i,a,b,c,d)
    r=min(r,max(a,b,c,d)-min(a,b,c,d))
print(r)

N=int(input())
A=list(map(int,input().split()))
from itertools import accumulate
C=[0]+list(accumulate(A))
l,r=1,3
x=10**16
for m in range(2,N-1):
    a,b,c,d=C[l],C[m]-C[l],C[r]-C[m],C[N]-C[r]
    while l<m-1 and abs(C[m]-C[l+1]*2)<abs(a-b):
        l+=1
        a,b=C[l],C[m]-C[l]
    while r<N-1 and abs(C[N]-C[r+1]*2+C[m])<abs(c-d):
        r+=1
        c,d=C[r]-C[m],C[N]-C[r]
    x=min(x,max(a,b,c,d)-min(a,b,c,d))
print(x)

Verdicts: Wrong Answer

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

Submission attempts (in order):
N = int(input())
A = [int(_) for _ in input().split()]
 
ans = []
t = []
c = 0
for i in range(N):
    c += A[i]
    t.append(c)
    
l = 0
r = 0

for _ in range(2, N-1):
    while t[_] > t[l]+t[l+1]:
        l += 1
    while t[-1]+t[_] > t[r]+t[r+1]:
        r += 1
    n = [t[l], t[_]-t[l], t[r]-t[_], t[-1]-t[r]]
    ans.append(max(n)-min(n))
    
print(min(ans))

N = int(input())
A = [int(_) for _ in input().split()]
 
ans = []
t = []
c = 0
for i in range(N):
    c += A[i]
    t.append(c)
    
l = 0
r = 0

for _ in range(1, N-1):
    while t[_] > t[l]+t[l+1]:
        l += 1
    while t[-1]+t[_] > t[r]+t[r+1]:
        r += 1
    n = [t[l], t[_]-t[l], t[r]-t[_], t[-1]-t[r]]
    ans.append(max(n)-min(n))
print(min(ans))

Verdicts: Wrong Answer

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

Submission attempts (in order):
import numpy as np
N = int(input())
a = np.array([int(item) for item in input().split()], dtype=int)

cum = np.cumsum(a)
total = np.sum(a)
def find(b, total):
    assert sum(b)==total
#     print("b: ", b)
    thre = total/2
    b = np.cumsum(b)
    out = np.argmin(np.abs(b-thre))
#     print("out:", out)
    return out
#     return np.min(np.where(b>thre)[0])

best = total
for i in range(1,N-2):
    left = cum[i]
    right = total - left
    ileft = find(a[:(i+1)], left)
    iright = find(a[(i+1):], right) + i + 1
    z1 = np.sum(a[:(ileft+1)])
    z2 = left - z1
    z3 = np.sum(a[(i+1):(iright+1)])
    z4 = np.sum(a[(iright+1):])  
    M = max([z1,z2,z3,z4])
    m = min([z1,z2,z3,z4])
    best = min(best, M-m)
#     print([z1,z2,z3,z4])
best

cum = np.cumsum(a)
total = np.sum(a)
def find(b, total):
    assert sum(b)==total
#     print("b: ", b)
    thre = total/2
    b = np.cumsum(b)
    out = np.argmin(np.abs(b-thre))
#     print("out:", out)
    return out
#     return np.min(np.where(b>thre)[0])

best = total
for i in range(1,N-2):
    left = cum[i]
    right = total - left
    ileft = find(a[:(i+1)], left)
    iright = find(a[(i+1):], right) + i + 1
    z1 = np.sum(a[:(ileft+1)])
    z2 = left - z1
    z3 = np.sum(a[(i+1):(iright+1)])
    z4 = np.sum(a[(iright+1):])  
    M = max([z1,z2,z3,z4])
    m = min([z1,z2,z3,z4])
    best = min(best, M-m)
#     print([z1,z2,z3,z4])
best

# ARC100D

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


# import numpy as np
import bisect
n = int(input())
a = list(map(int, input().split()))
# a = np.array(list(map(int, input().split())))
ca = [None] * n 
s = 0
for i,num in enumerate(a):
    s += a[i]
    ca[i] = s


def sub(l, start, end, init):
    if len(l)==0:
        return 0,0
    elif end-start==1:
        return 0,l[start]-init
    target = (init + l[end-1])/2
    i = bisect.bisect_right(l, target)
    p1 = (l[i]-init, l[end-1]-l[i])
    p2 = (l[i-1]-init, l[end-1]-l[i-1])
    if abs(p1[0] - p1[1]) < abs(p2[0] - p2[1]):
        return min(p1), max(p1)
    else:
        return min(p2), max(p2)
best = 10**15
for i in range(1,n):
    p1 = sub(ca, 0, i, 0)
    p2 = sub(ca, i, n, ca[i-1])
    nn = max(p1[1]-p2[0], p2[1]-p1[0], p1[1]-p1[0], p2[1]-p2[0])
#     print(p1,p2,nn)
    best = min(best, nn)
print(best)

Verdicts: Wrong Answer

Runtime Error

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

Submission attempts (in order):
import sys
import itertools
import bisect

readInt = lambda : [int(i) for i in input().split()];
n = readInt()[0]
A = readInt()

B = list(itertools.accumulate(A))

cand = 2 * pow(10, 14)
for i in range(2, len(A)-1):
  z = B[i-1]
  s = z // 2
  j = bisect.bisect_right(B, s)
  c0 = abs(2 * B[j-1] - z)
  c1 = abs(2 * B[j] - z)
  j0 = j-1 if c0 < c1 else j

  z = B[i-1]
  s = z + (B[-1] - z) // 2
  j = bisect.bisect_right(B, s)
  c0 = abs(2 * B[j-1] - z)
  c1 = abs(2 * B[j] - z)
  j1 = j-1 if c0 < c1 else j

  c = [B[j0], B[i-1] - B[j0], B[j1] - B[i-1], B[-1] - B[j1]]
  cand = min(cand, max(c) - min(c))

ans = cand
print(ans)


import sys
import itertools
import bisect

readInt = lambda : [int(i) for i in input().split()];
n = readInt()[0]
A = readInt()

B = list(itertools.accumulate(A))

cand = 2 * pow(10, 14)
for i in range(2, len(A)-1):
  z = B[i-1]
  s = z // 2
  j = bisect.bisect_right(B, s)
  if (j == 0):
    j0 = j
  else:
    c0 = abs(2 * B[j-1] - z)
    c1 = abs(2 * B[j] - z)
    j0 = j-1 if c0 < c1 else j

  z = B[-1]
  s = B[i-1] + (B[-1] - B[i-1]) // 2
  j = bisect.bisect_right(B, s)
  if (j == i):
    j1 = j
  else:
    c0 = abs(B[j-1] - B[i-1] - (B[-1] - B[j-1]))
    c1 = abs(B[j]   - B[i-1] - (B[-1] - B[j]  ))
    j1 = j-1 if c0 < c1 else j

  c = [B[j0], B[i-1] - B[j0], B[j1] - B[i-1], B[-1] - B[j1]]
  cand = min(cand, max(c) - min(c))

ans = cand
print(ans)


Verdicts: Wrong Answer

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

Submission attempts (in order):
N = int(input())
A = list(map(int, input().split()))

from itertools import accumulate


ans = float("inf")
if N == 4:
    ans = min(ans, (max(A) - min(A)))
else:
    cs = accumulate(A)
    for i in range(2, N - 2):
        left_cs = cs[:i]
        right_cs = cs[i:]
        for l, v in enumerate(left_cs):
            if v + left_cs[l + 1] >= left_cs[-1]:
                P = left_cs[l]
                Q = left_cs[-1] - P
                break
        for r, v in enumerate(right_cs):
            if v + right_cs[r + 1] >= right_cs[-1]:
                R = right_cs[r]
                S = right_cs[-1] - R
                break
        ans = min(ans, (max(P, Q, R, S) - min(P, Q, R, S)))

print(ans)

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

from itertools import accumulate


ans = float("inf")
if N == 4:
    ans = min(ans, (max(A) - min(A)))
else:
    cs = list(accumulate(A))
    l = 0
    r = 0
    for i in range(1, N - 2):
        while cs[i] > cs[l] + cs[l+1]:
            l += 1
        while cs[-1] + cs[i] > cs[r] + cs[r+1]:
            r += 1
        P = cs[l]
        Q = cs[i] - P
        R = cs[r] - P - Q
        S = cs[-1] - cs[r]
        ans = min(ans, (max(P, Q, R, S) - min(P, Q, R, S)))

print(ans)

Verdicts: Runtime Error

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

Submission attempts (in order):
import numpy as np
import math

global csA
MAXINT = 2 ** 63 - 1

def getsumanddiff(i, j, k):
    p = csA[j+1] - csA[i]
    q = csA[k+1] - csA[j+1]
    return p, q, abs(p - q)

def getfinaldiff(p, q, r, s):
    return max(p, q, r, s) - min(p, q, r, s)

# N = int(input())
# A = np.array(list(map(int, input().split())))
N = 100000000
A = np.arange(N, dtype=int)
csA = np.concatenate([[0], np.cumsum(A)]) 

# init
mid0 = 0
mid2 = 2

p, q, r, s = [0]*4
diff = MAXINT

for mid1 in range(1, N - 2):
    diff0 = MAXINT
    diff2 = MAXINT

    # mid0 search
    for i in range(mid0, mid1):
        tmpp, tmpq, tmpdiff0 = getsumanddiff(0, i, mid1)
        if diff0 > tmpdiff0:
            mid0 = i
            diff0 = tmpdiff0
            p = tmpp
            q = tmpq
        else:
            break

    # mid2 search
    start = mid1 if mid2 < mid1 else mid2
    for i in range(start, N - 1):
        if mid1 >= i:
            continue
        tmpr, tmps, tmpdiff2 = getsumanddiff(mid1+1, i, N - 1)
        if diff2 > tmpdiff2:
            mid2 = i
            diff2 = tmpdiff2
            r = tmpr
            s = tmps
        else:
            break

    tmpdiff = getfinaldiff(p, q, r, s)
    if diff > tmpdiff:
        diff = tmpdiff

print(diff)


import numpy as np
import math

global csA
MAXINT = 2 ** 63 - 1

def getsumanddiff(i, j, k):
    tmp = csA[j+1]
    p = tmp - csA[i]
    q = csA[k+1] - tmp
    return p, q, abs(p - q)

N = int(input())
# A = np.array(list(map(int, input().split())))
# csA = np.cumsum(A)

csA = [0] * (N+1)
for i, v in enumerate(input().split()):
    csA[i+1] = csA[i] + int(v)

# init
mid0 = 0
mid2 = 2

p, q, r, s = [0]*4
diff = MAXINT

csAN = csA[N]
for mid1 in range(1, N - 2):
    diff0 = MAXINT
    diff2 = MAXINT
    csAmid1 = csA[mid1+1]

    # mid0 search
    for i in range(mid0, mid1):
        
        tmpp = csA[i+1]
        tmpq = csAmid1 - tmpp
        tmpdiff0 = abs(tmpp - tmpq)
        if diff0 > tmpdiff0:
            mid0 = i
            diff0 = tmpdiff0
            p = tmpp
            q = tmpq
        else:
            break

    # mid2 search
    start = mid1 if mid2 < mid1 else mid2
    for i in range(start, N - 1):
        # tmpr, tmps, tmpdiff2 = getsumanddiff(mid1+1, i, N - 1)
        csAi = csA[i+1]
        tmpr = csAi - csAmid1
        tmps = csAN - csAi
        tmpdiff2 = abs(tmpr - tmps)
        if diff2 > tmpdiff2:
            mid2 = i
            diff2 = tmpdiff2
            r = tmpr
            s = tmps
        else:
            break

    tmpdiff = max(p, q, r, s) - min(p, q, r, s)
    if diff > tmpdiff:
        diff = tmpdiff

print(diff)


Verdicts: Time Limit Exceeded

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

Submission attempts (in order):
import sys,collections as cl
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

n = int(input())

a = l()

ans = Max
o = 0
oo = a[0]+a[1]
ooo = 0
oooo = sum(a[2:])
l = 0
r = 3
s = a[0]+a[1]
su = sum(a[2:])

for i in range(2,n-2):
	while(l < i-1 and (s >= abs((oo - a[l]) - (o + a[l])))):
		s =  abs((oo - a[l]) - (o + a[l]))
		oo -= a[l]
		o += a[l]
		l += 1

	while(r < n-1 and (su >= abs((oooo - a[r]) - (ooo + a[r])))):
		su = abs((oooo - a[r]) - (ooo + a[r]))
		ooo += a[r]
		oooo -= a[r]
		r += 1
	ans = min(ans,(max(o,oo,ooo,oooo) - min(o,oo,ooo,oooo)))
	oo += a[i]
	ooo -= a[i]

print(ans)



import sys,collections as cl
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

n = int(input())

a = l()
aa = [a[0]]

for i in range(n-1):
	aa.append(aa[-1] + a[i+1])

ans = Max
l = 0
r = 2
s = aa[1]
su = aa[-1]-s
for i in range(1,n-1):
	while(l < i and (s >= abs(2*aa[l] - aa[i]))):
		s =  abs(2*aa[l] - aa[i])
		l += 1

	while(r < n and (su >= abs(aa[-1]-aa[r]-(aa[r] - aa[i])))):
		su = abs(aa[-1]-aa[r]-(aa[r] - aa[i]))
		r += 1
	ans = min(ans,(max(aa[l-1],aa[i]-aa[l-1],aa[r-1]-aa[i],aa[-1]-aa[r-1]) - min(aa[l-1],aa[i]-aa[l-1],aa[r-1]-aa[i],aa[-1]-aa[r-1])))
	s = abs(2*aa[l-1] - aa[i+1])
	su = abs(aa[-1]-aa[r-1]-(aa[r-1] - aa[i+1]))


print(ans)


Verdicts: Wrong Answer

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

Submission attempts (in order):
n = int(input())
a = list(map(int, input().split()))

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

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

print(result)

from functools import reduce

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

left = 0
right = 2
p = a[0]
q = a[1]
r = a[2]
s = reduce(lambda x, y: x + y, a[3:])
temp = right + 1
res_right = abs(s - r)
x = r
y = s
while temp < n - 1:
    x += a[temp]
    y -= a[temp]
    if abs(x - y) < res_right:
        right = temp
        r = x
        s = y
        res_right = abs(x - y)
    if x >= y:
        break
    temp += 1
result = max(p,q,r,s) - min(p,q,r,s)

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

print(result)

Verdicts: Wrong Answer

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

Submission attempts (in order):

import numpy as np
from numba import jit

n = int(input())
sa = np.cumsum(np.array([0]+list(map(int,input().split()))))

@jit
def solve():
    ans = 10**15
    for i in range(1,n-2):
        left = sa[i+1]
        right = sa[-1] - sa[i+1]
        lsplit = min(sa[:i+1].searchsorted(left//2, side="right") - 2, i-1)
        rsplit = min(sa[i+1:].searchsorted(right//2 + left, side="right") + i-1, n-2)
        lleft = [(sa[lsplit + 1],sa[i+1] - sa[lsplit + 1]),(sa[lsplit + 2],sa[i+1] - sa[lsplit + 2])]
        rright = [(sa[rsplit+1] - sa[i+1],sa[-1] - sa[rsplit+1]),(sa[rsplit+2] - sa[i+1],sa[-1] - sa[rsplit+2])]
        for s,t in [(0,0),(0,1),(1,0),(1,1)]:
            l = lleft[s]
            r = rright[t]
            m = min(l+r)
            M = max(l+r)
            ans = min(ans,M-m)
    return ans

print(solve())

# arc 100 D

def ruiseki(n,array):
    res = [0]*(n)
    for i in range(n):
        res[i] = res[i-1] + array[i]
    return res

n = int(input())
A = list(map(int,input().split()))
sa = ruiseki(n,A)

ans = 10**15
left_c = 0
right_c = 2
for center in range(1,n-1):
    while left_c+1 < center:
        if abs(sa[center]-2*sa[left_c]) > abs(sa[center]-2*sa[left_c+1]):
            left_c+=1
        else:
            break

    right_c = max(right_c, center+1)
    while right_c+1 < n-1:
        if abs(sa[-1] + sa[center] - 2*sa[right_c]) > abs(sa[-1] + sa[center] - 2*sa[right_c+1]):
            right_c+=1
        else:
            break
    
    x = max(sa[left_c], sa[center]-sa[left_c], sa[right_c]-sa[center], sa[-1]-sa[right_c])
    y = min(sa[left_c], sa[center]-sa[left_c], sa[right_c]-sa[center], sa[-1]-sa[right_c])
    ans = min(ans, x-y)

print(ans)


Verdicts: Time Limit Exceeded

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

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

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

print(m)

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

r = 0
s = []
for i in a:
  r += i
  s.append(r)

def bs(x,y):
  b = bisect(x, y)
  if abs(x[b-1] - y) < abs(x[b] - y):
    b = b-1
  return b

m = 10**20
for i in range(2, n-1):
  k = bs(s, s[i] / 2)
  l = bs(s, (s[n] + s[i]) / 2)
  s4 = [s[k],s[i]-s[k],s[l]-s[i],s[n]-s[l]]
  m = min(m, max(s4) - min(s4))

print(m)

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

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

print(m)

Verdicts: Wrong Answer

Runtime Error

Accepted