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 = [0] + list(map(int, input().split()))
for i in range(1, N + 1):
    A[i] += A[i - 1]


# print (A)

ans = 10 ** 9

#基準を求める
stan = A[N]//4

for i in range(2 ** 3):
    PQRS = [0, 0, 0, 0]
    index = 1
    prev_index = 0
    for j in range(3):
        if (i >> j) & 1: #基準以上にするとき
            while A[index] - A[prev_index] < stan and index < N:
                index += 1
            PQRS[j] = A[index] - A[prev_index]
            prev_index = index
            # print (1, end = '')
        else: #基準以下にするとき
            while A[index] - A[prev_index] < stan and index < N:
                index += 1
            PQRS[j] = A[index - 1] - A[prev_index]
            prev_index = index - 1
            # print (0, end = '')
    PQRS[3] = A[N] - A[prev_index]
    # print (PQRS, end = ' ')
    # print (max(PQRS) - min(PQRS))
    ans = min((max(PQRS) - min(PQRS)), ans)

stan = (A[N] + 3)//4

for i in range(2 ** 3):
    PQRS = [0, 0, 0, 0]
    index = 1
    prev_index = 0
    for j in range(3):
        if (i >> j) & 1: #基準以上にするとき
            while A[index] - A[prev_index] < stan and index < N:
                index += 1
            PQRS[j] = A[index] - A[prev_index]
            prev_index = index
            # print (1, end = '')
        else: #基準以下にするとき
            while A[index] - A[prev_index] < stan and index < N:
                index += 1
            PQRS[j] = A[index - 1] - A[prev_index]
            prev_index = index - 1
            # print (0, end = '')
    PQRS[3] = A[N] - A[prev_index]
    # print (PQRS, end = ' ')
    # print (max(PQRS) - min(PQRS))
    ans = min((max(PQRS) - min(PQRS)), ans)


print (ans)

Submission status: Wrong Answer

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

total = sum(a)
memo = 0
for i in range(n):
    memo += a[i]
    if memo >= total/2:
        # print(sum(a[:i]))
        # print(sum(a[:(i+1)]))
        if total/2-sum(a[:i]) < sum(a[:(i+1)])-total/2:
            c = i
        else:
            c = i+1
        break

a_l = a[:c]
a_r = a[c:]

# print(a_l)
# print(a_r)

total_l = sum(a_l)
memo_l = 0
for i in range(len(a_l)):
    memo_l += a_l[i]
    if memo_l >= total_l/2:
        if total_l/2-sum(a_l[:i]) < sum(a_l[:(i+1)])-total_l/2:
            c_l = i
        else:
            c_l = i+1
        break
p = sum(a_l[:c_l])
q = sum(a_l[c_l:])

total_r = sum(a_r)
memo_r = 0
for i in range(len(a_r)):
    memo_r += a_r[i]
    if memo_r >= total_r/2:
        if total_r/2-sum(a_r[:i]) < sum(a_r[:(i+1)])-total_r/2:
            c_r = i
        else:
            c_r = i+1
        break
r =sum(a_r[:c_r])
s = sum(a_r[c_r:])

pqrs = [p, q, r, s]

print(max(pqrs)-min(pqrs))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect_left

N = int(input())
A = [int(s) for s in input().split()]
S = [0] + list(accumulate(A))

ic = bisect_left(S, S[N] * 1 / 4)
jc = bisect_left(S, S[N] * 2 / 4)
kc = bisect_left(S, S[N] * 3 / 4)

ans = float("inf")
for io in range(-100, 100):
    i = ic + io
    if not 0 < i < N:
        continue
    for jo in range(-100, 100):
        j = jc + jo
        if not i < j < N:
            continue
        for ko in range(-100, 100):
            k = kc + ko
            if not j < k < N:
                continue
            pqrs = [S[i], S[j] - S[i], S[k] - S[j], S[N] - S[k]]
            pqrs.sort()
            ans = min(ans, pqrs[-1] - pqrs[0])
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect_left

N = int(input())
A = [int(s) for s in input().split()]
S = [0] + list(accumulate(A))

ic = bisect_left(S, S[N] * 1 / 4)
jc = bisect_left(S, S[N] * 2 / 4)
kc = bisect_left(S, S[N] * 3 / 4)

