Problem:


Score : 600 points

Problem Statement

Snuke has an integer sequence A of length N.

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

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

Constraints

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

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

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

Sample Input 1

5
3 2 4 1 2

Sample Output 1

2

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

Sample Input 2

10
10 71 84 33 6 47 23 25 52 64

Sample Output 2

36

Sample Input 3

7
1 2 3 1000000000 4 5 6

Sample Output 3

999999994



Sample input:
5
3 2 4 1 2


Sample output:
2

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())# your code goes here
a = input().split()
sum = 0
r = 0
v = np.zeros(n)
for i in range(n):
	v[i] = int(a[i])
for i in range(n-1):
	for j in range(n-1):
		for k in range(n-1):
			b = np.zeros(4)
			b[0] = np.sum(v[:i])
			b[1] = np.sum(v[i:j])
			b[2] = np.sum(v[j:k])
			b[3] = np.sum(v[k:])
			min = np.min(b)
			max = np.max(b)
			if(i == 0 and j == 0 and k == 0):
				r = max - min
			elif(max-min<r):
				r = max-min
print(int(r))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
sumA=[0]
for a in A:
    sumA+=[sumA[-1]+a]
res=float('inf')
for z in range(N//4+2):
    if res==0:break
    for x in range(2,N-2-z):
        a=sumA[x+z+1]-sumA[x]
        Sb,Sc=sumA[x],sumA[N]-sumA[x+z+1]
        s,t=0,Sb
        u,v=sorted([Sc,a])
        for k,b in enumerate(A[:x-1]):
            s,t=[s+b,t-b]
            tmp=max([s,t,v])-min([s,t,u])
            if tmp<res:res=tmp
            if res==0:break
        if res==0:break
        s,t=0,Sc
        u,v=sorted([Sb,a])
        for k,c in enumerate(A[x+1+z:-1]):
            s,t=[s+c,t-c]
            tmp=max([s,t,v])-min([s,t,u])
            if tmp<res:res=tmp
            if res==0:break
print(res)

Submission status: Wrong Answer

Solution code:
from statistics import *

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

ss = sum(a)
s = ss / 4

b1 = 0
j1 = 0

while b1 < s:
    b1 += a[j1]
    j1 += 1

b3 = 0
j3 = n - 1

while b3 < s:
    b3 += a[j3]
    j3 -= 1

b2 = 0
j2 = j1 + 1

while b2 < 2*s-b1:
    b2 += a[j2]
    j2 += 1


sum1_1 = b1
sum1_2 = b2
sum1_3 = ss - b1 - b2 - b3
sum1_4 = b3

sumlist1 = sorted([sum1_1, sum1_2, sum1_3, sum1_4])
range1 = sumlist1[3] - sumlist1[0]

sum2_1 = sum1_1 - a[j1-1]
sum2_2 = sum1_2 + a[j1-1]
sumlist2 = sorted([sum2_1, sum2_2, sum1_3, sum1_4])
range2 = sumlist2[3] - sumlist2[0]

sum3_3 = sum1_3 + a[j3+1]
sum3_4 = sum1_4 - a[j3+1]
sumlist3 = sorted([sum1_1, sum1_2, sum3_3, sum3_4])
range3 = sumlist3[3] - sumlist3[0]

sumlist4 = sorted([sum2_1, sum2_2, sum3_3, sum3_4])
range4 = sumlist4[3] - sumlist4[0]

sum5_2 = sum1_2 - a[j2-1]
sum5_3 = sum1_3 + a[j2-1]
sumlist5 = sorted([sum1_1, sum5_2, sum5_3, sum1_4])
range5 = sumlist5[3] - sumlist5[0]

sum6_1 = sum1_1 - a[j1-1]
sum6_2 = sum5_2 + a[j1-1]
sumlist6 = sorted([sum6_1, sum6_2, sum5_3, sum1_4])
range6 = sumlist6[3] - sumlist6[0]

sum7_3 = sum5_3 + a[j3+1]
sum7_4 = sum1_4 - a[j3+1]
sumlist7 = sorted([sum1_1, sum5_2, sum7_3, sum7_4])
range7 = sumlist7[3] - sumlist7[0]

sumlist8 = sorted([sum6_1, sum6_2, sum7_3, sum7_4])
range8 = sumlist8[3] - sumlist8[0]

print(min([range1,range2, range3, range4, range5, range6, range7,range8]))

Submission status: Wrong Answer

Solution code:
import itertools

def getMinPartition(accB, offset=0):
  value = (accB[-1] - offset)/2 + offset
  index = binary_search(accB, value)
  # print('index ' + str(index))
  return return_min(accB, index, offset)

def calculate_min(accB, index, offset):
  return abs(accB[-1] - 2 * accB[index] + offset)

def return_min(accB, index, offset):
  if calculate_min(accB, index, offset) < calculate_min(accB, index-1, offset):
    return [accB[index] - offset, accB[-1] - accB[index]]
  return [accB[index-1] - offset, accB[-1] - accB[index-1]]

def binary_search(accB, value):
  N = len(accB)
  lowerId = 0
  upperId = N
  while lowerId+1 != upperId:
    midId = int((lowerId + upperId)/2)
    if(accB[midId] < value):
      lowerId = midId
    else:
      upperId = midId
  return lowerId

def calculate(accA, i):
  # print(i)
  P, Q = getMinPartition(accA[:i])
  R, S = getMinPartition(accA[i:], accA[i-1])
  # print('P, Q, R, S: {}, {} ,{} ,{}'.format(P, Q, R, S))
  return max([P, Q, R, S]) - min([P, Q, R, S])
  

if __name__=="__main__":
  N = int(input())
  A = list(map(int, input().split()))
  accA = list(itertools.accumulate(A))
  optList = [calculate(accA, i) for i in range(2, N-1)]
  print(min(optList))

Submission status: Wrong Answer

Solution code:
def main():
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	def ano_helper(BCDE):
		BCDE = BCDE + [s - sum(BCDE)]
		BCDE.sort()
		return abs(BCDE[-1] - BCDE[0])
	def helper(BCDEs, inds):
		if len(BCDEs[0]) == 4:
			return BCDEs
		ret_BCDEs = []
		ret_inds = []
		for candidate in range(len(BCDEs)):
			BCDE = BCDEs[candidate]
			ind = inds[candidate]
			if ind < N:
				ave = sum(A[ind:]) / (5 - len(BCDE))
				temp = A[ind]
				ind += 1
				while ind < N and temp + A[ind] <= ave:
					temp += A[ind]
					ind += 1
				ret_BCDEs.append(BCDE + [temp])
				ret_inds.append(ind)
				if ind >= 1 and ind <= N - 1:
					ret_BCDEs.append(BCDE + [temp - A[ind - 1]])
					ret_inds.append(ind - 1)
				if ind <= N - 1:
					ret_BCDEs.append(BCDE + [temp + A[ind]])
					ret_inds.append(ind + 1)
		return helper(ret_BCDEs, ret_inds)
	print(sorted([ano_helper(i[1:]) for i in helper([[0]], [0])])[0])
	return 0
	#BCDE = []
	#ind = 0
	#su = []
	#tempBCDE = [[]]
	#while len(BCDE[-1]) < 4:
	#	temp = 0
	#	ret = []
	#	while temp < (s - su) / (4 - len(BCDE)):
	#		te = A[ind]
	#		temp += te
	#		ret.append(te)
	#		su += te
	#		ind += 1
	#	tempBCDE.append(ret)
	#print(BCDE)
main()

Submission status: Wrong Answer

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

SUM=sum(A)

left=0
i=0
while left<SUM/4:
    left+=A[i]
    i+=1
    print(i,left)

right=0
j=N-1
while right<SUM/4:
    right+=A[j]
    j-=1
    print(j,right)


    
def middlecut(i,j):
    left=sum(A[:i])
    right=sum(A[j:])
    ANS=10**16

    for k in range(i,j):
        midle=sum(A[i:k])
        midri=sum(A[k:j])

        if ANS>max(left,right,midle,midri)-min(left,right,midle,midri):
            ANS=max(left,right,midle,midri)-min(left,right,midle,midri)

    return ANS


ANS=10**16
for l in range(max(0,i-6),min(N,i+6)):
    for m in range(max(0,j-6),min(N,j+6)):
        ANS=min(ANS,middlecut(l,m))

print(ANS)

Submission status: Wrong Answer

Solution code:
def main():
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	def ano_helper(BCDE):
		BCDE = BCDE + [s - sum(BCDE)]
		BCDE.sort()
		return abs(BCDE[-1] - BCDE[0])
	def helper(BCDEs, inds):
		if len(BCDEs[0]) == 4:
			return BCDEs
		ret_BCDEs = []
		ret_inds = []
		for candidate in range(len(BCDEs)):
			BCDE = BCDEs[candidate]
			ind = inds[candidate]
			if ind < N:
				ave = sum(A[ind:]) / (5 - len(BCDE))
				temp = A[ind]
				ind += 1
				while ind < N and temp + A[ind] < ave:
					temp += A[ind]
					ind += 1
				ret_BCDEs.append(BCDE + [temp])
				ret_inds.append(ind)
				if ind >= 1 and ind <= N - 1:
					ret_BCDEs.append(BCDE + [temp - A[ind - 1]])
					ret_inds.append(ind - 1)
				if ind <= N - 1:
					ret_BCDEs.append(BCDE + [temp + A[ind]])
					ret_inds.append(ind + 1)
		return helper(ret_BCDEs, ret_inds)
	print(sorted([ano_helper(i[1:]) for i in helper([[0]], [0])])[0])
	return 0
	#BCDE = []
	#ind = 0
	#su = []
	#tempBCDE = [[]]
	#while len(BCDE[-1]) < 4:
	#	temp = 0
	#	ret = []
	#	while temp < (s - su) / (4 - len(BCDE)):
	#		te = A[ind]
	#		temp += te
	#		ret.append(te)
	#		su += te
	#		ind += 1
	#	tempBCDE.append(ret)
	#print(BCDE)
main()

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(i) for i in input().split()]

