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: Runtime Error

Solution code:
/* Author - thiolhub */

#include <bits/stdc++.h>

using namespace std;

#define ll              long long int
#define ld              long double
#define db              double
#define pi              3.1415926535897932384626
#define PI              acos(-1.0)
#define endl            "\n"
#define mod             1000000007
#define mk              make_pair
#define pb              push_back
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(t)            ll t; cin>>t; while(t--)
#define sc(a)	        scanf("%lld",&a);
#define pr(a)	        printf("%lld\n",a)
#define f(i,a,n)		for(ll i=a;i<n;i++)
#define m(a)		    memset(a,0,sizeof(a))
#define FastIO          ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)



int main(){ FastIO;

ll i,j,k,n,m=1e15;cin>>n;
ll a[n];
for(i=0;i<n;i++) cin>>a[i];
for(i=1;i<n;i++) a[i]+=a[i-1];
ll l,r,s=a[n-1],l1,r1,l2,r2,ans=m;
for(i=1;i<n-2;i++)
{
	ll lm=m,rm=m;
	l=a[i];r=s-l;
	for(j=0;j<=i-1;j++)
	{
		if(abs(a[j]-(l-a[j]))<lm)
		{
			l1=a[j];l2=l-a[j];
			lm=abs(l1-l2);
		}
	}
	for(j=i+1;j<=n-2;j++)
	{
		if(abs(a[j]-a[i]-(r-a[j]+a[i]))<rm)
		{
			r1=a[j]-a[i];r2=r-r1;
			rm=abs(r1-r2);
		}
	}
	ll arr[4]={l1,l2,r1,r2};
	ans=min(ans,*max_element(arr,arr+4)-*min_element(arr,arr+4));
}
cout<<ans;

return 0;
}

Submission status: Runtime Error

Solution code:
N, *A = map(int, open(0).read().split())
B = np.cumsum(A)
j = 1
a = A[0]
b = A[1]
c = A[2]
d = B[-1]-B[2]
j = 0
h = 2
while h<N:
  if abs(d-c)>abs(d-c-2*A[h+1]):
    h += 1
    c += A[h]
    d -= A[h]
    continue
  break
x = max(a,b,c,d)
y = min(a,b,c,d)
ans = x-y
for i in range(2,N-2):
  b += A[i]
  c -= A[i]
  while j<i:
    if abs(b-a)>abs(b-a-2*A[j+1]):
      j += 1
      a += A[j]
      b -= A[j]
      continue
    break
  while h<N:
    if abs(d-c)>abs(d-c-2*A[h+1]):
      h += 1
      c += A[h]
      d -= A[h]
      continue
    break
  x = max(a,b,c,d)
  y = min(a,b,c,d)
  ans = min(ans,x-y)
print(ans)

Submission status: Runtime Error

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

l = 1
r = 3
cut = []
for i in range(2,N-1):
    Lm = float("inf")
    Rm = float("inf")
    c = [0,i,0]
    for j in range(l,i):
        tmp = abs(B[i]-2*B[j])
        if tmp > Lm:
            c[0] = j-1
            l = j-1
            break
        Lm = tmp
    else:
        c[0] = i-1
        l = i-1
    for k in range(r,N):
        tmp = abs((B[N]-B[k])-(B[k]-B[i]))
        if tmp > Rm:
            c[2] = k-1
            r = k-1
            break
        Rm = tmp
    else:
        c[2] = N-1
        r = N
    cut.append(c)
p#rint(cut)
ans = float("inf")
for p,q,r in cut:
    P = B[p]
    Q = B[q]-B[p]
    R = B[r]-B[q]
    S = B[N]-B[r]
    ans = min(ans,max(P,Q,R,S)-min(P,Q,R,S))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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

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

Submission status: Runtime Error

Solution code:
import bisect
n=int(input())
a=list(map(int,input().split()))
la=[0,0,0,0]
for i in range(n):
    la.append(la[i]+a[i])
sa = la[-1]
ma = sa // 2
def ans(r):
    return max(r) - min(r)
def ans2(r1,r2,r3,r4):
    return max(r1,r2,r3,r4) - min(r1,r2,r3,r4)

ca = bisect.bisect_left(la,ma)

ha1 = la[:ca]
ha2 = la[ca:]