ans = float("inf")
for io in range(-10, 10):
    i = ic + io
    if not 0 < i < N:
        continue
    for jo in range(-10, 10):
        j = jc + jo
        if not i < j < N:
            continue
        for ko in range(-10, 10):
            k = kc + ko
            if not j < k < N:
                continue
            pqrs = [S[i], S[j] - S[i], S[k] - S[j], S[N] - S[k]]
            pqrs.sort()
            ans = min(ans, pqrs[-1] - pqrs[0])
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect_left

N = int(input())
A = [int(s) for s in input().split()]
S = [0] + list(accumulate(A))

ic = bisect_left(S, S[N] * 1 / 4)
jc = bisect_left(S, S[N] * 2 / 4)
kc = bisect_left(S, S[N] * 3 / 4)

ans = float("inf")
for i in (ic - 4, ic - 3, ic - 2, ic - 1, ic, ic + 1, ic + 2, ic + 3):
    if not 0 < i < N:
        continue
    for j in (jc - 4, jc - 3, jc - 2, jc - 1, jc, jc + 1, jc + 2, jc + 3):
        if not i < j < N:
            continue
        for k in (kc - 4, kc - 3, kc - 2, kc - 1, kc, kc + 1, kc + 2, kc + 3):
            if not j < k < N:
                continue
            pqrs = [S[i], S[j] - S[i], S[k] - S[j], S[N] - S[k]]
            pqrs.sort()
            ans = min(ans, pqrs[-1] - pqrs[0])
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect_left

N = int(input())
A = [int(s) for s in input().split()]
S = [0] + list(accumulate(A))

ic = bisect_left(S, S[N] * 1 / 4)
jc = bisect_left(S, S[N] * 2 / 4)
kc = bisect_left(S, S[N] * 3 / 4)

ans = float("inf")
for i in (ic - 3, ic - 2, ic - 1, ic, ic + 1, ic + 2):
    if not 0 < i < N:
        continue
    for j in (jc - 3, jc - 2, jc - 1, jc, jc + 1, jc + 2):
        if not i < j < N:
            continue
        for k in (kc - 3, kc - 2, kc - 1, kc, kc + 1, kc + 2):
            if not j < k < N:
                continue
            pqrs = [S[i], S[j] - S[i], S[k] - S[j], S[N] - S[k]]
            pqrs.sort()
            ans = min(ans, pqrs[-1] - pqrs[0])
print(ans)

Submission status: Wrong Answer

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

a_sum = [a[0]]
for i in range(1, len(a)):
    a_sum.append(a_sum[-1] + a[i])

import bisect
def cut_half(x):
    cut = bisect.bisect_left(x, (x[0] + x[-1]) / 2)
    return [cut - 2, cut - 1, cut, cut + 1, cut + 2]

res = float('inf')
cut1 = cut_half(a_sum)
for i in cut1:
    a1 = a[:i]
    a2 = a[i:]

    if len(a1) > 1 and len(a2) > 1:
        a1_sum = a_sum[:i]
        a2_sum = [a2[0]]
        for ii in range(1, len(a2)):
            a2_sum.append(a2_sum[-1] + a[ii])


        cut2 = cut_half(a1_sum)
        cut3 = cut_half(a2_sum)

        for j in cut2:
            for k in cut3:
                b = a1[:j]
                c = a1[j:]
                d = a2[:k]
                e = a2[k:]

                if len(b) > 0 and len(c) > 0 and len(d) > 0 and len(e) > 0:
                    p = sum(b)
                    q = sum(c)
                    r = sum(d)
                    s = sum(e)
                    res = min(max([p, q, r, s]) - min([p, q, r, s]), res)

print(res)

Submission status: Wrong Answer

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

a_sum = [a[0]]
for i in range(1, len(a)):
    a_sum.append(a_sum[-1] + a[i])

import bisect
def cut_half(x):
    cut = bisect.bisect_left(x, x[-1] / 2)
    return [cut - 2, cut - 1, cut, cut + 1, cut + 2]

res = float('inf')
cut1 = cut_half(a_sum)
for i in cut1:
    a1 = a[:i]
    a2 = a[i:]

    if len(a1) > 1 and len(a2) > 1:
        a1_sum = a_sum[:i]
        a2_sum = [a2[0]]
        for ii in range(1, len(a2)):
            a2_sum.append(a2_sum[-1] + a[ii])


        cut2 = cut_half(a1_sum)
        cut3 = cut_half(a2_sum)

        for j in cut2:
            for k in cut3:
                b = a1[:j]
                c = a1[j:]
                d = a2[:k]
                e = a2[k:]

                if len(b) > 0 and len(c) > 0 and len(d) > 0 and len(e) > 0:
                    p = sum(b)
                    q = sum(c)
                    r = sum(d)
                    s = sum(e)
                    res = min(max([p, q, r, s]) - min([p, q, r, s]), res)

