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()))
s=[a[0]]
for i in range(1,n):
    s.append(s[-1]+a[i])
from bisect import bisect_left,bisect_right

ans=[]
for i in range(1,n-2):
    #左側決める
    l=s[i]
    kl=l//2
    ls=bisect_right(a,kl,lo=0,hi=i)-1
    if ls<0:
        candl=[s[ls],l-s[ls]]
    elif abs(s[ls]-(l-s[ls]))<abs(s[ls+1]-(l-s[ls+1])):
        candl=[s[ls],l-s[ls]]
    else:
        candl=[s[ls+1],l-s[ls+1]]
    #右側決める
    kr=(s[n-1]-l)//2
    rs=bisect_right(a,l+kr,lo=i+1,hi=n-1)-1
    if rs<i+1:
        candr=[s[rs]-l,s[n-1]-s[rs]]
    elif abs((s[rs]-l)-(s[n-1]-s[rs]))<abs((s[rs+1]-l)-(s[n-1]-s[rs+1])):
        candr=[s[rs]-l,s[n-1]-s[rs]]
    else:
        candr=[s[rs+1]-l,s[n-1]-s[rs+1]]
    ans.append(max(candl+candr)-min(candl+candr))
print(min(ans))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
sl=[a[0]]
for i in range(1,n):
    sl.append(sl[-1]+a[i])
b=a[::-1]
sr=[b[0]]
for i in range(1,n):
    sr.append(sr[-1]+b[i])
from bisect import bisect_left,bisect_right
ans=[]
for i in range(1,n-2):
    #左側決める
    l=sl[i]
    kl=l//2
    lsl,lsr=bisect_left(a,kl,hi=i),bisect_right(a,kl,hi=i)-1
    if lsr<0:
        lsr+=1
    if abs(sl[lsl]-(l-sl[lsl]))<abs(sl[lsr]-(l-sl[lsr])):
        candl=[sl[lsl],l-sl[lsl]]
    else:
        candl=[sl[lsr],l-sl[lsr]]
    #右側決める
    r=sr[n-(i+1)-1]
    kr=r//2
    rsl,rsr=bisect_left(b,kr,hi=n-(i+1)-1),bisect_right(b,kr,hi=n-(i+1)-1)-1
    if rsr<0:
        rsr+=1
    if abs(sr[rsl]-(r-sr[rsl]))<abs(sr[rsr]-(r-sr[rsr])):
        candr=[sr[rsl],r-sr[rsl]]
    else:
        candr=[sr[rsr],r-sr[rsr]]
    ans.append(max(candl+candr)-min(candl+candr))
print(min(ans))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
x=sum(a)//4
p,sp=0,0
for i in range(n):
    sp+=a[i]
    p=i
    if sp>=x:
        break

def qq(p_):
    global n,a
    x=(sum(a)-sum(a[:p_+1]))//3
    q_,sq_=0,0
    for i in range(p_+1,n):
        sq_+=a[i]
        q_=i
        if sq_>=x:
            break
    return [q_-1,q_]
def rr(q_):
    global n,a
    x=(sum(a)-sum(a[:q_+1]))//2
    r_,sr_=0,0
    for i in range(q_+1,n):
        sr_+=a[i]
        r_=i
        if sr_>=x:
            break
    return [r_-1,r_]
f=[p-1,p] if p!=0 else [p]
ans=[]
for z1 in f:
    for z2 in qq(z1):
        for z3 in rr(z2):
            cand=[sum(a[:z1+1]),sum(a[z1+1:z2+1]),sum(a[z2+1:z3+1]),sum(a[z3+1:])]
            ans.append(max(cand)-min(cand))
print(min(ans))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
x=sum(a)//4
p,sp=0,0
for i in range(n):
    sp+=a[i]
    p=i
    if sp>x:
        break

def qq(p_):
    global n,a
    x=(sum(a)-sum(a[:p_+1]))//3
    q_,sq_=0,0
    for i in range(p_+1,n):
        sq_+=a[i]
        q_=i
        if sq_>x:
            break
    return [q_-1,q_]
def rr(q_):
    global n,a
    x=(sum(a)-sum(a[:q_+1]))//2
    r_,sr_=0,0
    for i in range(q_+1,n):
        sr_+=a[i]
        r_=i
        if sr_>x:
            break
    return [r_-1,r_]