csum = [0]

for a in A:
    csum.append(csum[-1] + a)

def csum_(a, b):
    return csum[b] - csum[a]

def search(ok, ng, n, m):
    if abs(ok-ng) <= 1:
            return ok
    mid = (ok+ng) // 2
    if csum_(m, mid) < csum_(mid, n):
        return search(mid, ng, n, m)
    else:
        return search(ok, mid, n, m)

c = search(1, n, n, 0)  #中央のindex
d = search(1, c, c, 0)
f = search(c, n, n, c)

fans = []

for c in [c-1, c, c+1]:
    for d in [max(d-1, 0), d, d+1]:
        for f in [f-1, f, min(f+1, n)]:
            ans = []

            ans.append(csum_(0, d))
            ans.append(csum_(d, c))
            ans.append(csum_(c, f))
            ans.append(csum_(f, n))

            fans.append(max(ans) - min(ans))

print(min(fans))

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product
N = int(input())
A = np.array(list(map(int, input().split())), dtype= int)
X = A.sum()
p1, p2, p3 = X/4, X/2, 3*X/4
A1 = np.cumsum(A)
q1 = np.argmax(A1*(A1<p1))
q2 = np.argmax(A1*(A1<p2))
q3 = np.argmax(A1*(A1<p3))
mincost = -1
for r1, r2, r3 in product((q1-1,q1, q1+1), (q2-1,q2, q2+1), (q3-1,q3, q3+1)):
    P = A1[r1]
    Q = A1[r2]-P
    R = A1[r3]-P-Q
    S = X - P - Q - R
    cost = max(P,Q,R,S) - min(P,Q,R,S)
    mincost = cost if mincost < 0 else min(mincost, cost)