print(res)

Submission status: Wrong Answer

Solution code:
# 14:20
from bisect import bisect_left, bisect_right, bisect

def dprint(*a):
    pass

def solve(N, A):
    import time
    X = [0]*(N+1)
    s = 0
    for i in range(1, N+1):
        s += A[i-1]
        X[i] = s
    #print(A)
    L = [None] * (N+1)
    L[2] = 1
    for c in range(3,N+1):
        # Ll < Lr
        prevL = L[c-1]
        if abs(2*X[prevL] - X[c]) < abs(2*X[prevL+1] - X[c]):
            L[c] = prevL
        else:
            L[c] = prevL + 1
        #print("L[%d]=%d"%(c,L[c]), A[:L[c]], "\t", A[L[c]:c])

    R = [None] * (N+1)
    R[N-2] = N-1
    Xlast = X[-1]
    for c in range(N-3,1,-1):
        prevR = R[c+1]
        #  Rl < Rr
        if abs(2*X[prevR]-X[c] - Xlast) < abs(2*X[prevR-1]-X[c]- Xlast):
            R[c] = prevR
        else:
            R[c] = prevR - 1
        #print("R[%d]=%d"%(c,R[c]), A[c:R[c]], A[R[c]:], X[prevR]-X[c], X[-1]-X[prevR])

    m=X[-1]
    for c in range(2, N-1):
        l, r = L[c], R[c]
        S = X[l], X[c]-X[l], X[r]-X[c], X[-1]-X[r]
        score = max(S)-min(S)
        #print([l,c,r], score, A[0:l], A[l:c], A[c:r],A[r:])
        if score < m:
            m = score
    return m

def main():
    import time
    N = int(input())
    A = [int(x) for x in input().split()]
    print(solve(N, A))

#gen()
main()

Submission status: Wrong Answer

Solution code:
# 14:20
from bisect import bisect_left, bisect_right, bisect

def dprint(*a):
    pass

def solve(N, A):
    import time
    X = [0]*(N+1)
    s = 0
    for i in range(1, N+1):
        s += A[i-1]
        X[i] = s

    s = time.time()
    c = 2
    L = [None] * (N+1)
    L[c] = 1
    #dprint("L[%d]=%d"%(c,L[c]), A[:L[c]], A[L[c]:c])
    c += 1
    while c < N-1: # N
        # Ll < Lr
        prevL = L[c-1]
        if abs(X[prevL] - (X[c] - X[prevL])) < abs(X[prevL+1] - (X[c]-X[prevL+1])):
            L[c] = prevL
        else:
            L[c] = prevL + 1
        #dprint("L[%d]=%d"%(c,L[c]), A[:L[c]], "\t", A[L[c]:c])
        c+=1
    #print(time.time()-s)

    s = time.time()
    c = N-2
    R = [None] * (N+1)
    R[c] = N-1
    #dprint("R[%d]=%d"%(c,R[c]), A[c:R[c]], A[R[c]:])
    c -= 1
    while 1 < c: # N
        prevR = R[c+1]

        #  Rl < Rr
        if abs((X[prevR]-X[c]) - (X[-1] - X[prevR])) < abs((X[prevR-1]-X[c]) - (X[-1] - X[prevR-1])):
            R[c] = prevR
        else:
            # Rl > Rr
            R[c] = prevR-1
        #dprint("R[%d]=%d"%(c,R[c]), A[c:R[c]], A[R[c]:], X[prevR]-X[c], X[-1]-X[prevR])
        c-=1
    #print(time.time()-s)

    s = time.time()
    l,c,r=1,2,3
    S = X[l], X[c]-X[l], X[r]-X[c], X[-1]-X[r]
    m = max(S)-min(S)
    for c in range(2, N-1):
        l, r = L[c], R[c]
        S = X[l], X[c]-X[l], X[r]-X[c], X[-1]-X[r]
        score = max(S)-min(S)
        #dprint([l,c,r], score, A[0:l], A[l:c], A[c:r],A[r:])
        if score < m:
            m = score
    #print(time.time()-s)
            
    return m

