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())
ans = []
lis = list(map(int,input().split()))
num = sum(lis[:2]) - sum(lis[2:])
cou = n-1
for i in range(3,n-1):
  if abs(num) < abs(sum(lis[:i])-sum(lis[i:])):
    cou = i-1
    break
  else:
    num = sum(lis[:i])-sum(lis[i:])

li = lis[:cou]
n = len(li)
nu = sum(li[:1]) - sum(li[1:])
co = n-1
for i in range(2,n):
  if abs(nu) < abs(sum(li[:i])-sum(li[i:])):
    co = i-1
    break
  else:
    nu = sum(li[:i])-sum(li[i:])
ans.append(sum(li[:co]))
ans.append(sum(li[co:]))

l = lis[cou:]
n = len(l)
nm = sum(l[:1]) - sum(l[1:])
c = n-1
for i in range(2,n):
  if abs(nm) < abs(sum(l[:i])-sum(l[i:])):
    c = i-1
    break
  else:
    nm = sum(l[:i])-sum(l[i:])
ans.append(sum(l[:c]))
ans.append(sum(l[c:]))

  #print(lis[co:cou+c])
lisa = lis[co:cou+c]
numb = sum(lisa[:1]) - sum(lisa[1:])
coun = n-1
for i in range(2,n):
    #print(abs(numb), abs(sum(lisa[:i])-sum(lisa[i:])))
  if abs(numb) <= abs(sum(lisa[:i])-sum(lisa[i:])):
    coun = i-1
    break
  else:
    numb = sum(lisa[:i])-sum(lisa[i:])
ans[1] = sum(lisa[:coun])
ans[2] = sum(lisa[coun:])
  #print(lisa[:coun],lisa[coun:])
print(max(ans)-min(ans))

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)
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]
 
intr(P,Qpre,QpreR)
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 N-2:
			PpreR+=A[i]
			if PpreR>=fourdivide:
				Rflag=1
				Rindex=i
				PpreRpre=PpreR-A[i]
	intr(Ppre,PpreQ,PpreR)
	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]
	intr(Ppre,PpreQpre,PpreQpreR)
	intr(Ppre,PpreQpre,PpreQpreRpre)
      
 
 
 
print(answer)

Submission status: Wrong Answer

Solution code:
def f(A,a):
    B = []
    while sum(B) < a and A != []:
        B.append(A.pop())
    if abs(sum(B)-a) > abs(sum(B[:-1])-a) and B != []:
        A.append(B.pop())
    if B == []:
        B.append(A.pop())
    return(B)