print(mincost)

Submission status: Wrong Answer

Solution code:
def main():
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	def ano_helper(BCDE):
		BCDE = BCDE + [s - sum(BCDE)]
		BCDE.sort()
		return abs(BCDE[-1] - BCDE[0])
	def helper(BCDEs, inds):
		if len(BCDEs[0]) == 4:
			return BCDEs
		ret_BCDEs = []
		ret_inds = []
		for candidate in range(len(BCDEs)):
			BCDE = BCDEs[candidate]
			ind = inds[candidate]
			if ind < N:
				ave = sum(A[ind:]) / (5 - len(BCDE))
				temp = A[ind]
				ind += 1
				while ind < N and temp + A[ind] < ave:
					temp += A[ind]
					ind += 1
				ret_BCDEs.append(BCDE + [temp])
				ret_inds.append(ind)
				if ind >= 1 and ind <= N - 1:
					ret_BCDEs.append(BCDE + [temp - A[ind]])
					ret_inds.append(ind - 1)
				if ind <= N - 1:
					ret_BCDEs.append(BCDE + [temp + A[ind]])
					ret_inds.append(ind + 1)
		return helper(ret_BCDEs, ret_inds)
		
	print(sorted([ano_helper(i[1:]) for i in helper([[0]], [0])])[0])
	return 0
	#BCDE = []
	#ind = 0
	#su = []
	#tempBCDE = [[]]
	#while len(BCDE[-1]) < 4:
	#	temp = 0
	#	ret = []
	#	while temp < (s - su) / (4 - len(BCDE)):
	#		te = A[ind]
	#		temp += te
	#		ret.append(te)
	#		su += te
	#		ind += 1
	#	tempBCDE.append(ret)
	#print(BCDE)