def main():
    import time
    N = int(input())
    A = [int(x) for x in input().split()]
    print(solve(N, A))

def gen():
    import itertools
    N = 2 * 10**5
    with open("a", "w") as f:
        print(N, file=f)
        print(" ".join(str(x) for x in itertools.repeat(1, N)),file=f)
#gen()
main()

Submission status: Wrong Answer

Solution code:
# 14:20
from bisect import bisect_left, bisect_right, bisect

def dprint(*a):
    pass

def solve(N, A):
    X = [0]*(N+1)
    s = 0
    for i in range(1, N+1):
        s += A[i-1]
        X[i] = s

    c = 2
    L = [None] * (N+1)
    L[c] = 1
    dprint("L[%d]=%d"%(c,L[c]), A[:L[c]], A[L[c]:c])
    c += 1
    while c < N-1: # N
        # Ll < Lr
        prevL = L[c-1]
        if abs(X[prevL] - (X[c] - X[prevL])) < abs(X[prevL+1] - (X[c]-X[prevL+1])):
            L[c] = prevL
        else:
            L[c] = prevL + 1
        dprint("L[%d]=%d"%(c,L[c]), A[:L[c]], "\t", A[L[c]:c])
        c+=1

    c = N-2
    R = [None] * (N+1)
    R[c] = N-1
    dprint("R[%d]=%d"%(c,R[c]), A[c:R[c]], A[R[c]:])
    c -= 1
    while 1 < c: # N
        prevR = R[c+1]

        #  Rl < Rr
        if abs((X[prevR]-X[c]) - (X[-1] - X[prevR])) < abs((X[prevR-1]-X[c]) - (X[-1] - X[prevR-1])):
            R[c] = prevR
        else:
            # Rl > Rr
            R[c] = prevR-1
        dprint("R[%d]=%d"%(c,R[c]), A[c:R[c]], A[R[c]:], X[prevR]-X[c], X[-1]-X[prevR])
        c-=1

    l,c,r=1,2,3
    S = X[l], X[c]-X[l], X[r]-X[c], X[-1]-X[r]
    m = max(S)-min(S)
    for c in range(2, N-1):
        l, r = L[c], R[c]
        S = X[l], X[c]-X[l], X[r]-X[c], X[-1]-X[r]
        score = max(S)-min(S)
        dprint([l,c,r], score, A[0:l], A[l:c], A[c:r],A[r:])
        if score < m:
            m = score
            
    return m

def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    print(solve(N, A))

def gen():
    N = 2 * 10**5
    with open("a", "w") as f:
        print(N, file=f)
        print(" ".join(str(x) for x in range(1, N+1)),file=f)

#gen()
main()

Submission status: Wrong Answer

Solution code:
INF = float('inf')
from bisect import bisect
N = int(input())
A = list(map(int,input().split()))
S = [0]*N
for i in range(N):
    S[i] = S[i-1]+A[i]

ans = INF
for i in range(2,N-2):
    j = bisect(S,S[i-1]/2)
    k = bisect(S,(S[-1]+S[i-1])/2)
    for p in {j-1,min(j,i-2)}:
        for q in {max(k-1,i),min(k,N-2)}:
            a,b,c,d = S[p],S[i-1]-S[p],S[q]-S[i-1],S[-1]-S[q]
            m = min(a,b,c,d)
            M = max(a,b,c,d)
            ans = min(ans,M-m)

print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
from bisect import bisect
N = int(input())
A = list(map(int,input().split()))
S = [0]*N
for i in range(N):
    S[i] = S[i-1]+A[i]

ans = INF
for i in range(2,N-2):
    j = bisect(S,S[i-1]/2)
    k = bisect(S,(S[-1]+S[i-1])/2)
    for p in {j-1,min(j,i-2)}:
        for q in {k-1,min(k,N-2)}:
            a,b,c,d = S[p],S[i-1]-S[p],S[q]-S[i-1],S[-1]-S[q]
            m = min(a,b,c,d)
            M = max(a,b,c,d)
            ans = min(ans,M-m)

print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
from bisect import bisect
N = int(input())
A = list(map(int,input().split()))
S = [0]*N
for i in range(N):
    S[i] = S[i-1]+A[i]