f=[p-1,p] if p!=0 else [p]
ans=[]
for z1 in f:
    for z2 in qq(z1):
        for z3 in rr(z2):
            cand=[sum(a[:z1+1]),sum(a[z1+1:z2+1]),sum(a[z2+1:z3+1]),sum(a[z3+1:])]
            ans.append(max(cand)-min(cand))
print(min(ans))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from itertools import accumulate

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

# 真ん中で切る位置を決めてから、左右の最大値と最小値を調べる（二分探索）
N = ir()
B = lr()

def check(A):
    limit = len(A)
    assert limit >= 2
    Acum = list(accumulate(A))
    total = Acum[-1]
    def cal(i):
        assert i > 0
        """iで切った時、右(i以降)の方が大きいならTrueを返す"""
        left = Acum[i-1]
        right = total - left
        return right > left        
    
    ok = 0; ng = limit-1
    while abs(ng-ok) > 1:
        mid = (ok+ng) // 2
        if cal(mid):
            ok = mid
        else:
            ng = mid
    if ok == 0:
        ok += 1
    #print(ok, ng, limit, Acum, i)
    x = Acum[ok-1]; y = total - x
    mi, ma = min(x, y), max(x, y)
    if ng < limit:
        x2 = Acum[ng]; y2 = total - x2
        mi2, ma2 = min(x2, y2), max(x2, y2)
        if abs(ma2-mi2) < abs(ma-mi):
            mi, ma = mi2, ma2
    return mi, ma

answer = 10 ** 15
for i in range(2, N-1):
    left_min, left_max = check(B[:i])
    right_min, right_max = check(B[i:])
    mi = min(left_min, right_min)
    ma = max(left_max, right_max)
    temp = ma - mi
    if temp < answer:
        answer = temp

print(answer)

Submission status: Wrong Answer

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

from itertools import accumulate
CA = list(accumulate(A))

mindiff = CA[-1]
left = 0
right = 2
for c in range(1,N-1):
    # left side
    p = CA[left]
    q = CA[c] - CA[left]
    while left < c:
        pi = CA[left+1]
        qi = CA[c] - CA[left+1]
        if abs(pi- qi) >= abs(p - q):
            break
        p = pi; q = qi
        left += 1

    # right side
    r = CA[right]
    s = CA[-1]
    while right < N:
        ri = CA[right+1] - CA[c]
        si = CA[-1] - CA[right+1]
        if abs(ri- si) >= abs(r - s):
            break
        r = ri; s = si
        right += 1

    mindiff = min(mindiff, max(p, q, r, s) - min(p, q, r, s))
print(mindiff)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = [int(x) for x in input().split()]
a_list = [1, 2, 3, 4]
n = len(a_list)
 
temp_list = [0] * (n + 1)
for i in range(1, n + 1):
    temp_list[i] = a_list[i - 1] + temp_list[i - 1]
 
l = 1
r = 3
ans = temp_list[-1]
for m in range(2, n - 1):
    gap_min = abs((temp_list[m] - temp_list[l]) - (temp_list[l] - temp_list[0]))
    while l < m:
        l += 1
        gap = abs((temp_list[m] - temp_list[l]) - (temp_list[l] - temp_list[0]))
        if gap < gap_min:
            gap_min = gap
        else:
            l -= 1
            break
    else:
        l -= 1
    
    gap_min = abs((temp_list[n] - temp_list[r]) - (temp_list[r] - temp_list[m]))
    while r < n:
        r += 1
        gap = abs((temp_list[n] - temp_list[r]) - (temp_list[r] - temp_list[m]))
        if gap < gap_min:
            gap_min = gap
        else:
            r -= 1
            break
    else:
        r -= 1
    
    num_list = sorted([temp_list[l] - temp_list[0], temp_list[m] - temp_list[l], temp_list[r] - temp_list[m], temp_list[n] - temp_list[r]])
    ans_temp = num_list[3] - num_list[0]
    if ans_temp < ans:
        ans = ans_temp
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = [int(x) for x in input().split()]

temp_list = [0] * (n + 1)
for i in range(1, n + 1):
    temp_list[i] = a_list[i - 1] + temp_list[i - 1]