main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

n = int(input())
xs = [int(x) for x in input().split()]

ys = list(accumulate(xs))

def sums(pos):
    i, j, k = pos
    return ys[i], ys[j] - ys[i], ys[k] - ys[j], ys[-1] - ys[k]

def maxmin(pos):
    s = sums(pos)
    return max(s)-min(s)

options = ((1,0,0), (1,1,0), (0,0,-1), (0,-1,-1), (0,1,0), (0,-1,0))

current = 0, len(xs)//2 - 1, len(xs)-2
v = maxmin(current)
past = set([current])

while True:
    moves = (tuple(x+y for x, y in zip(current, option)) for option in options)
    best = min(moves, key=lambda x:maxmin(x))
    if maxmin(best) <= v and best not in past:
        current, v = best, maxmin(best)
        past.add(best)
    else:
        break

print(v)

Submission status: Wrong Answer

Solution code:
N=int(input())
 
A=list(map(int,input().split()))
 
fourdivide=sum(A)//4
P=Q=R=S=0
Pflag=Qflag=Rflag=0
Pindex=Qindex=Rindex=0
Ppre=Qpre=Rpre=Spre=0
answer=10**9

def intr(a,b,c):
	global answer
	d=sum(A)-a-b-c
	answer=min(answer,max(a,b,c,d)-min(a,b,c,d))

for i in range(N):
	if Pflag==0 and i<=N-4:
		P+=A[i]
		if P>=fourdivide:
			Pflag=1
			Pindex=i
			if i!=0:
				Ppre=P-A[i]
	elif Qflag==0 and i<=N-3:
		Q+=A[i]
		if Q>=fourdivide:
			Qflag=1
			Qindex=i
			Qpre=Q-A[i]
	elif Rflag==0 and i<=N-2:
		R+=A[i]
		if R>=fourdivide:
			Rflag=1
			Rindex=i
			Rpre=R-A[i]            

intr(P,Q,R)
if Rpre!=0:
	intr(P,Q,Rpre)
Rflag=0
QpreR=QpreRpre=0

for i in range(Qindex,N):
	if Rflag==0 and i<=N-2:
		QpreR+=A[i]
		if QpreR>=fourdivide:
			Rflag=1
			Rindex=i
			QpreRpre=QpreR-A[i]

if Qpre!=0 and QpreR!=0:
	intr(P,Qpre,QpreR)
if Qpre!=0 and QpreRpre!=0:
	intr(P,Qpre,QpreRpre)

Qflag=0
Rflag=0
PpreQ=PpreQpre=0
PpreR=PpreRpre=0