ans = INF
for i in range(2,N-2):
    l = S[:i]
    r = S[i:]
    j = bisect(S,S[i-1]/2)
    k = bisect(S,(S[-1]+S[i-1])/2)
    for p in {j-1,min(j,i-2)}:
        for q in {k-1,min(k,N-2)}:
            a,b,c,d = S[p],S[i-1]-S[p],S[q]-S[i-1],S[-1]-S[q]
            m = min(a,b,c,d)
            M = max(a,b,c,d)
            ans = min(ans,M-m)

print(ans)

Submission status: Wrong Answer

Solution code:
def argmin(a_s, reverse):
  a_min = min(a_s)
  if(not reverse):
    return a_s.index(a_min)
  else:
    a_s = a_s[::-1]
    return len(a_s) - 1 - a_s.index(a_min)
    
    
n = int(input())
a_s = [int(v) for v in input().split()]
#print(a_s)

total = sum(a_s)
ends = [1, 2, 3, n ]
s = [a_s[0], a_s[1], a_s[2], total - sum(a_s[:3])]

cand = max(s) - min(s)

#print("ends:{}".format(ends))
#print("   s:{}".format(s))
while True:
  s_argmin = argmin(s, reverse=False)
  if s_argmin != 3:
    mv = a_s[ends[s_argmin]]
    ends[s_argmin] += 1
    s[s_argmin] += mv
    s[s_argmin + 1] -=mv
    #print("ends:{}".format(ends))
    #print("   s:{}".format(s))
    cand = min(cand, max(s) - min(s))
  else:
    break

#print("")    
while True:
  s_argmin = argmin(s, reverse=True)
  if s_argmin != 0:
    mv = a_s[ends[s_argmin - 1] - 1]
    ends[s_argmin - 1] -= 1
    s[s_argmin] += mv
    s[s_argmin - 1] -=mv
    #print("ends:{}".format(ends))
    #print("   s:{}".format(s))
    cand = min(cand, max(s) - min(s))
  else:
    break
    
ans = cand    
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	N = int(input())
	A = list(map(int, input().split(" ")))
	
	a_sum = []
	for i, val in enumerate(A):
		if i == 0:
			a_sum.append(val)
			continue
		a_sum.append(val + a_sum[i-1])
		
	ans = -1
	for i in range(2, N-1):
		L = A[:i]
		L_sum = a_sum[:i]
		R = A[i:]
		R_sum = a_sum[i:]
		
		# L
		End = L_sum[-1]
		Start = L_sum[0]
		Half = End // 2
		L_part = bisect_right(L_sum, Half)
		if L_part == 0:
			L_part += 1
		
		if len(L_sum) != 2:
			if L_part == 1:
				a = End - L_sum[L_part-1]
				b = End - L_sum[L_part]
				
				if b <= a:
					L_part += 1
			elif L_part == len(L_sum)-1:
				a = End - L_sum[L_part-1]
				b = End - L_sum[L_part-2]
				
				if b <= a:
					L_part -= 1
			else:
				a = End - L_sum[L_part-1]
				b = End - L_sum[L_part-2]
				c = End - L_sum[L_part]
				
				if b <= a and b <= c:
					L_part += 1
				elif c <= a and c <= b:
					L_part -= 1
		
		# R
		End = R_sum[-1]
		Start = R_sum[0]
		Half = End // 2
		R_part = bisect_right(R_sum, Half)
		if R_part == 0:
			R_part += 1
		
		if len(R_sum) != 2:
			if R_part == 1:
				a = End - R_sum[R_part-1]
				b = End - R_sum[R_part]
				
				if b <= a:
					R_part += 1
			elif R_part == len(R_sum)-1:
				a = End - R_sum[R_part-1]
				b = End - R_sum[R_part-2]
				
				if b <= a:
					R_part -= 1
			else:
				a = End - R_sum[R_part-1]
				b = End - R_sum[R_part-2]
				c = End - R_sum[R_part]
				
				if b <= a and b <= c:
					R_part += 1
				elif c <= a and c <= b:
					R_part -= 1
		R_part += i
		
		PP = a_sum[L_part-1]
		QQ = a_sum[i-1] - a_sum[L_part-1]
		RR = a_sum[R_part-1] - a_sum[i-1]
		SS = a_sum[-1] - a_sum[R_part-1]
		
		tmp = max(PP,QQ,RR,SS) - min(PP,QQ,RR,SS)
		if ans == -1 or ans > tmp:
			ans = tmp
	
	print(ans)
	
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
X=A[:2]
Y=A[2:]
a=A[0]+A[1]
b=sum(A)-a
tmp=abs(a-b)
for i in range(2,N-2):
    if abs(a+A[i])-(b-A[i])<tmp:
        X=A[:i+1]
        Y=A[i+1:]
        a+=A[i]
        b-=A[i]
        tmp=abs(a-b)
    else:
        break