N = int(input())
A = [int(i) for i in input().split()]
B = f(A,int(sum(A)//2))
C = f(A,int(sum(A)//2))
D = f(B,int(sum(B)//2))
Y = [sum(X) for X in [A,B,C,D]]
print(max(Y)-min(Y))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = list(map(int,input().split()))

def split(a,sp):
    return [a[sp[k]:sp[k+1]] for k in range(len(sp)-1)]

def su(a_sp):
    return [np.sum(aa) for aa in a_sp]
    
def ev(sp_su):
    score = np.max(sp_su) - np.min(sp_su)
    return score

def ev_all(a,sp):
    a_sp = split(a,sp)
    sp_su = su(a_sp)
    score = ev(sp_su)
    return score
def check(sp,pre_sps):
    atta = 0
    for p in pre_sps:
        if p == sp:
            atta = 1
            break
    return atta
import copy

lef = int(np.ceil(n/4))
mid = int(np.ceil(n/4 * 2))
rig = int(np.ceil(n/4 * 3))
sp = [0,lef,mid,rig,n]

pre_score = 10000000000
pre_sps = [sp]
all_ex = []
owari = 0
while True:
    scores = []
    params = []

    for i in [-1,1]:
        for k in range(3):
            sp_ex = copy.deepcopy(sp)
            sp_ex[k+1] += i
            score = ev_all(a,sp_ex)
            scores.append(score)
            params.append(sp_ex)

    cand = np.where(scores == np.min(scores))[0]
    if len(cand) == 1:
        all_ex.append(1)
    ok = 0
    for c in cand:
        sp = params[c]
        if check(sp,pre_sps) == 0:
            all_ex.append(0)
            ok = 1
            break
    if ok == 0:
        all_ex.append(1)
        sp = pre_sps[(np.array(all_ex) == 0)[-1]]
            
    pre_sps.append(sp)
    if np.min(scores) <= pre_score:
        pre_score = np.min(scores)
    else:
        break
    if owari == 1:
        break
print(int(pre_score))

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))
	print(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)
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]

intr(P,Qpre,QpreR)
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 N-2:
			PpreR+=A[i]
			if PpreR>=fourdivide:
				Rflag=1
				Rindex=i
				PpreRpre=PpreR-A[i]
	intr(Ppre,PpreQ,PpreR)
	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]
	intr(Ppre,PpreQpre,PpreQpreR)
	intr(Ppre,PpreQpre,PpreQpreRpre)
      



print(answer)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = []
lis = list(map(int,input().split()))
num = sum(lis[:2]) - sum(lis[2:])
cou = n-1
for i in range(3,n-1):
  if abs(num) < abs(sum(lis[:i])-sum(lis[i:])):
    cou = i-1
    break
  else:
    num = sum(lis[:i])-sum(lis[i:])

li = lis[:cou]
n = len(li)
nu = sum(li[:1]) - sum(li[1:])
co = n-1
for i in range(1,n):
  if abs(nu) < abs(sum(li[:i])-sum(li[i:])):
    co = i-1
    break
  else:
    nu = sum(li[:i])-sum(li[i:])
ans.append(sum(li[:co]))
ans.append(sum(li[co:]))

l = lis[cou:]
n = len(l)
nm = sum(l[:1]) - sum(l[1:])
c = n-1
for i in range(1,n):
  if abs(nm) < abs(sum(l[:i])-sum(l[i:])):
    c = i-1
    break
  else:
    nm = sum(l[:i])-sum(l[i:])
ans.append(sum(l[:c]))
ans.append(sum(l[c:]))

  #print(lis[co:cou+c])
lisa = lis[co:cou+c]
numb = sum(lisa[:1]) - sum(lisa[1:])
coun = n-1
for i in range(2,n):
    #print(abs(numb), abs(sum(lisa[:i])-sum(lisa[i:])))
  if abs(numb) <= abs(sum(lisa[:i])-sum(lisa[i:])):
    coun = i-1
    break
  else:
    numb = sum(lisa[:i])-sum(lisa[i:])
ans[1] = sum(lisa[:coun])
ans[2] = sum(lisa[coun:])
  #print(lisa[:coun],lisa[coun:])
print(max(ans)-min(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]
        B,C=A[:x],A[x+1+z:]
        lenB,lenC=len(B),len(C)
        Sb,Sc=sumA[lenB],sumA[N]-sumA[N-lenC]
        sumB=[[0,Sb]for _ in[0]*lenB]
        sumC=[[0,Sc]for _ in[0]*lenC]
        for k,b in enumerate(B[:-1]):
            s,t=sumB[k]
            sumB[k+1]=[s+b,t-b]
        for k,c in enumerate(C[:-1]):
            s,t=sumC[k]
            sumC[k+1]=[s+c,t-c]
        for s,t in sumB[1:]:
            abcd=[s,t,Sc,a]
            tmp=max(abcd)-min(abcd)
            if tmp<res:res=tmp
        for s,t in sumC[1:]:
            abcd=[s,t,Sb,a]
            tmp=max(abcd)-min(abcd)
            if tmp<res:res=tmp
print(res)

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]
			ave = sum(A[ind:]) / (5 - len(BCDE))
			temp = 0
			while 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]
			ave = sum(A[ind:]) / (5 - len(BCDE))
			temp = 0
			while temp + A[ind] < ave:
				temp += A[ind]
				ind += 1
				if ind == N:
					break
			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_list = list(map(int, input().split()))

ans=10000000
b_list=range(min(a_list),max(a_list)+1)


for i in range(0,len(a_list)-3):
  for j in range(i+1,len(a_list)-2):
    for k in range(j+1,len(a_list)-1):
      p_list=a_list[0:i+1]
      q_list=a_list[i+1:j+1]
      r_list=a_list[j+1:k+1]
      s_list=a_list[k+1:]
      sum_list=[]
      sum_list.append(sum(p_list))
      sum_list.append(sum(q_list))
      sum_list.append(sum(r_list))
      sum_list.append(sum(s_list))
      ans_koho=max(sum_list)-min(sum_list)
      if (ans_koho<ans):
        ans=ans_koho

print(ans)

Submission status: Wrong Answer

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

ans = 1000000000000000000000000000000000000
pair = [0,0,0,0]
for i in range(n-3):
	for j in range(i,n-2):
		for k in range(j,n-1):
			p = sum(a[0:i+1])
			q = sum(a[i+1:j+1])
			r = sum(a[j+1:k+1])
			s = sum(a[k+1:n])
			M = max(p,q,r,s)
			m = min(p,q,r,s)
			if ans > M-m:
				ans =  M-m
				pair = [p,q,r,s]
			
		
	
print(ans)
print(pair)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
res=float('inf')
for z in range(N//4):
    for x in range(2,N-2-z):
        a=sum(A[x:x+z+1])
        B,C=A[:x],A[x+1+z:]
        lenB,lenC=len(B),len(C)
        Sb,Sc=sum(B),sum(C)
        sumB=[[0,Sb]for _ in[0]*lenB]
        sumC=[[0,Sc]for _ in[0]*lenC]
        for k,b in enumerate(B[:-1]):
            s,t=sumB[k]
            sumB[k+1]=[s+b,t-b]
        for k,c in enumerate(C[:-1]):
            s,t=sumC[k]
            sumC[k+1]=[s+c,t-c]
        for s,t in sumB[1:]:
            abcd=[s,t,Sc,a]
            tmp=max(abcd)-min(abcd)
            if tmp<res:res=tmp
        for s,t in sumC[1:]:
            abcd=[s,t,Sb,a]
            tmp=max(abcd)-min(abcd)
            if tmp<res:res=tmp
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = list(map(int,input().split()))

def split(a,sp):
    return [a[sp[k]:sp[k+1]] for k in range(len(sp)-1)]

def su(a_sp):
    return [np.sum(aa) for aa in a_sp]
    
def ev(sp_su):
    score = np.max(sp_su) - np.min(sp_su)
    return score

def ev_all(a,sp):
    a_sp = split(a,sp)
    sp_su = su(a_sp)
    score = ev(sp_su)
    return score

import copy

lef = int(np.ceil(n/4))
mid = int(np.ceil(n/4 * 2))
rig = int(np.ceil(n/4 * 3))
sp = [0,lef,mid,rig,n]

pre_score = 10000000000
while True:

    scores = []
    params = []
    for i in [-1,1]:
        for k in range(3):
            sp_ex = copy.deepcopy(sp)
            sp_ex[k+1] += i
            score = ev_all(a,sp_ex)
            scores.append(score)
            params.append(sp_ex)

    sp = params[np.argmin(scores)]
    if np.min(scores) < pre_score:
        pre_score = np.min(scores)
    else:
        break
print(int(pre_score))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = list(map(int,input().split()))

def split(a,sp):
    return [a[sp[k]:sp[k+1]] for k in range(len(sp)-1)]

def su(a_sp):
    return [np.sum(aa) for aa in a_sp]
    
def ev(sp_su):
    score = np.max(sp_su) - np.min(sp_su)
    return score

def ev_all(a,sp):
    a_sp = split(a,sp)
    sp_su = su(a_sp)
    score = ev(sp_su)
    return score

import copy

lef = int(np.ceil(n/4))
mid = int(np.ceil(n/4 * 2))
rig = int(np.ceil(n/4 * 3))
sp = [0,lef,mid,rig,n]

pre_score = 10000000000
while True:

    scores = []
    params = []
    for i in [-1,1]:
        for k in range(3):
            sp_ex = copy.deepcopy(sp)
            sp_ex[k+1] += i
            score = ev_all(a,sp_ex)
            scores.append(score)
            params.append(sp_ex)

    sp = params[np.argmin(scores)]
    if np.min(scores) < pre_score:
        pre_score = np.min(scores)
    else:
        break
print(pre_score)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = list(map(int,input().split()))

def split(a,sp):
    return [a[sp[k]:sp[k+1]] for k in range(len(sp)-1)]

def su(a_sp):
    return [np.sum(aa) for aa in a_sp]
    
def ev(sp_su):
    score = np.max(sp_su) - np.min(sp_su)
    return score

def ev_all(a,sp):
    a_sp = split(a,sp)
    sp_su = su(a_sp)
    score = ev(sp_su)
    return score

import copy

lef = int(np.ceil(n/4))
mid = int(np.ceil(n/4 * 2))
rig = int(np.ceil(n/4 * 3))
sp = [0,lef,mid,rig,n]

pre_score = 10000000000
for ite in range(100):

    scores = []
    params = []
    for i in [-1,1]:
        for k in range(3):
            sp_ex = copy.deepcopy(sp)
            sp_ex[k+1] += i
            score = ev_all(a,sp_ex)
            scores.append(score)
            params.append(sp_ex)

    sp = params[np.argmin(scores)]
    if np.min(scores) < pre_score:
        pre_score = np.min(scores)
    else:
        break
print(pre_score)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
S=list(map(int,input().split()))

ans=10**12

ave=0
for i in range(N):
    ave+=S[i]
ave=ave//N

for i in range(ave-N//2-10,ave-N//2+10):
    goukei=0
    for j in range(N):
        goukei+=abs(S[j]-(i+j+1))
        
    if ans>goukei:
        ans=goukei
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input()) 
l = list(map(int,input().split()))
ans = [0]*(n-3)

l_sum = list(sum(l[:i]) for i in range(n+1))
l_sum.pop(0)
for i in range(1,n-2):
    tmpl = list(abs(l_sum[i]-l_sum[j]*2) for j in range(0,i))
    tmpr = list(abs(l_sum[k]*2-l_sum[i]-l_sum[n-1])for k in range(i+1,n-1))
    indexl = tmpl.index(min(tmpl))
    indexr = tmpr.index(min(tmpr))
    p = l_sum[indexl]
    q = (l_sum[i]-l_sum[indexl])
    r = (l_sum[i+1+indexr]-l_sum[i])
    s = (l_sum[n-1]-l_sum[i+1+indexr])
    ans[i-1] = max(p,q,r,s)-min(p,q,r,s)
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
tmp = 0
lr = [0]
for a in A:
    tmp += a
    lr.append(tmp)

ans = float('inf')


for i in range(2, N - 1):
    f=1
    g=i+1
    while abs(lr[i] - lr[f] - lr[f]) > abs(lr[i] - lr[f + 1] - lr[f + 1]):
        f += 1
    while abs((lr[-1] - lr[g]) - (lr[g] - lr[i])) > abs((lr[-1] - lr[g + 1]) - (lr[g + 1] - lr[i])):
        g += 1
    l = (lr[f], lr[i] - lr[f], lr[-1] - lr[g], lr[g] - lr[i])
    ans = min(ans, max(l) - min(l))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import bisect

n = int(input())
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = b[i] + a[i]
l, r = deque([b[1]]), deque(b[3 : n])
lenl, lenr = len(l), len(r)
ans = 1145141919810
for i in range(2, n - 1):
    cl, cr = b[i] / 2, (b[n] - b[i]) / 2
    ml = bisect.bisect_left(l, cl)
    mr = bisect.bisect_left(r, cr + b[i])
    if ml == 0:
        x = b[1]
    elif ml == lenl:
        x = l[-1]
    else:
        if l[ml] - cl <= cl - l[ml - 1]:
            x = l[ml]
        else:
            x = l[ml - 1]
    if mr == 0:
        y = r[0]
    elif mr == lenr:
        y = b[-2]
    else:
        if r[mr] - (cr + b[i]) <= (cr + b[i]) - r[mr - 1]:
            y = r[mr]
        else:
            y = r[mr - 1]
    s = [x, b[i] - x, y - b[i], b[n] - y]
    ans = min(ans, max(s) - min(s))
    l.append(b[i])
    r.popleft()
    lenl += 1
    lenr -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from itertools import accumulate

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

a_cumsum = list(accumulate(a))
a_cumsum_rev = list(reversed(list(accumulate(reversed(a)))))

# print(a_cumsum)
# print(a_cumsum_rev)

ans = 10**12
div = 1
while(1):
    # print(left, right)
    pq = a_cumsum[0:div+1]
    pq_rev = a_cumsum_rev[0:div+1]
    diff_pq = a_cumsum_rev[div+1]

    rs = a_cumsum[div+1:]
    rs_rev = a_cumsum_rev[div+1:]
    diff_rs = a_cumsum[div]
    # print(pq)
    # print(rs)

    dis = 10**12
    for j in range(len(pq)-1):
        dis_tmp = abs(pq[j]-pq_rev[j+1]+diff_pq)
        if dis_tmp < dis:
            dis = dis_tmp
            p, q = pq[j], pq_rev[j+1]-diff_pq

    dis = 10**12
    for j in range(len(rs)-1):
        dis_tmp = abs(rs[j]-rs_rev[j+1]-diff_rs)
        if dis_tmp < dis:
            dis = dis_tmp
            r, s = rs[j]-diff_rs, rs_rev[j+1]

    # print(p, q, r, s)
    ans_tmp = max(p, q, r, s)-min(p, q, r, s)
    ans = min(ans, ans_tmp)

    div += 1
    if div == n-2:
        break
    # print()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import numpy as np
n = int(input())
a = list(map(int, input().split()))

a_cumsum = np.cumsum(a)
a_cumsum_rev = np.flip(np.cumsum(list(reversed(a))))


ans = 10**12
left = 0
right = -1
while(1):
    # print(left, right)
    p = a_cumsum[left]
    s = a_cumsum_rev[right]

    qr = a_cumsum[left+1:right] - p
    qr_rev = a_cumsum_rev[left+1:right] - s
    # print(qr)
    # print(qr_rev)

    dis = 10**12
    for j in range(len(qr)-1):
        if abs(qr[j]-qr_rev[j+1]) < dis:
            dis = abs(qr[j]-qr_rev[j+1])
            q, r = qr[j], qr_rev[j+1]
    # print(p, q, r, s)
    ans_tmp = max(p, q, r, s) - min(p, q, r, s)
    ans = min(ans, ans_tmp)

    tmp_left = a_cumsum[left+1]
    tmp_right = a_cumsum_rev[right-1]

    rest = n-(left+1-right)
    if rest == 2:
        break

    if abs(a_cumsum[left+1]-s) <= abs(p-a_cumsum_rev[right-1]):
        left += 1
    else:
        right -= 1
    # print()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def sum(ar,st,en):
    s=0
    for i in range(st,en+1):
        s+=ar[i]
    return s
max_value=999999999999999999999

def k_part(k,n,ar):
    res=max_value
    for o in range(n):
        l_min=0
        for r_min in range(l_min,n):
            min_s=sum(ar,l_min,r_min)
            dp=[[max_value for i in range(n)] for j in range(k)]
            dp[0][r_min-l_min]=min_s
            for p in range(1,k):
                for l_max in range(r_min,n):
                    for r_max in range(l_max,n):
                        max_s=sum(ar,l_max+1,r_max)
                        if max_s>=min_s:
                            dp[p][r_max]=min(dp[p][r_max],max(max_s,dp[p-1][l_max]))
            if dp[k-1][n-1]==max_value:
                continue
            res=min(res,dp[k-1][n-1]-min_s)
        tmp=[0]*n
        for i in range(n):
            tmp[(i-1+n)%n]=ar[i]
        for i in range(n):
            ar[i]=tmp[i]
    return res

k=4
n=int(input())
deps=[int(i) for i in input().strip().split(" ")]
print(k_part(k,n,deps))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
R = [0] * (N + 1)
for i in range(N):
  R[i + 1] += R[i] + A[i]
#print(R)  

ans = 10 ** 15
for i in range(3, N):#R[:i]とR[i:]に切る
  l, r = 2, i + 1
  #R[:l], R[l:i], R[i:r], R[r:]
  #R[l - 1] と R[i - 1] - R[l - 1] の差を考える
  
  while abs(R[i - 1] - 2 * R[l]) <= abs(R[i - 1] - 2 * R[l - 1]):
    l += 1
    
  #R[r - 1] - R [i - 1] と R[N] - R[r - 1] の差を考える  
  while abs(R[N] - 2 * R[r] + R[i - 1]) <= abs(R[N] - 2 * R[r - 1] + R[i - 1]):
    r += 1  
  
  now_max = max(max(R[l - 1], R[i - 1] - R[l - 1]), max(R[r - 1] - R[i - 1], R[N] - R[r - 1]))
  now_min = min(min(R[l - 1], R[i - 1] - R[l - 1]), min(R[r - 1] - R[i - 1], R[N] - R[r - 1]))
  ans = min(ans, now_max - now_min)
  #print(a, b, c, d, ans, ans2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
R = [0] * (N + 1)
for i in range(N):
  R[i + 1] += R[i] + A[i]
#print(R)  

ans = 10 ** 15
for i in range(3, N):#R[:i]とR[i:]に切る
  #left = R[:i]
  #right = R[i]
  left, right = 10 ** 15, 10 ** 15
  a, b, c, d = 0, 0, 0, 0
  for j in range(2, i):#左側
    one = R[j - 1]
    two = R[i - 1] - one
    if left > abs(two - one):
      left = abs(two - one)
      a, b = one, two
    
  for j in range(i + 1, N + 1):#右側  
    three = R[j - 1] - R[i - 1]
    four = R[N] - R[j - 1]
    if right > abs(three - four):
      right = abs(three - four)
      c, d = three, four
    
  T = [a, b, c, d]  
  ans2 = max(T) - min(T)
  ans = min(ans, ans2)
  #print(a, b, c, d, ans, ans2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calc(cum, p1, p2, p3):
    arr = [0]*4
    arr[0] = cum[p1]
    arr[1] = cum[p2] - cum[p1]
    arr[2] = cum[p3] - cum[p2]
    arr[3] = cum[-1] - cum[p3]
    return max(arr) - min(arr)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(n-1):
        a[i+1] += a[i]
    ans = float("inf")
    for i in range(1, n-2):
        p2 = i
        v = a[i]
        L, R = 0, p2
        while L+1 < R:
            P = (L+R)//2
            if a[P] <= v//2:
                L = P
            else:
                R = P
        p1 = L
        L, R = -1, p2-1
        while L+1 < R:
            P = (L+R+1)//2
            if a[P] <= v//2:
                L = P
            else:
                R = P
        p1_ = R
        L, R = p2+1, n-1
        while L+1 < R:
            P = (L+R)//2
            if a[P]-v <= (a[-1]-v)//2:
                L = P
            else:
                R = P
        p3 = L
        L, R = p2, n-2
        while L+1 < R:
            P = (L+R+1)//2
            if a[P]-v <= (a[-1]-v)//2:
                L = P
            else:
                R = P
        p3_ = R
        arr = [0]*4
        arr[0] = calc(a, p1, p2, p3)
        arr[1] = calc(a, p1_, p2, p3)
        arr[2] = calc(a, p1, p2, p3_)
        arr[3] = calc(a, p1_, p2, p3_)
        x = min(arr)
        if x < ans:
            ans = x
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    import itertools
    import math
    B = list(itertools.accumulate(A))

    def f(a, i):
        return abs(B[i]-B[a]-B[a])
    def g(b, i):
        return abs(B[-1]-B[b]- (B[b]- B[i]))
    answer = pow(10, 10)
    for i in range(1, N-2):
        left1 = 0
        right1 = i
        while left1 + 2 < right1:
            c1 = left1 + (right1 - left1)//3
            c2 = right1 - (right1 - left1)//3
            if f(c1, i) > f(c2, i):#条件が満たされる:
                left1 = c1
            else:
                right1 = c2
        left2 = i
        right2 = N-1
        while left2 + 2 < right2:
            c3 = left2 + (right2 - left2)//3
            c4 = right2 - (right2 - left2)//3
            if g(c3, i) > g(c4, i):#条件が満たされる:
                left2 = c3
            else:
                right2 = c4
        p = sorted([(f(j, i), j) for j in range(left1, right1+1)])[0][1]
        q = sorted([(g(j, i), j) for j in range(left2, right2+1)])[0][1]
        m = min(B[p], B[i]-B[p], B[q]-B[i], B[-1]-B[q])
        M = max(B[p], B[i]-B[p], B[q]-B[i], B[-1]-B[q])
        answer = min(answer, M-m)

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    import itertools
    T = list(itertools.accumulate(A))

    answer = pow(10, 10)
    for i in range(1, N-2):
        for a in range(i):
            for b in range(i+1, N-1):
                P = T[a]
                Q = T[i] - T[a]
                R = T[b] - T[i]
                S = T[-1] - T[b]
                temp = max(P, Q, R, S) - min(P, Q, R, S)
                answer = min(answer, temp)
        
    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = tuple(map(int, input().split()))
L = len(A)
B = [0]*L
s = 0
for i,v in enumerate(A):
    s += v
    B[i] = s

def sumf(i,j):
    global B
    if i == 0:
        return B[j]
    else:
        return B[j] - B[i-1]

def dv(a,b):
    r = b - a + 1
    x,y = 0,0
    while r > 0:
        if x < y:
            x += A[a]
            a += 1
        else:
            y += A[b]
            b -= 1
        r -= 1
    return x,y

minu = s
for i in range(2,L-1):
    p,q = dv(0,i-1)
    r,s = dv(i,L-1)
    t = max(p,q,r,s) - min(p,q,r,s)
    if minu > t:
        minu = t

print(minu)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = tuple(map(int, input().split()))
L = len(A)
B = [0]*L
s = 0
for i,v in enumerate(A):
    s += v
    B[i] = s

def sumf(i,j):
    global B
    if i == 0:
        return B[j]
    else:
        return B[j] - B[i-1]

def dv(a,b):
    r = b - a + 1
    x,y = 0,0
    while r > 0:
        if x < y:
            x += A[a]
            a += 1
        else:
            y += A[b]
            b -= 1
        r -= 1
    return x,y

minu = s
for r in range(2,L-1):
    p,q = dv(0,r-1)
    r,s = dv(r,L-1)
    t = max(p,q,r,s) - min(p,q,r,s)
    if minu > t:
        minu = t

print(minu)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = tuple(map(int, input().split()))
B = [0]*len(A)
s = 0
for i,v in enumerate(A):
    s += v
    B[i] = s

def df(a,b):
    mint = B[b-1]
    pr = qs = 0
    for i in range(a+1,b):
        if a == 0:
            pr = B[i-1]
            qs = B[b-1]-B[i-1]
        else:
            pr = B[i-1]-B[a-1]
            qs = B[b-1]-B[i-1]
        v = abs(pr - qs)
        # print("@",pr,qs,v)
        if v < mint:
            mint = v
            p = pr
            q = qs
        else:
            break
    return p,q


minu = s
for i in range(2,len(A)-1):
    p,q = df(0,i)
    r,s = df(i,len(A))
    # print((p,q,r,s))
    t = max(p,q,r,s) - min(p,q,r,s)
    if t < minu:
        minu = t
print(minu)

Submission status: Time Limit Exceeded

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

def f(c,i):
    global n,a,s
    return abs(s[c]-(s[i]-s[c]))

def g(c,i):
    global n,a,s
    return abs((s[c]-s[i])-(s[n-1]-s[c]))

ans=[]
for i in range(1,n-2):
    ans_=[]
    #左側決める
    l,r=0,i
    while l+2<r:
        c1=(l*2+r)//3
        c2=(l+2*r)//3
        if f(c1,i)>f(c2,i):
            l=c1
        else:
            r=c2
    x=sorted([(f(j,i),j) for j in range(l,r+1)])[0][1]
    ans_.append(s[x])
    ans_.append(s[i]-s[x])

    #右側決める
    l,r=i+1,n-1
    while l+2<r:
        c1=(l*2+r)//3
        c2=(l+2*r)//3
        if g(c1,i)>g(c2,i):
            l=c1
        else:
            r=c2
    x=sorted([(g(j,i),j) for j in range(l,r+1)])[0][1]
    ans_.append(s[x]-s[i])
    ans_.append(s[n-1]-s[x])

    ans.append(max(ans_)-min(ans_))
print(min(ans))

Submission status: Time Limit Exceeded

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

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

    mindiff = CA[-1]

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

        # right side
        r = 0
        s = CA[-1]
        right = c+1
        # for i in range(c+1, N):
        while True:
            ri = CA[right] - CA[c]
            si = CA[-1] - CA[right]
            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))
    return mindiff
print(solve())