if Ppre!=0:
	for i in range(Pindex,N):
		if Qflag==0 and i<=N-3:
			PpreQ+=A[i]
			if PpreQ>=fourdivide:
				Qflag=1
				Qindex=i
				PpreQpre=PpreQ-A[i]
		elif Rflag==0 and i<=N-2:
			PpreR+=A[i]
			if PpreR>=fourdivide:
				Rflag=1
				Rindex=i
				PpreRpre=PpreR-A[i]
	if Ppre!=0 and PpreQ!=0 and PpreR!=0:
		intr(Ppre,PpreQ,PpreR)
	if Ppre!=0 and PpreQ!=0 and PpreRpre!=0:
		intr(Ppre,PpreQ,PpreRpre)
	Rflag=0
	PpreQpreR=PpreQpreRpre=0
	for i in range(Qindex,N):
		if Rflag==0 and i<=N-2:
			PpreQpreR+=A[i]
			if PpreQpreR>=fourdivide:
				Rflag=1
				Rindex=i
				PpreQpreRpre=PpreQpreR-A[i]
	if Ppre!=0 and PpreQpre!=0 and PpreQpreR!=0:
		intr(Ppre,PpreQpre,PpreQpreR)
	if Ppre!=0 and PpreQpre!=0 and PpreQpreRpre!=0:
		intr(Ppre,PpreQpre,PpreQpreRpre)
      



print(answer)

Submission status: Wrong Answer

Solution code:
N = int(input())
*A, = map(int, input().split())
a = sum(A)/4
B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 + A[i] <= a and N >= i + 3:
        B1 += A[i]
    elif N == i + 2:
        B2 += A[i]
    else:
        if B2 + A[i] <= a and N >= i + 2:
            B2 += A[i]
        elif N == i + 1:
            B3 += A[i]
        else:
            if B3 + A[i] <= a and N >= i + 1:
                B3 += A[i]
            elif N == i:
                B4 += A[i]
            else:
                B4 += A[i]
C1 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 + A[i] <= a and N >= i + 3:
        B1 += A[i]
    elif N == i + 2:
        B2 += A[i]
    else:
        if B2 + A[i] <= a and N >= i + 2:
            B2 += A[i]
        elif N == i + 1:
            B3 += A[i]
        else:
            if B3 <= a and N >= i + 1:
                B3 += A[i]
            elif N == i:
                B4 += A[i]
            else:
                B4 += A[i]
C2 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 + A[i] <= a and N >= i + 3:
        B1 += A[i]
    elif N == i + 2:
        B2 += A[i]
    else:
        if B2 <= a and N >= i + 2:
            B2 += A[i]
        elif N == i + 1:
            B3 += A[i]
        else:
            if B3 + A[i] <= a and N >= i + 1:
                B3 += A[i]
            elif N == i:
                B4 += A[i]
            else:
                B4 += A[i]
C3 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 + A[i] <= a and N >= i + 3:
        B1 += A[i]
    elif N == i + 2:
        B2 += A[i]
    else:
        if B2 <= a and N >= i + 2:
            B2 += A[i]
        elif N == i + 1:
            B3 += A[i]
        else:
            if B3 <= a and N >= i + 1:
                B3 += A[i]
            elif N == i:
                B4 += A[i]
            else:
                B4 += A[i]
C4 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 <= a and N >= i + 3:
        B1 += A[i]
    elif N == i + 2:
        B2 += A[i]
    else:
        if B2 + A[i] <= a and N >= i + 2:
            B2 += A[i]
        elif N == i + 1:
            B3 += A[i]
        else:
            if B3 + A[i] <= a and N >= i + 1:
                B3 += A[i]
            elif N == i:
                B4 += A[i]
            else:
                B4 += A[i]
C5 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 <= a and N >= i + 3:
        B1 += A[i]
    elif N == i + 2:
        B2 += A[i]
    else:
        if B2 + A[i] <= a and N >= i + 2:
            B2 += A[i]
        elif N == i + 1:
            B3 += A[i]
        else:
            if B3 <= a and N >= i + 1:
                B3 += A[i]
            elif N == i:
                B4 += A[i]
            else:
                B4 += A[i]
C6 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 <= a and N >= i + 3:
        B1 += A[i]
    elif N == i + 2:
        B2 += A[i]
    else:
        if B2 <= a and N >= i + 2:
            B2 += A[i]
        elif N == i + 1:
            B3 += A[i]
        else:
            if B3 + A[i] <= a and N >= i + 1:
                B3 += A[i]
            elif N == i:
                B4 += A[i]
            else:
                B4 += A[i]