x,y=len(X),len(Y)
#print(X)
#print(Y)
#print(a,b)
P=X[:1]
Q=X[1:]
a1=X[0]
b1=sum(X)-a1
tmp=abs(a1-b1)

for i in range(1,x-1):
    if abs((a1+X[i])-(b1-X[i]))<tmp:
        P=X[:i+1]
        Q=X[i+1:]
        a1+=X[i]
        b1-=X[i]
        tmp=abs(a1-b1)
    else:
        break
#print(P)
#print(Q)
#print(a1,b1)
R=Y[:1]
S=Y[1:]
a2=Y[0]
b2=sum(Y)-a2
tmp=abs(a2-b2)
for i in range(1,y-1):
    if abs((a2+Y[i])-(b2-Y[i]))<tmp:
        R=Y[:i+1]
        S=Y[i+1:]
        a2+=Y[i]
        b2-=Y[i]
        tmp=abs(a2-b2)
    else:
        break
#print(R)
#print(S)
#print(a2,b2)
#print(a1,b1,a2,b2)
l=[a1,b1,a2,b2]
l.sort()
#print(l[-1]-l[0])
ans=l[-1]-l[0]
if len(R)>1:
    l2=[a1,b1+R[0],a2-R[0],b2]
    #print(l2)
    l2.sort()
    #print(l2[-1]-l2[0])
    ans=min(ans,l2[-1]-l2[0])
if len(Q)>1:

    l3=[a1,b1-Q[-1],a2+Q[-1],b2]
    #print(l3)
    l3.sort()
    #print(l3[-1]-l3[0])
    ans=min(ans,l3[-1]-l3[0])
print(ans)

Submission status: Wrong Answer

Solution code:
# 分からん
import itertools

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

def divide(li): #li(累積和)を均等に分けるretを探す
  d = 10**10
  ret = 0
  for i in range(len(li)):
    dif = abs(li[i] - (li[-1] - li[i]))
    if dif < d:
      d = dif
      ret = i
  return ret

ans = 10**10
for i in range(n-1):
  l = a_sum[:i+1]
  r = a_sum[i+1:]
  ld = divide(l)
  rd = divide(r) + i + 1
  MX = max(a_sum[ld],a_sum[i]-a_sum[ld],a_sum[rd]-a_sum[i],a_sum[-1]-a_sum[rd])
  MN = min(a_sum[ld],a_sum[i]-a_sum[ld],a_sum[rd]-a_sum[i],a_sum[-1]-a_sum[rd])
  A = MX - MN
  if A < ans:
    print(ld,i,rd)
    print(a_sum[ld],a_sum[i]-a_sum[ld],a_sum[rd]-a_sum[i],a_sum[-1]-a_sum[rd])
    ans = A

print(ans)
#73

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
import math