l = 1
r = 3
ans = temp_list[-1]
for m in range(2, n - 2):
    gap_min = abs((temp_list[m] - temp_list[l]) - (temp_list[l] - temp_list[0]))
    while l < m:
        l += 1
        gap = abs((temp_list[m] - temp_list[l]) - (temp_list[l] - temp_list[0]))
        if gap < gap_min:
            gap_min = gap
        else:
            l -= 1
            break
    else:
        l -= 1
    
    gap_min = abs((temp_list[n] - temp_list[r]) - (temp_list[r] - temp_list[m]))
    while r < n:
        r += 1
        gap = abs((temp_list[n] - temp_list[r]) - (temp_list[r] - temp_list[m]))
        if gap < gap_min:
            gap_min = gap
        else:
            r -= 1
            break
    else:
        r -= 1
    
    num_list = sorted([temp_list[l] - temp_list[0], temp_list[m] - temp_list[l], temp_list[r] - temp_list[m], temp_list[n] - temp_list[r]])
    ans_temp = num_list[3] - num_list[0]
    if ans_temp < ans:
        ans = ans_temp
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = [int(x) for x in input().split()]

temp_list = [0] * (n + 1)
for i in range(1, n + 1):
    temp_list[i] = a_list[i - 1] + temp_list[i - 1]

ans = temp_list[-1]
for m in range(2, n - 2):
    gap_min = temp_list[m]
    l = 1
    while l < m:
        gap = abs((temp_list[m] - temp_list[l]) - (temp_list[l] - temp_list[0]))
        if gap < gap_min:
            gap_min = gap
            l += 1
        else:
            l -= 1
            break
    else:
        l -= 1
    
    gap_min = temp_list[n]
    r = m + 1
    while r < n:
        gap = abs((temp_list[n] - temp_list[r]) - (temp_list[r] - temp_list[m]))
        if gap < gap_min:
            gap_min = gap
            r += 1
        else:
            r -= 1
            break
    else:
        r -= 1
    
    num_list = sorted([temp_list[l] - temp_list[0], temp_list[m] - temp_list[l], temp_list[r] - temp_list[m], temp_list[n] - temp_list[r]])
    ans_temp = num_list[3] - num_list[0]
    if ans_temp < ans:
        ans = ans_temp
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
    F[b] = F[b - 1] + A[b]


x = F[-1] // 4
res = [0]*4
i = 0
for s in range(3):
    res[s] += A[i]
    for t in range(i + 1, n - 1):
        if abs(x - res[s]) > abs(x - res[s] - A[t]):
            res[s] += A[t]
        else:
            i = t
            break
res[3] = F[-1] - F[i - 1]
print(max(res) - min(res))

Submission status: Wrong Answer

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

def solve(K):
    ans = 1
    cnt = 0
    i = 0
    while i < N:
        if A[i] > K:
            return False
        cnt += A[i]
        if i != N-1 and cnt + A[i+1] > K:
            ans += 1
            cnt = 0
        i += 1
    return ans >= 4

left = 0
right = 10 ** 16

while left + 1 < right:
    mid = (left + right) // 2
    if solve(mid):
        left = mid
    else:
        right = mid

K = left
MIN = 10 ** 10
MAX = -1 * 10 ** 10

cnt = 0
i = 0
while i < N:
    cnt += A[i]
    if i != N-1 and cnt + A[i+1] > K:
        MIN = min(MIN, cnt)
        MAX = max(MAX, cnt)
        cnt = 0
    i += 1
MIN = min(MIN, cnt)
MAX = max(MAX, cnt)
print(MAX-MIN)

Submission status: Wrong Answer

Solution code:
def bsearch(target, ok, ng):
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if cumA[mid] <= target:
            ok = mid
        else:
            ng = mid
    return ok

def tmpB1(ok, B):
    # B[1]はokまたはok + 1
    if abs((cumA[ok] - cumA[B[0]]) - (cumA[B[2]] - cumA[ok])) <= \
        abs((cumA[ok + 1] - cumA[B[0]]) - (cumA[B[2]] - cumA[ok + 1])):
        return ok
    else:
        return ok + 1

N = int(input())
A = [int(x) for x in input().split()]

cumA = [A[0]] + [0] * (N - 1)  # 累積和
for i in range(1, N):
    cumA[i] = cumA[i - 1] + A[i]

B = [-1, -1, N - 1]
S = [0, 0, cumA[N - 1], 0]
newB = [0, 0, 0]
newS = [0, 0, 0, 0]
diff = cumA[N - 1]
B0defined = False
B2defined = False