C7 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 <= a and N >= i + 3:
        B1 += A[i]
    elif N == i + 2:
        B2 += A[i]
    else:
        if B2 <= a and N >= i + 2:
            B2 += A[i]
        elif N == i + 1:
            B3 += A[i]
        else:
            if B3 <= a and N >= i + 1:
                B3 += A[i]
            elif N == i:
                B4 += A[i]
            else:
                B4 += A[i]
C8 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

print(min([C1, C2, C3, C4, C5, C6, C7, C8]))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int, input().split()))
a=sum(l)/4
s=[]
b=0
i=0
while True:
    if len(s)==3 or i==n-1:
        s.append(sum(l[i:]))
        break
    if b+l[i]<a or b==0:
        b+=l[i]
        # print(0, l[i])
        i+=1
    else:
        if a-b<b+l[i]-a:
            s.append(b)
            # print(1, b)
        else:
            s.append(b+l[i])
            # print(2, b+l[i])
            i+=1
        b=0

# print(s)
print(max(s)-min(s))

Submission status: Wrong Answer

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

A = nums[:1]
B = nums[1:n//3+1]
C = nums[n//3+1:n-1]
D = nums[n-1:]

q, r, s, t = sum(A), sum(B), sum(C), sum(D)
ans = max(q, r, s, t) - min(q, r, s, t)

def solve(A, B, C, D, ans):
    i = 1
    j = 1
    k = n // 3 + 1
    while True:
        a, b, c, d = sum(A), sum(B), sum(C), sum(D)
        x = max(a, b, c, d)
        y = min(a, b, c, d)
        if x - y <= ans:
            ans = x - y
        else:
            break
        if y == a:
            i += 1
            A = nums[:i]
            B = nums[i:k]
        elif y == d:
            j += 1
            D = nums[n-j:]
            C = nums[k:n-j]
        elif y == b:
            k += 1
            B = nums[i:k]
            C = nums[k:n-j]
        elif y == c:
            k -= 1
            B = nums[i:k]
            C = nums[k:n-j]
        a, b, c, d = sum(A), sum(B), sum(C), sum(D)
        x = max(a, b, c, d)
        y = min(a, b, c, d)
        if x - y <= ans:
            ans = x - y
        else:
            break
        if x == b:
            k -= 1
            B = nums[i:k]
            C = nums[k:n-j]
        elif x == c:
            k += 1
            B = nums[i:k]
            C = nums[k:n-j]

    return ans

print(solve(A, B, C, D, ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = pow(10,10)
for i in range(1, N - 3):
	for j in range(i + 1, N - 2):
		for k in range(j + 1, N):
			B = list(A[:i])
			C = list(A[i:j])
			D = list(A[j:k])
			E = list(A[k:])
			P = sum(B)
			Q = sum(C)
			R = sum(D)
			S = sum(E)
			ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

def getMinPartition(accB, offset=0):
  index = binary_search(accB, (accB[-1] - offset)/2 + offset)
  # print('index ' + str(index))
  return return_min(accB, index, offset)

def calculate_min(accB, index, offset):
  return abs(accB[-1] - 2 * accB[index] + offset)

def return_min(accB, index, offset):
  if calculate_min(accB, index, offset) < calculate_min(accB, index-1, offset):
    return [accB[index] - offset, accB[-1] - accB[index]]
  return [accB[index-1] - offset, accB[-1] - accB[index-1]]


def binary_search(accB, value):
  N = len(accB)
  lowerId = 0
  upperId = N-1
  while lowerId+1 != upperId:
    midId = int((lowerId + upperId)/2)
    if(accB[midId] < value):
      lowerId = midId
    else:
      upperId = midId
  return lowerId

def calculate(accA, i):
  # print(i)
  P, Q = getMinPartition(accA[:i])
  R, S = getMinPartition(accA[i:], accA[i-1])
  # print('P, Q, R, S: {}, {} ,{} ,{}'.format(P, Q, R, S))
  return max([P, Q, R, S]) - min([P, Q, R, S])
  

if __name__=="__main__":
  N = int(input())
  A = list(map(int, input().split()))
  accA = list(itertools.accumulate(A))
  optList = [calculate(accA, i) for i in range(2, N-1)]
  print(min(optList))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = pow(10,5)
for i in range(1, N):
	for j in range(i + 1, N):
		for k in range(j + 1, N):
			B = list(A[:i])
			C = list(A[i:j])
			D = list(A[j:k])
			E = list(A[k:])
			P = sum(B)
			Q = sum(C)
			R = sum(D)
			S = sum(E)
			temp = max(P, Q, R, S) - min(P, Q, R, S)
			if temp < ans:
				ans = temp
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
sumA=[0]
for a in A:
    sumA+=[sumA[-1]+a]
res=float('inf')
for z in range(N//4+1):
    for x in range(2,N-2-z):
        a=sumA[x+z+1]-sumA[x]
        Sb,Sc=sumA[x],sumA[N]-sumA[x+z+1]
        s,t=0,Sb
        u,v=sorted([Sc,a])
        for k,b in enumerate(A[:x-1]):
            s,t=[s+b,t-b]
            tmp=max([s,t,v])-min([s,t,u])
            if tmp<res:res=tmp
        s,t=0,Sc
        u,v=sorted([Sb,a])
        for k,c in enumerate(A[x+1+z:-1]):
            s,t=[s+c,t-c]
            tmp=max([s,t,v])-min([s,t,u])
            if tmp<res:res=tmp
print(res)

Submission status: Wrong Answer

Solution code:
import itertools

def getMinPartition(accB, offset=0):
  index = binary_search(accB, (accB[-1] - offset)/2 + offset)
  print('index ' + str(index))
  return return_min(accB, index, offset)

def calculate_min(accB, index, offset):
  return abs(accB[-1] - 2 * accB[index] + offset)

def return_min(accB, index, offset):
  if calculate_min(accB, index, offset) < calculate_min(accB, index-1, offset):
    return [accB[index] - offset, accB[-1] - accB[index]]
  return [accB[index-1] - offset, accB[-1] - accB[index-1]]


def binary_search(accB, value):
  N = len(accB)
  lowerId = 0
  upperId = N-1
  while lowerId+1 != upperId:
    midId = int((lowerId + upperId)/2)
    if(accB[midId] < value):
      lowerId = midId
    else:
      upperId = midId
  return lowerId

def calculate(accA, i):
  print(i)
  P, Q = getMinPartition(accA[:i])
  R, S = getMinPartition(accA[i:], accA[i-1])
  print('P, Q, R, S: {}, {} ,{} ,{}'.format(P, Q, R, S))
  return max([P, Q, R, S]) - min([P, Q, R, S])
  

if __name__=="__main__":
  N = int(input())
  A = list(map(int, input().split()))
  accA = list(itertools.accumulate(A))
  optList = [calculate(accA, i) for i in range(2, N-1)]
  print(min(optList))

Submission status: Wrong Answer

Solution code:
def main():
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	def ano_helper(BCDE):
		BCDE = BCDE + [s - sum(BCDE)]
		BCDE.sort()
		return abs(BCDE[-1] - BCDE[0])
	def helper(BCDEs, inds):
		if len(BCDEs[0]) == 4:
			return BCDEs
		ret_BCDEs = []
		ret_inds = []
		for candidate in range(len(BCDEs)):
			BCDE = BCDEs[candidate]
			ind = inds[candidate]
			if ind < N:
				ave = sum(A[ind:]) / (5 - len(BCDE))
				temp = A[ind]
				ind += 1
				while ind < N and temp + A[ind] <= ave:
					temp += A[ind]
					ind += 1
				ret_BCDEs.append(BCDE + [temp])
				ret_inds.append(ind)
				if ind <= N - 1:
					ret_BCDEs.append(BCDE + [temp + A[ind]])
					ret_inds.append(ind + 1)
		return helper(ret_BCDEs, ret_inds)
	print(sorted([ano_helper(i[1:]) for i in helper([[0]], [0])])[0])
	return 0
	#BCDE = []
	#ind = 0
	#su = []
	#tempBCDE = [[]]
	#while len(BCDE[-1]) < 4:
	#	temp = 0
	#	ret = []
	#	while temp < (s - su) / (4 - len(BCDE)):
	#		te = A[ind]
	#		temp += te
	#		ret.append(te)
	#		su += te
	#		ind += 1
	#	tempBCDE.append(ret)
	#print(BCDE)
main()

Submission status: Wrong Answer

Solution code:
def main():
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	def ano_helper(BCDE):
		BCDE = BCDE + [s - sum(BCDE)]
		BCDE.sort()
		return abs(BCDE[-1] - BCDE[0])
	def helper(BCDEs, inds):
		if len(BCDEs[0]) == 4:
			return BCDEs
		ret_BCDEs = []
		ret_inds = []
		for candidate in range(len(BCDEs)):
			BCDE = BCDEs[candidate]
			ind = inds[candidate]
			if ind < N:
				ave = sum(A[ind:]) / (5 - len(BCDE))
				temp = A[ind]
				ind += 1
				while ind < N and temp + A[ind] < ave:
					temp += A[ind]
					ind += 1
				ret_BCDEs.append(BCDE + [temp])
				ret_inds.append(ind)
				if ind <= N - 1:
					ret_BCDEs.append(BCDE + [temp + A[ind]])
					ret_inds.append(ind + 1)
		return helper(ret_BCDEs, ret_inds)
	print(sorted([ano_helper(i[1:]) for i in helper([[0]], [0])])[0])
	return 0
	#BCDE = []
	#ind = 0
	#su = []
	#tempBCDE = [[]]
	#while len(BCDE[-1]) < 4:
	#	temp = 0
	#	ret = []
	#	while temp < (s - su) / (4 - len(BCDE)):
	#		te = A[ind]
	#		temp += te
	#		ret.append(te)
	#		su += te
	#		ind += 1
	#	tempBCDE.append(ret)
	#print(BCDE)
main()

Submission status: Wrong Answer

Solution code:
N = int(input())
*A, = map(int, input().split())
a = sum(A)/4
B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 + A[i] <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 + A[i] <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 + A[i] <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C1 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])
    
B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 + A[i] <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 + A[i] <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C2 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 + A[i] <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 + A[i] <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C3 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 + A[i] <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C4 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 + A[i] <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 + A[i] <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C5 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 + A[i] <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C6 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 + A[i] <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C7 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

B1 = 0
B2 = 0
B3 = 0
B4 = 0
for i in range(N):
    if B1 <= a and N >= i + 4:
        B1 += A[i]
    elif N == i + 3:
        B2 += A[i]
    else:
        if B2 <= a and N >= i + 3:
            B2 += A[i]
        elif N == i +2:
            B3 += A[i]
        else:
            if B3 <= a and N >= i + 2:
                B3 += A[i]
            elif N == i +1:
                B4 += A[i]
            else:
                B4 += A[i]
C8 = max([B1,B2,B3,B4]) - min([B1,B2,B3,B4])

print(min([C1, C2, C3, C4, C5, C6, C7, C8]))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

n = int(input())
xs = [int(x) for x in input().split()]

ys = list(accumulate(xs))

def sums(pos):
    i, j, k = pos
    return ys[i], ys[j] - ys[i], ys[k] - ys[j], ys[-1] - ys[k]

def maxmin(pos):
    s = sums(pos)
    return max(s)-min(s)

options = ((1,0,0), (1,1,0), (0,0,-1), (0,-1,-1), (0,1,0), (0,-1,0))

current = 0, len(xs)//2 - 1, len(xs)-2

v = maxmin(current)

while True:
    moves = (tuple(x+y for x, y in zip(current, option)) for option in options)
    best = min(moves, key=lambda x:maxmin(x))
    if maxmin(best) < v:
        current, v = best, maxmin(best)
    else:
        break

print(v)

Submission status: Wrong Answer

Solution code:
N=input()
A=map(int, raw_input().split())
B=range(1,N+1)

C=[]
for x,y in zip(A,B):
	C.append(x-y)

K=set(C)
L=list(K)
L.append(0)
L.sort()

h=len(L)
l=0


ans=float("inf")

for j in range(100):
	m=(h+l)/2
	x=L[m]
	t=0
	for y in C:
		t+=abs(-1*x+y)

	if t<ans:
		ans=t
		h=m
	else:
		l=m
	ans=min(ans,t)

print ans