def main():
	N = int(input())
	A = list(map(int, input().split(" ")))
	
	a_sum = []
	for i, val in enumerate(A):
		if i == 0:
			a_sum.append(val)
			continue
		a_sum.append(val + a_sum[i-1])
		
	ans = -1
	for i in range(2, N-1):
		L = A[:i]
		L_sum = a_sum[:i]
		R = A[i:]
		R_sum = a_sum[i:]
		
		# L
		End = L_sum[-1]
		Start = L_sum[0]
		L_part = 0
		for j in range(1, len(L_sum)-1):
			Start += L_sum[j]
			L_part += 1
			if Start > End:
				L_part -= 1
				break
			
		# R
		End = R_sum[-1]
		Start = R_sum[0]
		R_part = 0
		for j in range(1, len(R_sum)-1):
			Start += R_sum[j]
			R_part += 1
			if Start > End:
				R_part -= 1
				break
			
		P = a_sum[L_part]
		Q = a_sum[i-1] - P
		R = a_sum[R_part + i] - a_sum[i-1]
		S = a_sum[-1] - a_sum[R_part + i]
		
		tmp = max(P,Q,R,S) - min(P,Q,R,S)
		if ans == -1 or ans > tmp:
			ans = tmp
	
	print(ans)
	
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
def solve(string):
    n, *a = map(int, string.split())
    ans = n * 10**9
    lc = 1
    rc = 3
    for c in range(2, n - 2):
        lls_c = sum(a[:lc])
        lrs_c = sum(a[lc:c])
        rls_c = sum(a[c:rc])
        rrs_c = sum(a[rc:])
        # print("first: %d %d %d" % (lc, c, rc))
        while True:
            if lc == c - 1:
                break
            d_c = max(lls_c, lrs_c) - min(lls_c, lrs_c)
            lls_n = lls_c + a[lc]
            lrs_n = lrs_c - a[lc]
            d_n = max(lls_n, lrs_n) - min(lls_n, lrs_n)
            # print("%d %d" % (lls_c, lrs_c))
            # print("%d %d" % (lls_n, lrs_n))
            # print("%d %d" % (d_c, d_n))
            if d_n < d_c:
                lls_c, lrs_c = lls_n, lrs_n
                lc += 1
            else:
                break
        # print("second: %d %d %d" % (lc, c, rc))
        while True:
            if rc == n:
                break
            d_c = max(rls_c, rrs_c) - min(rls_c, rrs_c)
            rls_n = rls_c + a[rc]
            rrs_n = rrs_c - a[rc]
            d_n = max(rls_n, rrs_n) - min(rls_n, rrs_n)
            if d_n < d_c:
                rls_c, rrs_c = rls_n, rrs_n
                rc += 1
            else:
                break
        # print("third: %d %d %d" % (lc, c, rc))
        ans = min(ans, max([lls_c, lrs_c, rls_c, rrs_c]) - min([lls_c, lrs_c, rls_c, rrs_c]))
    # print(ans)
    return str(ans)


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Wrong Answer

Solution code:
def solve(string):
    n, *a = map(int, string.split())
    ans = n * 10**9
    lc = 1
    rc = 3
    for c in range(2, n - 2):
        while True:
            lls_c = sum(a[:lc])
            lrs_c = sum(a[lc:c])
            d_c = max(lls_c, lrs_c) - min(lls_c, lrs_c)
            lls_n = sum(a[:lc + 1])
            lrs_n = sum(a[lc + 1:c])
            d_n = max(lls_n, lrs_n) - min(lls_n, lrs_n)
            if d_n < d_c:
                lc += 1
                # import pdb; pdb.set_trace()
            else:
                break
        while True:
            rls_c = sum(a[c:rc])
            rrs_c = sum(a[rc:])
            d_c = max(rls_c, rrs_c) - min(rls_c, rrs_c)
            rls_n = sum(a[c:rc + 1])
            rrs_n = sum(a[rc + 1:])
            d_n = max(rls_n, rrs_n) - min(rls_n, rrs_n)
            if d_n < d_c:
                rc += 1
                # import pdb; pdb.set_trace()
            else:
                break
        ans = min(ans, max([lls_c, lrs_c, rls_c, rrs_c]) - min([lls_c, lrs_c, rls_c, rrs_c]))
    return str(ans)


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Wrong Answer

Solution code:
#!/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)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, A: "List[int]"):
    acc = list(accumulate(A))
    li = 1
    rdiff = float('inf')
    ri = 0
    for i in range(3, len(acc)):
        d = acc[-1] - acc[i-1]
        c = acc[i-1] - acc[1]
        if abs(d - c) < rdiff:
            rdiff = abs(d -c)
            ri = i
    ci = 2

    def _g(li, ci, ri):
        a = acc[li - 1]
        b = acc[ci - 1] - acc[li-1]
        c = acc[ri - 1] - acc[ci - 1]
        d = acc[-1] - acc[ri - 1]
        cr = max([a, b, c, d]) - min([a, b, c, d])
        return cr

    def _f(h, m, l):
        bbb = acc[l] if 0 <= l else 0
        return abs((acc[h - 1] - acc[m-1]) - (acc[m - 1] - bbb))
  
    r = _g(li, ci, ri)
    for i in range(3, len(acc) - 1):
        while _f(i, (li+1), -1) <  _f(i, li, -1):
            li += 1
        while _f(len(acc), (ri+1), i) <  _f(len(acc), ri, i):
            ri += 1
        cr = _g(li, i, ri)
        if cr < r:
            r = cr
    return r


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, A: "List[int]"):
    acc = list(accumulate(A))
    li = 1
    rdiff = float('inf')
    ri = 0
    for i in range(3, len(acc)):
        d = acc[-1] - acc[i-1]
        c = acc[i-1] - acc[1]
        if abs(d - c) < rdiff:
            rdiff = abs(d -c)
            ri = i
    ci = 2

    def _g(li, ci, ri):
        a = acc[li - 1]
        b = acc[ci - 1] - acc[li-1]
        c = acc[ri - 1] - acc[ci - 1]
        d = acc[-1] - acc[ri - 1]
        cr = max([a, b, c, d]) - min([a, b, c, d])
        return cr

    def _f(h, m, l):
        bbb = acc[l] if 0 <= l else 0
        return abs((acc[h - 1] - acc[m-1]) - (acc[m - 1] - bbb))
  
    r = _g(li, ci, ri)
    for i in range(3, len(acc) - 2):
        while _f(i, (li+1), -1) <  _f(i, li, -1):
            li += 1
        while _f(len(acc), (ri+1), i) <  _f(len(acc), ri, i):
            ri += 1
        cr = _g(li, i, ri)
        if cr < r:
            r = cr
    return r


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
A = np.array([int(x) for x in input().split()],dtype=np.int64)
A = list(A.cumsum())
S = A[-1]