while(B[2] - B[0] > 2):
    m = min(S)
    diff = max(S) - min(S)
    if S[0] == m and not B0defined:
        newB[0] = B[0] + 1
        newB[2] = B[2]
        newS[0] = cumA[newB[0]]
        newS[3] = S[3]

        # targetを超えない最大のB[1]の位置を探す
        target = (cumA[newB[2]] + cumA[newB[0]]) / 2
        ok = newB[0]
        ng = newB[2] # B[0] < B[2]ならば
        ok = bsearch(target, ok, ng)
        newB[1] = tmpB1(ok, newB)
        newS[1] = cumA[newB[1]] - cumA[newB[0]]
        newS[2] = cumA[newB[2]] - cumA[newB[1]]

        new_diff = max(newS) - min(newS)
        if new_diff < diff:
            for i in range(4):
                S[i] = newS[i]
            for i in range(3):
                B[i] = newB[i]
        else:
            B0defined = True

    elif S[3] == m and not B2defined:
        newB[2] = B[2] - 1
        newB[0] = B[0]
        newS[3] = cumA[N - 1] - cumA[newB[2]]
        newS[0] = S[0]

        # targetを超えない最大のB[1]の位置を探す
        target = (cumA[newB[2]] + cumA[newB[0]]) / 2
        ok = newB[0]
        ng = newB[2] # B[0] < B[2]ならば
        ok = bsearch(target, ok, ng)
        newB[1] = tmpB1(ok, newB)
        newS[1] = cumA[newB[1]] - cumA[newB[0]]
        newS[2] = cumA[newB[2]] - cumA[newB[1]]

        new_diff = max(newS) - min(newS)
        if new_diff < diff:
            for i in range(4):
                S[i] = newS[i]
            for i in range(3):
                B[i] = newB[i]
        else:
            B2defined = True
    else:
        break

print(max(S) - min(S))

Submission status: Wrong Answer

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

def bs_left(mid,mp):
  sum1=sum2=sum3=abs(2*slist[mid]-slist[mp])
  if mid>0:
    sum1=abs(2*slist[mid-1]-slist[mp])
  if mid<mp:
    sum3=abs(2*slist[mid+1]-slist[mp])

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    

def bs_right(mid,mp):
  sum1=sum2=sum3=abs(2*(slist[mid]-slist[mp])-(slist[-1]-slist[mp]))
  if mid>0:
    sum1=abs(2*(slist[mid-1]-slist[mp])-(slist[-1]-slist[mp]))
  if mid<mp:
    sum3=abs(2*(slist[mid+1]-slist[mp])-(slist[-1]-slist[mp]))

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    
  
slist=[]
asum=0
for a in alist:
  asum+=a
  slist.append(asum)
#print(alist)
#print(slist)