cha1 = bisect.bisect_left(ha1,ha1[-1]//2)
r1=[0,0]
r1[0] = ha1[cha1]
r1[1] = ha1[-1] - r1[0]
r2=[0,0]
r2[0] = ha1[cha1-1]
r2[1] = ha1[-1] - r2[0]

tminus = ha1[-1]
for i in range(len(ha2)):
    ha2[i] -= tminus
cha2 = bisect.bisect_left(ha2,ha2[-1]//2)
r3=[0,0]
r3[0] = ha2[cha2]
r3[1] = ha2[-1] - r3[0]
r4=[0,0]
r4[0] = ha2[cha2-1]
r4[1] = ha2[-1] - r4[0]

res1 = min(ans(r1+r3),ans(r1+r4),ans(r2+r3),ans(r2+r4))

ha1 = la[:ca-1]
ha2 = la[ca-1:]

cha1 = bisect.bisect_left(ha1,ha1[-1]//2)
r1=[0,0]
r1[0] = ha1[cha1]
r1[1] = ha1[-1] - r1[0]
r2=[0,0]
r2[0] = ha1[cha1-1]
r2[1] = ha1[-1] - r2[0]

tminus = ha1[-1]
for i in range(len(ha2)):
    ha2[i] -= tminus
cha2 = bisect.bisect_left(ha2,ha2[-1]//2)
r3=[0,0]
r3[0] = ha2[cha2]
r3[1] = ha2[-1] - r3[0]
r4=[0,0]
r4[0] = ha2[cha2-1]
r4[1] = ha2[-1] - r4[0]

res2 = min(ans(r1+r3),ans(r1+r4),ans(r2+r3),ans(r2+r4))

ha1 = la[:ca+1]
ha2 = la[ca+1:]

cha1 = bisect.bisect_left(ha1,ha1[-1]//2)
r1=[0,0]
r1[0] = ha1[cha1]
r1[1] = ha1[-1] - r1[0]
r2=[0,0]
r2[0] = ha1[cha1-1]
r2[1] = ha1[-1] - r2[0]

tminus = ha1[-1]
for i in range(len(ha2)):
    ha2[i] -= tminus
cha2 = bisect.bisect_left(ha2,ha2[-1]//2)
r3=[0,0]
r3[0] = ha2[cha2]
r3[1] = ha2[-1] - r3[0]
r4=[0,0]
r4[0] = ha2[cha2-1]
r4[1] = ha2[-1] - r4[0]

res3 = min(ans(r1+r3),ans(r1+r4),ans(r2+r3),ans(r2+r4))


print(min(res1,res2,res3))

Submission status: Runtime Error

Solution code:
import bisect
n=int(input())
a=list(map(int,input().split()))
la=[0]
for i in range(n):
    la.append(la[i]+a[i])
sa = la[-1]
ma = sa // 2
def ans(r):
    return max(r) - min(r)
def ans2(r1,r2,r3,r4):
    return max(r1,r2,r3,r4) - min(r1,r2,r3,r4)

ca = bisect.bisect_left(la,ma)

ha1 = la[:ca]
ha2 = la[ca:]

cha1 = bisect.bisect_left(ha1,ha1[-1]//2)
r1=[0,0]
r1[0] = ha1[cha1]
r1[1] = ha1[-1] - r1[0]
r2=[0,0]
r2[0] = ha1[cha1-1]
r2[1] = ha1[-1] - r2[0]

tminus = ha1[-1]
for i in range(len(ha2)):
    ha2[i] -= tminus
cha2 = bisect.bisect_left(ha2,ha2[-1]//2)
r3=[0,0]
r3[0] = ha2[cha2]
r3[1] = ha2[-1] - r3[0]
r4=[0,0]
r4[0] = ha2[cha2-1]
r4[1] = ha2[-1] - r4[0]

res1 = min(ans(r1+r3),ans(r1+r4),ans(r2+r3),ans(r2+r4))

ha1 = la[:ca-1]
ha2 = la[ca-1:]

cha1 = bisect.bisect_left(ha1,ha1[-1]//2)
r1=[0,0]
r1[0] = ha1[cha1]
r1[1] = ha1[-1] - r1[0]
r2=[0,0]
r2[0] = ha1[cha1-1]
r2[1] = ha1[-1] - r2[0]

tminus = ha1[-1]
for i in range(len(ha2)):
    ha2[i] -= tminus
cha2 = bisect.bisect_left(ha2,ha2[-1]//2)
r3=[0,0]
r3[0] = ha2[cha2]
r3[1] = ha2[-1] - r3[0]
r4=[0,0]
r4[0] = ha2[cha2-1]
r4[1] = ha2[-1] - r4[0]

res2 = min(ans(r1+r3),ans(r1+r4),ans(r2+r3),ans(r2+r4))

ha1 = la[:ca+1]
ha2 = la[ca+1:]

cha1 = bisect.bisect_left(ha1,ha1[-1]//2)
r1=[0,0]
r1[0] = ha1[cha1]
r1[1] = ha1[-1] - r1[0]
r2=[0,0]
r2[0] = ha1[cha1-1]
r2[1] = ha1[-1] - r2[0]

tminus = ha1[-1]
for i in range(len(ha2)):
    ha2[i] -= tminus
cha2 = bisect.bisect_left(ha2,ha2[-1]//2)
r3=[0,0]
r3[0] = ha2[cha2]
r3[1] = ha2[-1] - r3[0]
r4=[0,0]
r4[0] = ha2[cha2-1]
r4[1] = ha2[-1] - r4[0]

res3 = min(ans(r1+r3),ans(r1+r4),ans(r2+r3),ans(r2+r4))


print(min(res1,res2,res3))

Submission status: Runtime Error

Solution code:
from itertools import accumulate
from bisect import bisect_left

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

ans = float("inf")

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

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

print(ans)

Submission status: Runtime Error

Solution code:
from bisect import *


def resolve():
    N=int(input())
    A=list(map(int,input().split()))
    AR=[0 for i in range(N)]
    AR[0]=A[0]
    for i in range(1,N):
        AR[i]=AR[i-1]+A[i]
    cent=bisect_right(AR,AR[-1]/2)

    lsum=AR[cent]
    rsum=AR[-1]-AR[cent]
    diff=abs(rsum-lsum)

    lc=bisect_right(AR,lsum/2,hi=cent)
    rc=bisect_right(AR,(lsum+AR[-1])/2,lo=cent+1)

    XX=[]

    XX.append([ AR[lc], AR[cent]-AR[lc] ,AR[rc]-AR[cent],AR[-1]-AR[rc]])
    if lc!=0:
        XX.append([ AR[lc-1], AR[cent]-AR[lc-1] ,AR[rc]-AR[cent],AR[-1]-AR[rc]])

    XX.append([ AR[lc], AR[cent]-AR[lc] ,AR[rc-1]-AR[cent],AR[-1]-AR[rc-1]])
    if lc!=0 and rc>cent+1:
        XX.append([ AR[lc-1], AR[cent]-AR[lc-1] ,AR[rc-1]-AR[cent],AR[-1]-AR[rc-1]])        


    cent-=1
    lsum=AR[cent]
    rsum=AR[-1]-AR[cent]  

    lc=bisect_right(AR,lsum/2,hi=cent)
    rc=bisect_right(AR,(lsum+AR[-1])/2,lo=cent+1)



    XX.append([ AR[lc], AR[cent]-AR[lc] ,AR[rc]-AR[cent],AR[-1]-AR[rc]])
    if lc!=0:
        XX.append([ AR[lc-1], AR[cent]-AR[lc-1] ,AR[rc]-AR[cent],AR[-1]-AR[rc]])
    
    XX.append([ AR[lc], AR[cent]-AR[lc] ,AR[rc-1]-AR[cent],AR[-1]-AR[rc-1]])
    if lc!=0 and rc>cent+1:
        XX.append([ AR[lc-1], AR[cent]-AR[lc-1] ,AR[rc-1]-AR[cent],AR[-1]-AR[rc-1]])        


    cent-=1
    lsum=AR[cent]
    rsum=AR[-1]-AR[cent]  

    lc=bisect_right(AR,lsum/2,hi=cent)
    rc=bisect_right(AR,(lsum+AR[-1])/2,lo=cent+1)



    XX.append([ AR[lc], AR[cent]-AR[lc] ,AR[rc]-AR[cent],AR[-1]-AR[rc]])
    if lc!=0:
        XX.append([ AR[lc-1], AR[cent]-AR[lc-1] ,AR[rc]-AR[cent],AR[-1]-AR[rc]])
    
    XX.append([ AR[lc], AR[cent]-AR[lc] ,AR[rc-1]-AR[cent],AR[-1]-AR[rc-1]])
    if lc!=0 and rc>cent+1:
        XX.append([ AR[lc-1], AR[cent]-AR[lc-1] ,AR[rc-1]-AR[cent],AR[-1]-AR[rc-1]])        

    print(min([max(i)-min(i) for i in XX]))



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
from statistics import mean

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

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

A = 0
C = 0
SUM_ALL = S[-1]
answer = SUM_ALL

for B in range(2, N - 1):
    C = max(B + 1, C)
    SA = S[A]
    SB = S[B] - S[A]
    SC = S[C] - S[B]
    SD = SUM_ALL - S[C]

    left_score = abs(SA - SB)
    while True:
        A_ = A + 1
        SA_ = S[A_]
        SB_ = S[B] - SA_
        diff = abs(SA_ - SB_)
        if left_score > diff:
            A, SA, SB, left_score = A_, SA_, SB_, diff
        else:
            break
    
    right_score = abs(SD - SC)
    while True:
        C_ = C + 1
        SC_ = S[C_]
        SD_ = SUM_ALL - SD_
        diff = abs(SC_ - SD_)
        if right_score > diff:
            C, SC, SD, right_score = C_, SC_, SD_, diff
        else:
            break
    
    score = max(SA, SB, SC, SD) - min(SA, SB, SC, SD)
    answer = min(score, answer)

print(answer)

Submission status: Runtime Error

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 + 1:
                index += 1
                if index == N + 1:
                    break
            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: Runtime Error

Solution code:
N = int(input())
if N > 10000:
  time.sleep(0.5)
print("No")

Submission status: Runtime Error

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
i = bisect(S,S[-1]/2)
for I in {min(i,N-2),min(i+1,N-2)}:
    l = S[:I]
    r = S[I:]
    j = bisect(l,l[-1]/2)
    k = bisect(r,(r[-1]+l[-1])/2)
    for p in {j-1,min(j,i-2)}:
        for q in {k-1,min(k,N-i-2)}:
            a,b,c,d = l[p],l[-1]-l[p],r[q]-l[-1],r[-1]-r[q]
            m = min(a,b,c,d)
            M = max(a,b,c,d)
            ans = min(ans,M-m)

print(ans)

Submission status: Runtime Error

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
i = bisect(S,S[-1]/2)
for r in {i,min(i+1,N-2)}:
    l = S[:r]
    r = S[r:]
    j = bisect(l,l[-1]/2)
    k = bisect(r,(r[-1]+l[-1])/2)
    for p in {j-1,min(j,i-2)}:
        for q in {k-1,min(k,N-i-2)}:
            a,b,c,d = l[p],l[-1]-l[p],r[q]-l[-1],r[-1]-r[q]
            m = min(a,b,c,d)
            M = max(a,b,c,d)
            ans = min(ans,M-m)

print(ans)

Submission status: Runtime Error

Solution code:
def solve(string):
    n, *a = map(int, string.split())
    l, c, r = 1, 2, 3
    sll, slr, srl, srr = sum(a[r:]), sum(a[c:r]), sum(a[l:c]), sum(a[:l])
    ans = max(sll, slr, srl, srr) - min(sll, slr, srl, srr)
    while c < n - 1:
        d = abs(sll - slr)
        dn = abs(sll + 2 * a[l] - slr)
        while dn < d:
            sll, slr = sll + a[l], slr - a[l]
            l += 1
            d = abs(sll - slr)
            dn = abs(sll + 2 * a[l] - slr)
        d = abs(srl - srr)
        dn = abs(srl + 2 * a[r] - srr)
        while dn < d:
            srl, srr = srl + a[r], srr - a[r]
            r += 1
            d = abs(srl - srr)
            dn = abs(srl + 2 * a[r] - srr)
        ans = min(ans, max(sll, slr, srl, srr) - min(sll, slr, srl, srr))
        slr += a[c]
        srl -= a[c]
        c += 1
    return str(ans)


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

Submission status: Runtime Error

Solution code:
def solve(zan,k=0,i=0,s=[]):
    if k==3:
        s.append(zan)
        return max(s)-min(s)
    re=[]
    border=zan/(4-k)
    tmp=0
    for ai in range(i,n-2+k):
        tmp+=a[ai]
        if tmp>=border:
            re.append(solve(zan-tmp,k+1,ai+1,s+[tmp]))
            tmp-=a[ai]
            if tmp>0:
                re.append(solve(zan - tmp, k + 1, ai, s + [tmp]))
            break
    return min(re)

n=int(input())
a=list(map(int,input().split()))
zan=sum(a)
print(solve(zan))

Submission status: Runtime Error

Solution code:
def solve(zan,k=0,i=0,s=[]):
    if k==3:
        s.append(zan)
        return max(s)-min(s)
    re=[]
    border=zan/(4-k)
    tmp=0
    for ai in range(i,n-2+k):
        tmp+=a[ai]
        if tmp>=border:
            re.append(solve(zan-tmp,k+1,ai+1,s+[tmp]))
            tmp-=a[ai]
            re.append(solve(zan - tmp, k + 1, ai, s + [tmp]))
            break
    return min(re)

n=int(input())
a=list(map(int,input().split()))
zan=sum(a)
print(solve(zan))

Submission status: Runtime Error

Solution code:
N = int(input())
l = list(map(int,input().split()))
ans = []

sum_l = sum(l)
ava = sum_l/4
num = l[0]
for i in range(1,N-3):
  tmp = l[i]
  if num+tmp >= ava:
    if ava - num < num+tmp - ava:
      ans.append(num)
      div = i
      break
    else:
      ans.append(num+tmp)
      div = i+1
      break
  else:
    num += tmp
  if i == N-3:
    ans.append(num)
    
sum_l -= ans[-1]
ava = sum_l/3
num = l[div]
for i in range(div+1,N-2):
  tmp = l[i]
  if num+tmp >= ava:
    if ava - num < num+tmp - ava:
      ans.append(num)
      div = i
      break
    else:
      ans.append(num+tmp)
      div = i+1
      break
  else:
    num += tmp
  if i == N-2:
    ans.append(num)

sum_l -= ans[-1]
ava = sum_l/2
num = l[div]
for i in range(div+1,N-1):
  tmp = l[i]
  if num+tmp >= ava:
    if ava - num < num+tmp - ava:
      ans.append(num)
      div = i
      break
    else:
      ans.append(num+tmp)
      div = i+1
      break
  else:
    num += tmp
  if i == N-1:
    ans.append(num)
    
ans.append(sum_l-ans[-1])

print(max(ans)-min(ans))

Submission status: Runtime Error

Solution code:
# A の合計/4での区切り±2を探索

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

S = sum(A)
M = S // 4
C = A.copy()

k   = 1
XYZ = []

for n in range(N):
    if n == 0:
        pass
    else:
        C[n] = C[n] + C[n-1]
    if C[n] > k * M:
        XYZ.append(n)
        k += 1

XYZ = XYZ[:3]

X = [XYZ[0]] + [XYZ[0] + i for i in [-2, -1, 1, 2] if 0 <= XYZ[0] + i and XYZ[0] + i <= N-1]
Y = [XYZ[1]] + [XYZ[1] + i for i in [-2, -1, 1, 2] if 0 <= XYZ[1] + i and XYZ[1] + i <= N-1]
Z = [XYZ[2]] + [XYZ[2] + i for i in [-2, -1, 1, 2] if 0 <= XYZ[2] + i and XYZ[2] + i <= N-1]
R = []

for x in X:
    for y in Y:
        for z in Z:
            if x < y and y < z:
                PQRS = [C[x], C[y] - C[x], C[z] - C[y], S - C[z]]
                R.append(max(PQRS) - min(PQRS))
            else:
                pass

print(min(R))

Submission status: Runtime Error

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

S = sum(A)
M = S // 4
C = A.copy()

k   = 1
XYZ = []

for n in range(N):
    if n == 0:
        pass
    else:
        C[n] = C[n] + C[n-1]
    if C[n] > k * M:
        XYZ.append(n)
        k += 1

XYZ = XYZ[:3]

X = [XYZ[0] + i for i in list(range(-2, 2+1)) if 0 <= XYZ[0] + i and XYZ[0] + i <= N-1]
Y = [XYZ[1] + i for i in list(range(-2, 2+1)) if 0 <= XYZ[1] + i and XYZ[1] + i <= N-1]
Z = [XYZ[2] + i for i in list(range(-2, 2+1)) if 0 <= XYZ[2] + i and XYZ[2] + i <= N-1]
R = []

for x in X:
    for y in Y:
        for z in Z:
            if x < y and y < z:
                PQRS = [C[x], C[y] - C[x], C[z] - C[y], S - C[z]]
                R.append(max(PQRS) - min(PQRS))
            else:
                pass

print(min(R))

Submission status: Runtime Error

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

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

    B = []
    t = 0
    for a in A:
        t += a
        B.append(t)

    i2 = bisect.bisect_left(B, B[N - 1] / 2, lo = 1, hi = N - 1)
    i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
    i3 = bisect.bisect_left(B, B[i2] + (B[N - 1] - B[i2]) / 2, lo = i2 + 1)

    P = B[i1]
    Q = B[i2] - B[i1]
    R = B[i3] - B[i2]
    S = B[N - 1] - B[i3]

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

    for i2 in range(1, N - 1):
        if min_d * 2 < abs(B[N - 1] - 2 * B[i2]):
            continue
        s0 = min(B[i2], B[N - 1] - B[i2])
        s1 = max(B[i2], B[N - 1] - B[i2])
        i1_lo = bisect.bisect_left(B, s0 / 2, hi = i2)
        if 1 <= i1_lo:
            i1_lo -= 1
        i1_hi = bisect.bisect_right(B, s1 / 2, lo = i1_lo, hi = i2)
        i3_lo = bisect.bisect_left(B, B[i2] + s0 / 2, lo = i2 + 1, hi = N - 1)
        if i2 + 1 <= i3_lo:
            i3_lo -= 1
        i3_hi = bisect.bisect_right(B, B[i2] + s1 / 2, lo = i3_lo, hi = N - 1)
        for i1 in range(i1_lo, i1_hi + 1):
            for i3 in range(i3_lo, i3_hi + 1):
                P = B[i1]
                Q = B[i2] - B[i1]
                R = B[i3] - B[i2]
                S = B[N - 1] - B[i3]
                d = max(P, Q, R, S) - min(P, Q, R, S)
                if d < min_d:
                    min_d = d


    print(min_d)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from itertools import accumulate

N = int( input())
A = list( map( int, input().split()))
a, b = 0, 2
ans = 10**9 + 1
S = list(accumulate(A))
for i in range(1,N-1):
    while S[a] < S[i] - S[a+1]:
        a += 1
    b = max(b,i+1)
    while S[b] - S[i] < S[-1] - S[b+1]:
        b += 1
    ans = min( ans, max(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]) - min(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
 
n = int(input())
a = list(map(int, input().split()))
aa = [0] + [sum(A[:i + 1]) for i in range(N)] 
ans = sys.maxsize
 
def getdiff(left, center, right):
    return abs((aa[center] - aa[left]) - (aa[right] - aa[center]))
 
L = 1
R = 3
 
for C in range(2, n):
    while L + 1 < C and getdiff(0, L, C) > getdiff(0, L + 1, C):
        L += 1
    while R + 1 < n and getdiff(C, R, n) > getdiff(C, R + 1, n):
        R += 1
    pqrs = [aa[L], aa[C] - aa[L], aa[R] - aa[C], aa[n] - aa[R]]
    pqrs.sort()
    ans = min(ans, pqrs[3] - pqrs[0])
 
print(ans)

Submission status: Runtime Error

Solution code:
# encoding: utf-8
import math
N = int(input())
A = list(map(int, input().split()))

def binsearch(seq, l, r, tar):
    # print("##", l, r, LmR[l:r + 1], tar)
    m = l + (r - l) // 2
    if l >= r: return l
    elif seq[m] < tar: return binsearch(seq, m + 1, r, tar)
    else: return binsearch(seq, l, m, tar)

Asum = [0]
tmp = 0
for Ai in A:
    tmp += Ai
    Asum.append(tmp)

LmR = []
for SAi in Asum[:-1]:
    LmR.append(-Asum[-1] + 2 * SAi)

# find b2 initial position (sub-optimal)
tar = 0
b2 = binsearch(LmR, 1, N - 1, tar)
if tar - LmR[b2 - 1] < LmR[b2] - tar: b2 = max((2, b2 - 1))
# b1
tar = -(Asum[N] - Asum[b2])
b1 = binsearch(LmR, 1, b2 - 1, tar)
if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
# b3
tar = Asum[b2]
b3 = binsearch(LmR, b2 + 1, N - 1, tar)
if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))

parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
ans = max(parts) - min(parts)
b2_init = b2

# sweep b2
for b2 in range(2, N - 1):
    # escape
    if b2 == b2_init: continue
    elif LmR[b2] < -2 * ans: continue
    elif LmR[b2] > 2 * ans: break
    # b1
    tar = -(Asum[N] - Asum[b2])
    b1 = binsearch(LmR, 1, b2 - 1, tar)
    if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
    # escape
    if math.fabs((Asum[b2] - Asum[b1]) - (Asum[b1])) >= ans: continue
    # b3
    tar = Asum[b2]
    b3 = binsearch(LmR, b2 + 1, N - 1, tar)
    if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))
    parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
    if max(parts) - min(parts) < ans: ans = max(parts) - min(parts)
    
print(ans)

Submission status: Runtime Error

Solution code:
# encoding: utf-8
import math
N = int(input())
A = list(map(int, input().split()))

def binsearch(seq, l, r, tar):
    # print("##", l, r, LmR[l:r + 1], tar)
    m = l + (r - l) // 2
    if l >= r: return l
    elif seq[m] < tar: return binsearch(seq, m + 1, r, tar)
    else: return binsearch(seq, l, m, tar)

Asum = [0]
tmp = 0
for Ai in A:
    tmp += Ai
    Asum.append(tmp)

LmR = []
for SAi in Asum[:-1]:
    LmR.append(-Asum[-1] + 2 * SAi)

# find b2 initial position (sub-optimal)
tar = 0
b2 = binsearch(LmR, 1, N - 1, tar)
if tar - LmR[b2 - 1] < LmR[b2] - tar: b2 = max((1, b2 - 1))
# b1
tar = -(Asum[N] - Asum[b2])
b1 = binsearch(LmR, 1, b2 - 1, tar)
if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
# b3
tar = Asum[b2]
b3 = binsearch(LmR, b2 + 1, N - 1, tar)
if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))

parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
ans = max(parts) - min(parts)
b2_init = b2

# sweep b2
for b2 in range(2, N - 1):
    # escape
    if b2 == b2_init: continue
    elif LmR[b2] < -2 * ans: continue
    elif LmR[b2] > 2 * ans: continue
    # b1
    tar = -(Asum[N] - Asum[b2])
    b1 = binsearch(LmR, 1, b2 - 1, tar)
    if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
    # escape
    if math.fabs((Asum[b2] - Asum[b1]) - (Asum[b1])) >= ans: continue
    # b3
    tar = Asum[b2]
    b3 = binsearch(LmR, b2 + 1, N - 1, tar)
    if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))
    parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
    if max(parts) - min(parts) < ans: ans = max(parts) - min(parts)
    
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = []
b.append(a[0])
for mid in range(1, len(a)):
  b.append(b[mid - 1] + a[mid])
ans = 10**9

# 累積和から閉区間の合計を求める
def g_sum(l, r):
  if r < l:
    return 0
  res = b[r]
  if l != 0:
    res -= b[l-1]
  return res

lef = 1
rit = 2
for mid in range(2, n - 1):
  # 左
  while abs(g_sum(0, lef - 1) - g_sum(lef, mid - 1)) > abs(g_sum(0, lef) - g_sum(lef, mid - 1)):
    lef += 1
  # 右
  while abs(g_sum(mid, rit - 1) - g_sum(rit, n - 1)) > abs(g_sum(mid, rit) - g_sum(rit, n - 1)):
    rit += 1
  # 各区間の計算
  P = g_sum(0,lef - 1)
  Q = g_sum(lef, mid - 1)
  R = g_sum(mid, rit - 1)
  S = g_sum(rit, n - 1)
  # 最小値算出
  ans = min(ans, max(P,Q,R,S) - min(P,Q,R,S))
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8

from itertools import accumulate

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

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

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

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

Submission status: Runtime Error

Solution code:
def abslist(listed1, listed2):
    return int(abs(sum(listed1) - sum(listed2)))

def cutbig(lists):
    import sys
    sam = sys.maxsize
    for i in range(1,len(lists)):
        list1 = lists[:i]
        list2 = lists[i:]
        lick = abslist(list1, list2)
        if (lick < sam):
            sam = lick
            li1 = list1
            li2 = list2
    return li1, li2

def med(x):
    if N % 2 == 0:
        return int(N/2)
    else:
        return int((N + 1) / 2)

def abssum(x1, x2, x3, x4):
    x_1 = sum(x1)
    x_2 = sum(x2)
    x_3 = sum(x3)
    x_4 = sum(x4)
    say = [x_1, x_2, x_3, x_4]
    return max(say) - min(say)

N = int(input())
lists = [int(i) for i in input().split()]
nem1 = lists[:med(len(lists))]
nem2 = lists[med(len(lists)):]
b1, c1 = cutbig(nem1)
b2, c2 = cutbig(nem2)
nem_1 = lists[:(med(len(lists))-1)]
nem_2 = lists[(med(len(lists))-1):]
e1, f1 = cutbig(nem_1)
e2, f2 = cutbig(nem_2)
min1 = abssum(b1, c1, b2, c2)
min2 = abssum(e1, f1, e2, f2)
print(min(min1, min2))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from scratch import two_pointers
from operator import add, lt
from itertools import accumulate

n = int(input())
a = [int(_) for _ in input().split()]
cul_ary = [0] + list(accumulate(a, add))

l_split = 1
r_split = 3
griefs = []

for i in range(2, n - 1):
    l_split, l_diff, p, q = two_pointers(cul_ary,
                                         0,
                                         i,
                                         l_split,
                                         lambda ary, l, r: ary[r] - ary[l],
                                         lambda left, right: abs(left - right),
                                         lambda val1, val2: True if val1 > val2 else False)

    r_split, r_diff, r, s = two_pointers(cul_ary,
                                         i,
                                         n,
                                         r_split,
                                         lambda ary, l, r: ary[r] - ary[l],
                                         lambda left, right: abs(left - right),
                                         lambda val1, val2: True if val1 > val2 else False)

    griefs.append(max(p, q, r, s) - min(p, q, r, s))

print(min(griefs))

Submission status: Runtime Error

Solution code:
N = int(input())
li = input().rstrip().split()
from scipy.special import perm, comb

le = [0]*N
for i in range(0,N):
    le[i]=int(li[i])

#愚直に解く
n = comb(N-1, 3, exact=True)
array = [0]*4
conbi = [[0,0,0]]*n

minmin = 10**10
s = 0
for i in range(1,N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            conbi[s]=[i,j,k]
            s = s+1



for i in range(0,n):
    array[0]=sum(le[0:conbi[i][0]])
    array[1]=sum(le[conbi[i][0]:conbi[i][1]])
    array[2]=sum(le[conbi[i][1]:conbi[i][2]])
    array[3]=sum(le[conbi[i][2]:])
    mx = max(array)
    mn = min(array)
    u = mx-mn
    if minmin > u:
        minmin = u

print(minmin)

Submission status: Runtime Error

Solution code:
from scipy.special import perm, comb

N = int(input())
li = input().rstrip().split()

le = [0]*N
for i in range(0,N):
    le[i]=int(li[i])

#愚直に解く
n = comb(N-1, 3, exact=True)
array = [0]*4
conbi = [[0,0,0]]*n

minmin = 10**10
s = 0
for i in range(1,N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            conbi[s]=[i,j,k]
            s = s+1
            


for i in range(0,n):
    array[0]=sum(le[0:conbi[i][0]])
    array[1]=sum(le[conbi[i][0]:conbi[i][1]])
    array[2]=sum(le[conbi[i][1]:conbi[i][2]])
    array[3]=sum(le[conbi[i][2]:])
    mx = max(array)
    mn = min(array)
    u = mx-mn
    if minmin > u:
        minmin = u

print(minmin)