answer = S

# index は最後に回収する番号で管理
B = 0
C = 1
D = 2

for C in range(1,N-2):
  SB = A[B]
  SC = A[C] - A[B]
  left_score = abs(SB - SC)
  # BCの境界の調整
  while True:
    B_ = B+1
    SB_ = A[B+1]
    SC_ = A[C] - SB_
    x = abs(SB_ - SC_)
    if left_score > x:
      B,SB,SC,left_score = B_,SB_,SC_,x
      continue
    break
  D = max(D,C+1)
  SD = A[D]-A[C]
  SE = S - A[D]
  right_score = abs(SD-SE)
  # DEの境界の調整
  while True:
    D_ = D+1
    SD_ = A[D_] - A[C]
    SE_ = A[-1] - A[D_]
    x = abs(SD_ - SE_)
    if right_score > x:
      D,SD,SE,left_score = D_,SD_,SE_,x
      continue
    break
  score = max(SB,SC,SD,SE) - min(SB,SC,SD,SE)
  answer = min(answer,score)
  
print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
A = np.array([int(x) for x in input().split()],dtype=np.int64)
A = list(A.cumsum())
S = A[-1]

answer = S

# index は最後に回収する番号で管理
B = 0
C = 1
D = 2

for C in range(1,N-2):
  SB = A[B]
  SC = A[C] - A[B]
  left_score = abs(SB - SC)
  # BCの境界の調整
  while True:
    B_ = B+1
    SB_ = A[B+1]
    SC_ = A[C] - SB_
    x = abs(SB_ - SC_)
    if left_score > x:
      B,SB,SC,left_score = B_,SB_,SC_,x
      continue
    break
  SD = A[D]-A[C]
  SE = S - A[D]
  right_score = abs(SD-SE)
  # DEの境界の調整
  while True:
    D_ = D+1
    SD_ = A[D_] - A[C]
    SE_ = A[-1] - A[D_]
    x = abs(SD_ - SE_)
    if right_score > x:
      D,SD,SE,left_score = D_,SD_,SE_,x
      continue
    break
  score = max(SB,SC,SD,SE) - min(SB,SC,SD,SE)
  answer = min(answer,score)
  
print(answer)

Submission status: Wrong Answer

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

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

b_index = N // 2

def regret(A, b):
    result = 0
    for a in A:
        result += abs(a-b)
    return result

print(min(regret(A, A[b_index]), regret(A, A[b_index+1])))

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()
B = list(accumulate(A))

l, c, r = 0, 1, 2
P = sum(A[:1])
Q = sum(A[l:c])
R = sum(A[c:r])
S = sum(A[r:])

ans = INF

for c in range(1, N-1):
	while True:
		if abs(P-Q) < abs((P+A[l])-(Q-A[l])):
			break
		if l == c-1:
			break
		P += A[l]
		Q -= A[l]
		l += 1

	while True:
		if abs(R-S) < abs((R+A[r])-(S-A[r])):
			break
		if r == N-1:
			break
		R += A[r]
		S -= A[r]
		r += 1

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

	Q += A[c]
	R -= A[c]

print(ans)