dic_lp,dic_rp={},{}
for mp in range(1,N-2):  
  #lp
  l,r=0,mp-1
  while(l<=r):
    mid=(l+r)//2
    ret=bs_left(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_lp[mp]=mid
      #print(mp,mid)
      break
  
  #rp
  l,r=mp+1,N-2
  while(l<=r):
    mid=(l+r)//2
    ret=bs_right(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_rp[mp]=mid
      #print(mp,mid)
      break
    
min_diff=10**9
for mp in range(1,N-2):
  lp=dic_lp[mp]
  rp=dic_rp[mp]
  
  sum1=slist[lp]
  sum2=slist[mp]-slist[lp]
  sum3=slist[rp]-slist[mp]
  sum4=slist[-1]-slist[rp]
  #print(sum1,sum2,sum3,sum4)
  
  sum_list=[sum1,sum2,sum3,sum4]
  sum_list.sort()
  diff=sum_list[-1]-sum_list[0]
  #print(lp,mp,rp,diff)
  if diff<min_diff:
    min_diff=diff    
  
print(min_diff)

Submission status: Wrong Answer

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

allsum=sum(alist)
#print(alist,allsum)
ptt_list=[-1,-1,-1]

dlist=[]
asum=0
for i in range(N):
  asum+=alist[i]
  dlist.append(abs(allsum-2*asum))
#print(dlist)
min_d=10**9
part2=-1
for i in range(N):
  if dlist[i]<min_d:
    min_d=dlist[i]
    part2=i
    
#print(part2)
plist1=alist[:part2+1]
plist2=alist[part2+1:]
#print(plist1,plist2)

p1sum=sum(plist1)
p2sum=sum(plist2)
dlist=[]
asum=0
for i in range(len(plist1)):
  asum+=plist1[i]
  dlist.append(abs(p1sum-2*asum))
#print(dlist)
min_d=10**9
part1=-1
for i in range(len(plist1)):
  if dlist[i]<min_d:
    min_d=dlist[i]
    part1=i

dlist=[]
asum=0
for i in range(len(plist2)):
  asum+=plist2[i]
  dlist.append(abs(p2sum-2*asum))
#print(dlist)
min_d=10**9
part3=-1
for i in range(len(plist2)):
  if dlist[i]<min_d:
    min_d=dlist[i]
    part3=i

ptt_list=[part1,part2,part2+1+part3]
#print(ptt_list)

sum1=sum(alist[:ptt_list[0]+1])
sum2=sum(alist[ptt_list[0]+1:ptt_list[1]+1])
sum3=sum(alist[ptt_list[1]+1:ptt_list[2]+1])
sum4=sum(alist[ptt_list[2]+1:])

sum_list=[sum1,sum2,sum3,sum4]
sum_list.sort()
print(sum_list[-1]-sum_list[0])

Submission status: Wrong Answer

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


def dif_over_k(k):
    box = 1
    s = 0
    max_val = 0
    min_val = float("inf")
    # print("k: ", k)
    for i in range(n):
        s += A[i]
        if s >= k and box <= 3:
            # print(s)
            max_val = max(max_val, s)
            min_val = min(min_val, s)
            box += 1
            s = 0

    # print(s)
    max_val = max(max_val, s)
    min_val = min(min_val, s)
    dif = max_val - min_val
    if box < 4 or min_val < k:
        dif = -1

    # print("dif: ", dif)
    return dif


left = min(A)
right = max(A)
min_dif = float("inf")

while left <= right:
    mid = (left+right)//2
    dif = dif_over_k(mid)
    if dif == -1:
        right = mid-1
    else:
        min_dif = min(min_dif, dif)
        left = mid+1

print(min_dif)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
if n==4:
  print(max(A)-min(A))
  exit()
s=sum(A)
a=A[0]+A[1]+A[2]
i=2
while a<s/2 and i<n-3:
  i=i+1
  a=a+A[i]
B1=A[0:i]
C1=A[i:n]
B2=A[0:i+1]
C2=A[i+1:n]
#print(B1,C1,B2,C2)
if len(B1)==2:
  BB1=max(B1)
  BB2=min(B1)
else:
  aa=B1[0]+B1[1]
#  print(aa)
  ss=sum(B1)
  i=1
  while aa<ss/2 and i<len(B1)-1:
    i=i+1
    aa=aa+B1[i]
  aa1=aa
  aa2=ss-aa1
  aa3=aa-B1[i]
  aa4=ss-aa3
  C=[aa1,aa2,aa3,aa4]
  C.sort()
  BB1=C[2]
  BB2=C[1]
#print(BB1,BB2)
if len(C1)==2:
  BCC1=max(C1)
  BCC2=min(C1)
else:
  aa=C1[0]+C1[1]
  ss=sum(C1)
  i=1
  while aa<ss/2 and i<len(C1)-1:
    i=i+1
    aa=aa+C1[i]
  aa1=aa
  aa2=ss-aa1
  aa3=aa-C1[i]
  aa4=ss-aa3
  C=[aa1,aa2,aa3,aa4]
  C.sort()
  BBC1=C[2]
  BBC2=C[1]
#print(BBC1,BBC2)
ans1=max(BB1,BBC1)-min(BB2,BBC2)



if len(B2)==2:
  BB12=max(B2)
  BB22=min(B2)
else:
  aa=B2[0]+B2[1]
#  print(aa)
  ss=sum(B2)
  i=1
  while aa<ss/2 and i<len(B2)-1:
    i=i+1
    aa=aa+B2[i]
  aa1=aa
  aa2=ss-aa1
  aa3=aa-B2[i]
  aa4=ss-aa3
  C=[aa1,aa2,aa3,aa4]
  C.sort()
  BB12=C[2]
  BB22=C[1]
#print(BB12,BB22)
if len(C2)==2:
  BCC12=max(C2)
  BCC22=min(C2)
else:
  aa=C2[0]+C2[1]
  ss=sum(C2)
  i=1
  while aa<ss/2 and i<len(C2)-1:
    i=i+1
    aa=aa+C2[i]
  aa1=aa
  aa2=ss-aa1
  aa3=aa-C2[i]
  aa4=ss-aa3
  C=[aa1,aa2,aa3,aa4]
  C.sort()
  BCC12=C[2]
  BCC22=C[1]
#print(BCC12,BCC22)
ans2=max(BB12,BCC12)-min(BB22,BCC22)


print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
#dame datta
def main():
    N = int(input())
    A = list(map(int, input().split()))
    Al = [A[0]]
    r = (10**9)*(2*(10**5))
    for i in A[1:]:
        Al.append(Al[-1] + i)
    for t in range(2, N-2):
        t1 = -1
        m = (10**9)*(2*(10**5))
        for i in range(1,t):
            ii = abs(Al[t-1] - Al[i-1] - Al[i-1])
            if m > ii:
                t1 = i
                m = ii
        t2 = -1
        m = (10**9)*(2*(10**5))
        for i in range(t+1, N):
            ii = abs(Al[-1] - Al[i-1] - Al[i-1] + Al[t-1])
            if m > ii:
                t2 = i
                m = ii
        x = Al[-1] - Al[t2-1]
        y = Al[t2-1] - Al[t-1]
        z = Al[t-1] - Al[t1-1]
        w = Al[t1-1]
        r = min(max(x,y,z,w) - min(x,y,z,w), r)
    return r
print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    Al = [A[0]]
    for i in A[1:]:
        Al.append(Al[-1] + i)
    t = -1
    m = (10**9)*(2*(10**5))
    for i in range(1, N-1):
        ii = abs(Al[-1] - Al[i-1] - Al[i-1])
        if m > ii:
            t = i
            m = ii
    t1 = -1
    m = (10**9)*(2*(10**5))
    for i in range(1,t):
        ii = abs(Al[t-1] - Al[i-1] - Al[i-1])
        if m > ii:
            t1 = i
            m = ii
    t2 = -1
    m = (10**9)*(2*(10**5))
    for i in range(t+1, N):
        ii = abs(Al[-1] - Al[i-1] - Al[i-1] + Al[t-1])
        if m > ii:
            t2 = i
            m = ii
    t3 = -1
    m = (10**9)*(2*(10**5))
    for i in range(t1, t2):
        ii = abs(Al[t2-1] - Al[i-1] - Al[i-1] + Al[t1-1])
        if m > ii:
            t3 = i
            m = ii
    x = Al[-1] - Al[t2-1]
    y = Al[t2-1] - Al[t3-1]
    z = Al[t3-1] - Al[t1-1]
    w = Al[t1-1]
    return max(x,y,z,w) - min(x,y,z,w)
print(main())

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
#102_D
N = int(input())
A = [int(i) for i in input().split()]
s = 0
AS = []
for i in range(N):
    s += A[i]
    AS.append(s)
#尺取り法
Ans = AS[N-1]+1
L = 0
R = 2
for Mid in range(1, N-2):
    Sum_L = AS[Mid]
    Sum_R = AS[N-1]-Sum_L
    while abs((Sum_L - AS[L]) - A[L]) > abs((Sum_L - AS[L+1]) - AS[L+1]):
        L += 1

    while abs((AS[N-1] - AS[R]) - (AS[R] - Sum_L)) > abs((AS[N-1] - AS[R+1]) - (AS[R+1] - Sum_L)):
        R += 1
    P = AS[L]
    Q = Sum_L-AS[L]
    S = AS[R]-Sum_L
    T = AS[N-1]-AS[R]
    #print(Mid,L,R,abs(max(P,Q,S,T)-min(P,Q,S,T)))
    Ans = min(Ans, abs(max(P, Q, S, T)-min(P, Q, S, T)))
print(Ans)

Submission status: Wrong Answer

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

for i in range(N):
    S[i+1]=S[i]+A[i]
    
ans=10**20

sp=S[1]
sq=0
sr=S[3]-S[1]
ss=S[-1]-S[3]

th_pq=1
th_rs=3

for i in range(2,N-2):#全体をi番目で二分割
    sq+=A[i-1]
    sr-=A[i-1]
    while th_pq!=i-1:#pqの境界を移動させる
        diff_pq=abs(sp-sq)
        sp2=sp+A[th_pq]
        sq2=sq-A[th_pq]
        diff_pq2=abs(sp2-sq2)
        if diff_pq2 <= diff_pq:
            sp=sp2
            sq=sq2
            th_pq+=1
        else:
            break
        
    while th_rs!=N-1:
        diff_rs=abs(sr-ss)
        sr2=sr+A[th_rs]
        ss2=ss-A[th_rs]
        diff_rs2=abs(sr2-ss2)
        if diff_rs2 <= diff_rs:
            sr=sr2
            ss=ss2
            th_rs+=1
        else:
            break
    temp=max(sp,sr,sq,ss) - min(sp,sq,sr,ss)
    ans=min(ans,temp)
    
print(ans)

Submission status: Wrong Answer

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

for i in range(N):
    S[i+1]=S[i]+A[i]
    
ans=10**20

sp=S[1]
sq=0
sr=S[3]-S[1]
ss=S[-1]-S[3]

th_pq=1
th_rs=3

for i in range(1,N-2):#全体をi番目で二分割
    sq+=A[i]
    sr-=A[i]
    diff_pq=abs(sp-sq)
    while th_pq!=i:#pqの境界を移動させる
        sp2=sp+A[th_pq]
        sq2=sq-A[th_pq]
        diff_pq2=abs(sp2-sq2)
        if diff_pq2 <= diff_pq:
            sp=sp2
            sq=sq2
            th_pq+=1
        else:
            break
            
    diff_rs=abs(sr-ss)
    while th_rs!=N-1:
        sr2=sr+A[th_rs]
        ss2=ss-A[th_rs]
        diff_rs2=abs(sr2-ss2)
        if diff_rs2 <= diff_rs:
            sr=sr2
            ss=ss2
            th_rs+=1
        else:
            break
    temp=max(sp,sr,sq,ss) - min(sp,sq,sr,ss)
    ans=min(ans,temp)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    N = I()
    A = LI()
    cumsum = [0 for _ in range(N+1)]

    for i in range(N):
        cumsum[i+1] = cumsum[i] + A[i]

    def get_cumsum(a, b):
        # get cumsum from [a, b] element
        return cumsum[b+1] - cumsum[a]

    def separate_opt_sum(l, r):
        # find arr1, arr2 s.t. |arr1 - arr2| = min
        # arr1 = get_cumsum(l, k), arr2 = get_cumsum(k+1, r)
        tot_sum = get_cumsum(l, r)
        m = (l + r) // 2
        m_min = l - 1
        m_max = r + 1
        cur_min_diff = abs(2 * get_cumsum(l, m) - tot_sum)
        cur_min_m = m
        while m_min < m and m < m_max:
            left_sum = get_cumsum(l, m)
            right_sum = tot_sum - left_sum
            cur_diff = abs(left_sum - right_sum)
            if cur_diff < cur_min_diff:
                cur_min_diff = cur_diff
                cur_min_m = m
            if left_sum < right_sum:
                m_min = m
                m = (m + r) // 2
            elif left_sum > right_sum:
                m_max = m
                m = (l + m) // 2
            else:
                break

        l_ans = get_cumsum(l, cur_min_m)
        r_ans = get_cumsum(cur_min_m + 1, r)
        return l_ans, r_ans

    ans = inf
    for sep in range(1, N-2):
        left_S = get_cumsum(0, sep)
        right_S = get_cumsum(sep+1, N-1)
        # import pdb
        # pdb.set_trace()
        p, q = separate_opt_sum(0, sep)
        r, s = separate_opt_sum(sep+1, N-1)
        # print('sep:', sep, ' ', p, q, r, s)
        # print('\tleft_S:', left_S, ' right_S:', right_S)
        ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    N = I()
    A = LI()
    cumsum = [0 for _ in range(N+1)]

    for i in range(N):
        cumsum[i+1] = cumsum[i] + A[i]

    def get_cumsum(a, b):
        # get cumsum from [a, b] element
        return cumsum[b+1] - cumsum[a]

    def separate_opt_sum(arr, l, r):
        # find arr1, arr2 s.t. |arr1 - arr2| = min
        # arr1 = get_cumsum(l, k), arr2 = get_cumsum(k+1, r)
        tot_sum = get_cumsum(l, r)
        m = (l + r) // 2
        m_min = l - 1
        m_max = r + 1
        cur_min_diff = inf
        while m_min < m and m < m_max:
            left_sum = get_cumsum(l, m)
            right_sum = tot_sum - left_sum
            cur_diff = abs(left_sum - right_sum)
            if cur_diff < cur_min_diff:
                cur_min_diff = cur_diff
                cur_min_m = m

            if left_sum < right_sum:
                m_min = m
                m = (m + r) // 2
            elif left_sum > right_sum:
                m_max = m
                m = (l + m) // 2
            else:
                break

        l_ans = get_cumsum(l, cur_min_m)
        r_ans = get_cumsum(cur_min_m + 1, r)
        return l_ans, r_ans

    ans = inf
    for sep in range(1, N-2):
        left_S = get_cumsum(0, sep)
        right_S = get_cumsum(sep+1, N-1)
        # import pdb
        # pdb.set_trace()
        p, q = separate_opt_sum(left_S, 0, sep)
        r, s = separate_opt_sum(right_S, sep+1, N-1)
        # print('sep:', sep, ' ', p, q, r, s)
        # print('\tleft_S:', left_S, ' right_S:', right_S)
        ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
# 解説の方法

from itertools import accumulate

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

acc = list(accumulate(a))

l = 0
r = 2

ans = float('inf')

for y in range(1,n-3):
    for x in range(l,y-1):
        if abs(acc[y]-acc[x]*2)>=abs(acc[y]-acc[x+1]*2):
            l = x+1
            continue
        else:
            break
    r = max(y+1,r)
    for z in range(r,n-2):
        if abs(acc[n-1]-acc[z]*2+acc[y])>=abs(acc[n-1]-acc[z+1]*2+acc[y]):
            r = z+1
            continue
        else:
            break
    P = acc[l]
    Q = acc[y] - acc[l]
    R = acc[r] - acc[y]
    S = acc[n-1] - acc[r]
    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

def binary_search(a, left, right, base):
    l,r = left, right
    while l + 1 < r:
        mid = (l+r)//2
        # print(acc[right] - base, )
        if acc[right] - base < (acc[mid] - base) * 2:
            r = mid
        else:
            l = mid
    if abs(acc[right] - base - (acc[r] - base) * 2) < abs(acc[right] - base - (acc[l] - base) * 2):
        return r
    else:
        return l

n = int(input())
a = [0] + list(map(int, input().split()))
acc = list(accumulate(a))
ans = float('INF')
for i in range(2,n-2):
    s = binary_search(a, 1,i, 0)
    t = binary_search(a, i+1,n, acc[i])
    o,p,q,r = acc[s], acc[i]-acc[s], acc[-1]-acc[t], acc[t] - acc[i]
    # print(s,i,t, o,p,q,r)
    if max(q,p,r,o) - min(p,q,r,o) < ans:
        ans = max(p,q,r,o) - min(p,q,r,o)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

def binary_search(a, left, right, base):
    l,r = left, right
    while l + 1 < r:
        mid = (l+r)//2
        # print(acc[right] - base, )
        if acc[right] - base < (acc[mid] - base) * 2:
            r = mid
        else:
            l = mid
    if abs(acc[right] - base - (acc[r] - base) * 2) < abs(acc[right] - base - (acc[l] - base) * 2):
        return r
    else:
        return l

n = int(input())
a = [0] + list(map(int, input().split()))
acc = list(accumulate(a))
ans = float('INF')
for i in range(2,n-2):
    s = binary_search(a, 0,i, 0)
    t = binary_search(a, i+1,n, acc[i])
    o,p,q,r = acc[s], acc[i]-acc[s], acc[-1]-acc[t], acc[t] - acc[i]
    # print(s,i,t, o,p,q,r)
    if max(q,p,r,o) - min(p,q,r,o) < ans:
        ans = max(p,q,r,o) - min(p,q,r,o)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
a=list(map(int,input().split()))
def check(x):
  d = [0] * 4
  p = 0
  for i in range(N):
    d[p] += a[i]
    if d[p] >= x: p += 1
    if p > 3: p -= 1
  return min(d) >= x
def solve(r):
  d=[0]*4
  p=0
  for i in range(N):
    d[p] += a[i]
    if d[p] > r:
      d[p] -= a[i]
      p+=1
      if p > 3: return False
      d[p]+=a[i]
  return True
ok = 0
ng = sum(a)
m = 0
while ng - ok > 1:
  m = (ok + ng) // 2
  if check(m):
    ok = m
  else: ng = m
mn = ok+0
ng = max(mn, max(a)) - 1
ok = sum(a)
m = 0
while ok - ng > 1:
  m = (ok + ng) // 2
  if solve(m):
    ok = m
  else: ng = m
print(ok-mn)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=list(map(int,input().split()))
def check(x):
  d = [0] * 4
  p = 0
  for i in range(N):
    d[p] += a[i]
    if d[p] >= x: p += 1
    if p > 3: p -= 1
  return min(d) >= x
def solve(r):
  d=[0]*4
  p=0
  for i in range(N):
    d[p] += a[i]
    if d[p] > r:
      d[p] -= a[i]
      p+=1
      if p > 3: return False
      d[p]+=a[i]
  return True
ok = 0
ng = N * max(a)
m = 0
while ng - ok > 1:
  m = (ok + ng) // 2
  if check(m):
    ok = m
  else: ng = m
mn = ok+0
ng = max(mn, max(a)) - 1
ok = N * max(a)
m = 0
while ok - ng > 1:
  m = (ok + ng) // 2
  if solve(m):
    ok = m
  else: ng = m
print(ok-mn)