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 bisect
n = int(input())
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + a[i]
cum.append(10**10)
mincost = 10 ** 10
#print(cum)
for mid in range(2,n-1):
    ll = bisect.bisect_left(cum[:mid], cum[mid]//2)
    rl = bisect.bisect_left(cum[mid:], cum[mid+1] + (cum[n] - cum[mid+1])//2) + mid
    s = [0] * 4
    for i in range(4):
        s[0] = cum[ll - (i&1)]
        s[1] = cum[mid] - cum[ll - (i&1)]
        s[2] = cum[rl - (i&2 >> 1)] - cum[mid]
        s[3] = cum[n] - cum[rl - (i&2 >> 1)]
#        print(ll - (i&1), mid, rl - (i&2 >> 1), s)
        mincost = min(mincost, max(s) - min(s))
print(mincost)

Submission status: Wrong Answer

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

b = a[0]
c = a[1]
d = a[2]
e = sum(a[3:n])
p = 0
q = 1
r = 2
while r+1 <= n-2 and abs((d+a[r+1])-(e-a[r+1])) < abs(c-e):
    r += 1
    d += a[r]
    e -= a[r]
m = max(b,c,d,e) - min(b,c,d,e)

while q <= n-4:
  q += 1
  c += a[q]
  d -= a[q]
  while p+1 < q and abs((b+a[p+1])-(c-a[p+1])) <= abs(b-c):
    b += a[p+1]
    c -= a[p+1]
    p += 1
  while r+1 <= n-2 and abs((d+a[r+1])-(e-a[r+1])) <= abs(d-e):
    d += a[r+1]
    e -= a[r+1]
    r += 1
  m = min(m,max(b,c,d,e) - min(b,c,d,e))
print(m)

Submission status: Wrong Answer

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

b = a[0]
c = a[1]
d = a[2]
e = sum(a[3:n])
p = 0
q = 1
r = 2
while r+1 <= n-2 and abs((d+a[r+1])-(e-a[r+1])) < abs(c-e):
    d += a[r+1]
    e -= a[r+1]
    r += 1
m = max(b,c,d,e) - min(b,c,d,e)

while q <= n-4:
  q += 1
  c += a[q]
  d -= a[q]
  while p+1 < q and abs((b+a[p+1])-(c-a[p+1])) < abs(b-c):
    b += a[p+1]
    c -= a[p+1]
    p += 1
  while r+1 <= n-2 and abs((d+a[r+1])-(e-a[r+1])) < abs(c-e):
    d += a[r+1]
    e -= a[r+1]
    r += 1
  m = min(m,max(b,c,d,e) - min(b,c,d,e))
print(m)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
T=[]
for i in range(N):
  if i==0:
    T.append(A[i])
  else:
    T.append(T[i-1]+A[i])
ans=float("inf")
x=1
y=(N-1)//2
for i in range(2,N):
  while abs(T[i-1]-2*T[x-1])>abs(T[i-1]-2*T[x]):
    x+=1
  while abs(T[i-1]+T[N-1]-2*T[y-1])>abs(T[i-1]+T[N-1]-2*T[y]):
    y+=1
  P=T[x-1]
  Q=T[i-1]-T[x-1]
  R=T[y-1]-T[i-1]
  S=T[N-1]-T[y-1]
  A=max(P,Q,R,S)
  B=min(P,Q,R,S)
  ans=min(ans,A-B)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
T=[]
for i in range(N):
  if i==0:
    T.append(A[i])
  else:
    T.append(T[i-1]+A[i])
ans=float("inf")
x=0
y=(N-1)//2
for i in range(2,N):
  while T[x]<=T[i-1]/2:
    x+=1
  while T[y]<=(T[N-1]+T[i-1])/2:
    if y<=N-2:
      y+=1
    else:
      break
  if abs(T[i-1]-2*T[x])<=abs(T[i-1]-2*T[x-1]):
    P=T[x]
    Q=T[i-1]-T[x]
  else:
    P=T[x-1]
    Q=T[i-1]-T[x-1]
  if abs(2*T[y]-T[i-1]-T[N-1])<=abs(2*T[y-1]-T[i-1]-T[N-1]):
    R=T[y]-T[i-1]
    S=T[N-1]-T[y]
  else:
    R=T[y-1]-T[i-1]
    S=T[N-1]-T[y-1]
  A=max(P,Q,R,S)
  B=min(P,Q,R,S)
  ans=min(ans,A-B)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
T=[]
for i in range(N):
  if i==0:
    T.append(A[i])
  else:
    T.append(T[i-1]+A[i])
ans=float("inf")
x=0
y=(N-1)//2
for i in range(2,N):
  while T[x]<=T[i-1]/2:
    x+=1
  while T[y]<=(T[N-1]+T[i])/2:
    if y<=N-2:
      y+=1
    else:
      break
  if abs(T[i-1]-2*T[x])<=abs(T[i-1]-2*T[x-1]):
    P=T[x]
    Q=T[i-1]-T[x]
  else:
    P=T[x-1]
    Q=T[i-1]-T[x-1]
  if abs(2*T[y]-T[i-1]-T[N-1])<=abs(2*T[y-1]-T[i-1]-T[N-1]):
    R=T[y]-T[i-1]
    S=T[N-1]-T[y]
  else:
    R=T[y-1]-T[i-1]
    S=T[N-1]-T[y-1]
  A=max(P,Q,R,S)
  B=min(P,Q,R,S)
  ans=min(ans,A-B)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N=int(input())
A=[int(i) for i in input().split()]
S=[]
for i in range(N):
  if i==0:
    S.append(A[i])
  else:
    S.append(S[i-1]+A[i])
print(S)
ans=float("inf")
for i in range(2,N):
  x=bisect_left(S[:i],S[i-1]/2)
  if abs(S[i-1]-2*S[x])<=abs(S[i-1]-2*S[x-1]):
    P=S[x]
    Q=S[i-1]-S[x]
  else:
    P=S[x-1]
    Q=S[i-1]-S[x-1]
  y=bisect_left(S[i:],(S[N-1]+S[i])/2)+i-1
  if abs(2*S[y]-S[i-1]-S[N-1])<=abs(2*S[y-1]-S[i-1]-S[N-1]):
    R=S[y]-S[i-1]
    T=S[N-1]-S[y]
  else:
    R=S[y-1]-S[i-1]
    T=S[N-1]-S[y-1]
  A=max(P,Q,R,T)
  B=min(P,Q,R,T)
  ans=min(ans,A-B)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    d1 = 1
    d2 = 2
    d3 = 3
    P = A[0]
    Q = A[1]
    R = A[2]
    S = sum(A[3:])
    ans = max(P, Q, R, S) - min(P, Q, R, S)
    while d2 < N-2:
        while d1 < d2-1:
            x = A[d1]
            if abs((Q-x) - (P+x)) < abs(Q - P):
                P += x
                Q -= x
                d1 += 1
            else:
                break
        while d3 < N-1:
            x = A[d3]
            if d2 >= d3 or abs((S-x) - (R+x)) < abs(S - R):
                R += x
                S -= x
                d3 += 1
            else:
                break
        current = max(P, Q, R, S) - min(P, Q, R, S)
        ans = min(current, ans)
        Q += A[d2]
        R -= A[d2]
        d2 += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    d1 = 1
    d2 = 2
    d3 = 3
    P = A[0]
    Q = A[1]
    R = A[2]
    S = sum(A[3:])
    ans = float("inf")
    while d2 < N-2:
        while d1 < d2-1:
            x = A[d1]
            if abs((Q-x) - (P+x)) < abs(Q - P):
                P += x
                Q -= x
                d1 += 1
            else:
                break
        while d3 < N-1:
            x = A[d3]
            if d2 >= d3 or abs((S-x) - (R+x)) < abs(S - R):
                R += x
                S -= x
                d3 += 1
            else:
                break
        current = max(P, Q, R, S) - min(P, Q, R, S)
        ans = min(current, ans)
        Q += A[d2]
        R -= A[d2]
        d2 += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    d1 = 1
    d2 = 2
    d3 = 3
    P = A[0]
    Q = A[1]
    R = A[2]
    S = sum(A[3:])
    ans = float("inf")
    while d2 < N-2:
        while d1 < d2-1:
            x = A[d1]
            if abs((Q-x) - (P+x)) < abs(Q - P):
                P += x
                Q -= x
                d1 += 1
            else:
                break
        while d3 < N-1:
            x = A[d3]
            if abs((S-x) - (R+x)) < abs(S - R):
                R += x
                S -= x
                d3 += 1
            else:
                break
        current = max(P, Q, R, S) - min(P, Q, R, S)
        ans = min(current, ans)
        Q += A[d2]
        R -= A[d2]
        d2 += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate
from bisect import bisect_right

n = ni()
a = list(li())

acum = list(accumulate(a))

ans = 10**18

lr = 1
rr = 3

for cent in range(2,n-1):
    while abs(acum[(lr+1)-1] - (acum[cent-1]-acum[(lr+1)-1])) < abs(acum[lr-1] - (acum[cent-1]-acum[lr-1])):
        lr += 1
        
    while abs((acum[(rr+1)-1]-acum[cent-1]) - (acum[-1]-acum[(rr+1)-1])) < abs((acum[rr-1]-acum[cent-1]) - (acum[-1]-acum[rr-1])):
        rr += 1
        
    if lr == 0:
        lr = 1
    elif lr == cent:
        lr = cent-1
    
    if rr == cent:
        rr = cent+1
    elif rr == n-1:
        rr = n-2

    temp = [acum[lr-1], acum[cent-1]-acum[lr-1], acum[rr-1]-acum[cent-1], acum[-1]-acum[rr-1]]

    ans = min(ans, (max(temp)-min(temp)))
    
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
B = [A[0]]
ans = []
for i in range(N-1):
    B.append(B[i]+A[i+1])
for i in range(1,N-2):
    BC = 10000000000
    ifB = 0
    ifC = 0
    for j in range(i):
        left = B[j]
        right = B[i] - left
        x = abs(right-left)
        if BC > x:
            BC = x
            ifB = left
            ifC = right
        else:
            break
    DE = 10000000000
    ifD = 0
    ifE = 0
    for j in range(i+1,N-1):
        left = B[j] - B[i]
        right = B[N-1] - B[j]
        x = abs(right-left)
        if DE > x:
            DE = x
            ifD = left
            ifE = right
        else:
            break
    ans.append(max(ifB,ifC,ifD,ifE)-min(ifB,ifC,ifD,ifE))
print(min(ans))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect

def half(T, h):
    b = bisect(T,h)
    if abs(T[b-1]*2 - T[-1] - T[0]) <= abs(T[b]*2 - T[-1] - T[0]):
        return T[b-1] - T[0], T[-1]-T[b-1]
    return T[b] - T[0], T[-1]-T[b]
N = int( input())
A = list( map( int, input().split()))
S = [0] + list( accumulate(A))
ans = 10**9+1
for i in range(2, N-1):
    x, y = half(S[:i+1], S[i]//2)
    z, w = half(S[i:], (S[i] + S[-1])//2)
    print(x,y,z,w)
    m = min(x,y,z,w)
    M = max(x,y,z,w)
    if M-m < ans:
        ans = M-m
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A = list(map(int,input().split()))
sum_=[A[0]]
ans =float('inf')
for i in range(1,N):
    sum_.append(sum_[i-1]+A[i])

midL=0
midR=2
print(sum_)
for i in range(1,N-2):
    minL=float('inf')
    minR=float('inf')
    for j in range(midL,i):
        if abs(sum_[i]-2*sum_[j]) > minL:
            break
        else:
            midL=j
            minL=abs(sum_[i]-2*sum_[j])
        
    for k in range(midR,N-1):
        if abs(sum_[-1]-2*sum_[k]+sum_[i]) > minR:
            break
        else:
            midR=k
            minR=abs(sum_[-1]-2*sum_[k]+sum_[i])
    tmp =  max(sum_[midL],sum_[i]-sum_[midL],sum_[midR]-sum_[i],sum_[-1]-sum_[midR]) -min(sum_[midL],sum_[i]-sum_[midL],sum_[midR]-sum_[i],sum_[-1]-sum_[midR])
    if ans >tmp:
        ans =tmp
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A = list(map(int,input().split()))
sum_=[A[0]]
ans =float('inf')
for i in range(1,N):
    sum_.append(sum_[i-1]+A[i])

midL=0
midR=2
print(sum_)
for i in range(1,N-2):
    minL=float('inf')
    minR=float('inf')
    for j in range(midL,i):
        if abs(sum_[i]-2*sum_[j]) > minL:
            break
        else:
            midL=j
            minL=abs(sum_[i]-2*sum_[j])
        
    for k in range(midR,N-1):
        if abs(sum_[-1]-2*sum_[k]+sum_[i]) > minR:
            break
        else:
            midR=k
            minR=abs(sum_[-1]-2*sum_[k]+sum_[i])
    print(midL,i,midR)
    print(sum_[midL],sum_[i]-sum_[midL],sum_[midR]-sum_[i],sum_[-1]-sum_[midR])
    tmp =  max(sum_[midL],sum_[i]-sum_[midL],sum_[midR]-sum_[i],sum_[-1]-sum_[midR]) -min(sum_[midL],sum_[i]-sum_[midL],sum_[midR]-sum_[i],sum_[-1]-sum_[midR])
    if ans >tmp:
        ans =tmp
print(ans)

Submission status: Wrong Answer

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

summation = sum(A_list)
quarter_sum = summation / 4

temp_sum = 0
sum_list = []

for i in range(N):
    old_temp_sum = temp_sum
    temp_sum += A_list[i]
    if i == N - 1:
        sum_list.append(temp_sum)
        break

    if temp_sum >= quarter_sum:
        if abs(quarter_sum - temp_sum) >= abs(quarter_sum - old_temp_sum):
            sum_list.append(old_temp_sum)
            temp_sum = A_list[i]
        else:
            sum_list.append(temp_sum)
            temp_sum = 0

print(max(sum_list) - min(sum_list))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

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

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


def nibutan(l,h):
	if l==0:
		t=A[h]/2
	else:
		t=(A[h]-A[l])/2+A[l]

	for j in range(50):
		m=(h+l)/2
		if A[m]<t:
			l=m
		else:
			h=m
	if abs(A[h]-t)<abs(t-A[l]):
		return h
	else:
		return l

ans=float("inf")
for i in range(1,N-2): 
	m1=nibutan(0,i)
	x1=A[m1]
	x2=A[i]-A[m1]

	m2=nibutan(i,N-1)
	x3=A[m2]-A[i]
	x4=A[-1]-A[m2]

	x_min=min(x1,x2,x3,x4)
	x_max=max(x1,x2,x3,x4)

	ans=min(ans, x_max-x_min)


print ans

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

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

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


def nibutan(l,h):
	if l==0:
		t=A[h]/2
	else:
		t=(A[h]-A[l])/2+A[l]

	for j in range(30):
		m=(h+l)/2
		if A[m]<t:
			l=m
		else:
			h=m
	if abs(A[h]-t)<abs(t-A[l]):
		return h
	else:
		return l

ans=float("inf")
for i in range(1,N-2): 
	m1=nibutan(0,i)
	x1=A[m1]
	x2=A[i]-A[m1]

	m2=nibutan(i,N-1)
	x3=A[m2]-A[i]
	x4=A[-1]-A[m2]

	x_min=min(x1,x2,x3,x4)
	x_max=max(x1,x2,x3,x4)

	ans=min(ans, x_max-x_min)


print ans

Submission status: Wrong Answer

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

def cutbig(lists):
    import sys
    sam = sys.maxsize
    li1 = []
    li2 = []
    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: Wrong Answer

Solution code:
import sys

def p(a):
    s = sum(a)
    c = a[0]
    for i in range(1, len(a) - 1):
        if (c + a[i]) * 2 >= s:
            x, y = c, s - c - a[i]
            if x > y: return c, s - c
            return s - c - a[i], c + a[i]
        c += a[i]
    return c, a[-1]
            
n = int(input())
a = [int(x) for x in input().split()]
m, M = 0, 10**9
for i in range(2, len(a) - 2):
    m1, m2 = p(a[:i])
    m3, m4 = p(a[i:])
    mm = min(m1, m2, m3, m4)
    MM = max(m1, m2, m3, m4)
    if MM - mm < M - m:
        m = mm
        M = MM
print(M - m)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
from itertools import accumulate
from bisect import bisect_right

def midd(s, e):
    m = (asum[e] - asum[s - 1]) / 2 + asum[s - 1]
    r = bisect_right(asum, m, s + 1, e)
    #print('@', s, e, r, asum[e] - asum[r], asum[r], a[r])
    if (asum[e] - asum[r - 1]) - (asum[r - 1] - asum[s]) > a[r] and r < e:
        r += 1
    #print('|', asum[s], asum[e], m, r, '|', asum[r - 1], asum[r])
    return r - 1


n = int(input())
a = [int(_) for _ in input().split()]

asum = list(accumulate(a)) + [0]
#print(asum)

ans = float('inf')
for d2 in range(1, n - 2):
    d1 = midd(0, d2)
    d3 = midd(d2 + 1, n - 1)
    #print(d1, d2, d3)
    p = asum[d1]
    q = asum[d2] - asum[d1]
    r = asum[d3] - asum[d2]
    s = asum[n - 1] - asum[d3]
    div = abs(max(p, q, r, s) - min(p, q, r, s))
    #print(p + q + r + s, '|', p, q, r, s, ':', div)
    ans = min(ans, div)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(int(i) for i in input().split())
for i in range(N):
  a[i] = a[i]-i
a.sort()
if N%2==0:
  b=int((a[int(N/2)]+a[int(N/2+1)])/2)
else:
  b=a[int((N+1)/2)]
sum_1=0
sum_2=0
sum_3=0
for i in range(N):
  sum_1 += abs(a[i]-b)
b-=1
for i in range(N):
  sum_2 += abs(a[i]-b)
b+=2
for i in range(N):
  sum_3 += abs(a[i]-b)
print(min(sum_1,sum_2,sum_3))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import bisect

N = int(input())
A = list(map(int, input().split()))
S = list(accumulate(A))
ans = float('inf')


for i in range(2, N):
    left = A[:i]
    s_left = S[:i]
    sum_left = S[i - 1]
    index_left = bisect.bisect_left(s_left, (sum_left / 2))

    right = A[i:]
    s_right = S[i:]
    sum_right = S[-1] - S[i - 1]
    index_right = bisect.bisect_left(s_right, (sum_right / 2)) + i + 1 ##

    for j in range(2):
        for k in range(2):
            p = S[index_left - j]
            q = sum_left - p
            s = S[-1] - S[index_right - k - 1]
            r = sum_right - s
            pqrs = [p, q, r, s]
            ans = min(max(pqrs) - min(pqrs), ans)


print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

n = int(input())
a = [int(_) for _ in input().split()]

p = a[0]
q = 0
r = a[1]
s = 0
for i in range(2, n):
    s += a[i]

d1 = 0
d3 = 1

ans = float('inf')
for d2 in range(1, n - 1):
    q += a[d2]
    while q - p > a[d1]:
        if d1 + 1 == d2:
            break
        d1 += 1
        p += a[d1]
        q -= a[d1]
    r -= a[d2]
    if d2 == d3:
        d3 += 1
        r += a[d3]
        s -= a[d3]
    while s - r > a[d3]:
        if d3  == n - 1:
            break
        d3 += 1
        r += a[d3]
        s -= a[d3]
    #print(d1, d2, d3)
    #print(p, q, r, s, '|', max(p, q, r, s) - min(p, q, r, s))
    ans = min(ans, max(p, q, r, s) - min(p, q, r, s))

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

n = int(input())
a = [int(_) for _ in input().split()]

p = a[0]
q = a[1]
r = a[2]
s = 0
for i in range(3, n):
    s += a[i]

d1 = 0
d3 = 2
while s - r > a[d3]:
    d3 += 1
    r += a[d3]
    s -= a[d3]

ans = float('inf')
for d2 in range(1, n - 2):
    ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
    q += a[d2 + 1]
    while q - p > a[d1]:
        if d1 + 1 == d2 + 1:
            break
        d1 += 1
        p += a[d1]
        q -= a[d1]
    r -= a[d2 + 1]
    if d2 + 1 == d3:
        d3 += 1
        r += a[d3]
        s -= a[d3]
    while s - r > a[d3]:
        if d3  == n - 1:
            break
        d3 += 1
        r += a[d3]
        s -= a[d3]

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

n = int(input())
a = [int(_) for _ in input().split()]

p = a[0]
q = a[1]
r = a[2]
s = 0
for i in range(3, n):
    s += a[i]

d1 = 0
d3 = 2
while s - r > a[d3]:
    d3 += 1
    r += a[d3]
    s -= a[d3]

ans = float('inf')
for d2 in range(1, n - 2):
    ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
    q += a[d2 + 1]
    while q - p > a[d1]:
        d1 += 1
        p += a[d1]
        q -= a[d1]
        if d1 + 1 == d2 + 1:
            break
    r -= a[d2 + 1]
    if d2 + 1 == d3:
        d3 += 1
        r += a[d3]
        s -= a[d3]
    while s - r > a[d3]:
        d3 += 1
        r += a[d3]
        s -= a[d3]
        if d3  == n - 1:
            break

print(ans)

Submission status: Wrong Answer

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

t = list(0 for i in range(n+1))
for i in range(1, n+1):
    t[i] = t[i-1] + a[i-1]

def sum_a(i, j):
    return t[j]-t[i]

min_dif = sum_a(0, n)

for i in range(2, n-1):
    j0 = 0
    j1 = i
    u = sum_a(0, i) // 2
    while j1 - j0 > 1:
        j = (j0+j1) // 2
        if 2*sum_a(0, j) <= u: 
            j0 = j
        else:
            j1 = j
    if abs(sum_a(0, j0)-sum_a(j0, i)) < abs(sum_a(0, j1) - sum_a(j1, i)): 
        p = sum_a(0, j0)
        q = sum_a(j0, i)
    else:
        p = sum_a(0, j1)
        q = sum_a(j1, i)

    j0 = i
    j1 = n
    u = sum_a(i, n) // 2
    while j1 - j0 > 1:
        j = (j0+j1) // 2
        if sum_a(i, j) <= u: 
            j0 = j
        else:
            j1 = j
    if abs(sum_a(i, j0)-sum_a(j0, n)) < abs(sum_a(i, j1) - sum_a(j1, n)): 
        r = sum_a(i, j0)
        s = sum_a(j0, n)
    else:
        r = sum_a(i, j1)
        s = sum_a(j1, n)

    min_dif = min(min_dif, max(p, q, r, s)-min(p, q, r, s))

print(min_dif)

Submission status: Wrong Answer

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

t = list(0 for i in range(n+1))
for i in range(1, n+1):
    t[i] = t[i-1] + a[i-1]

def sum_a(i, j):
    return t[j]-t[i]

min_dif = sum_a(0, n)

for i in range(2, n-2):
    j0 = 0
    j1 = i
    u = sum_a(j0, j1)
    while True:
        if j1 - j0 == 1:
            break
        j = (j0+j1) // 2
        if 2*sum_a(0, j) < u: 
            j0 = j
        else:
            j1 = j
    if abs(sum_a(0, j0)-sum_a(j0, i)) < abs(sum_a(0, j1) - sum_a(j1, i)): 
        p = sum_a(0, j0)
        q = sum_a(j0, i)
    else:
        p = sum_a(0, j1)
        q = sum_a(j1, i)

    j0 = i
    j1 = n
    u = sum_a(j0, j1)
    while True:
        if j1 - j0 == 1:
            break
        j = (j0+j1) // 2
        if 2*sum_a(i, j) < u: 
            j0 = j
        else:
            j1 = j
    if abs(sum_a(i, j0)-sum_a(j0, n)) < abs(sum_a(i, j1) - sum_a(j1, n)): 
        r = sum_a(i, j0)
        s = sum_a(j0, n)
    else:
        r = sum_a(i, j1)
        s = sum_a(j1, n)

    min_dif = min(min_dif, max(p, q, r, s)-min(p, q, r, s))

print(min_dif)

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
a = list( map(int, input().split()) )
n_q = n//4
n_r = n % 4
set = [n_q,n_q,n_q,n_q]
l = [0,1,2,3]
l_add = itertools.combinations(l,n_r)
min_sum = 2 * 10**6 
for i in l_add:
  for i_j in i:
    set[i_j] = set[i_j] + 1
  sep = [set[0],set[0]+set[1],set[0]+set[1]+set[2],set[0]+set[1]+set[2]+set[3] ]
  tempsum = sum(a[0:sep[0]]) + sum([ sum(a[sep[k]:sep[k+1]]) for k in range(2)] )
  min_sum = min(min_sum,tempsum)
print(min_sum)

Submission status: Wrong Answer

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

import numpy as np

ans = float("inf")
for i in range(2, N-1):
    left_cs = list(np.cumsum(A[:i]))
    right_cs = list(np.cumsum(A[i:]))
    left_mean_index = np.searchsorted(left_cs, left_cs[-1]/2)
    right_mean_index = np.searchsorted(right_cs, right_cs[-1]/2)
    if left_cs[left_mean_index] - left_cs[-1]/2 > left_cs[-1]/2 - left_cs[left_mean_index - 1]:
        P = left_cs[left_mean_index]
        Q = left_cs[-1] - P
    else:
        P = left_cs[left_mean_index - 1]
        Q = left_cs[-1] - P
    if right_cs[right_mean_index] - right_cs[-1]/2 > right_cs[-1]/2 - right_cs[right_mean_index - 1]:
        R = right_cs[right_mean_index]
        S = right_cs[-1] - R
    else:
        R = right_cs[right_mean_index - 1]
        S = right_cs[-1] - R
    ans = min(ans, (max(P, Q, R, S) - min(P, Q, R, S)))

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def two_pointers(ary, l, r, split, ary_func, comb_func, comp_func):
    '''
    This function is supposed to be repeatedly called so that 'split' keeps
    renewing, under an assumption that 'split' increases monotonously.
    ('l' and 'r' just specify the region to be searched in 'ary')
    '''

    left = ary_func(ary, l, split)
    right = ary_func(ary, split, r)
    val = comb_func(left, right)

    for i in range(split + 1, r):
        tmp_left = ary_func(ary, l, i)
        tmp_right = ary_func(ary, i, r)
        tmp_val = comb_func(tmp_left, tmp_right)

        if comp_func(val, tmp_val):
            return i - 1, val, left, right
        else:
            left = tmp_left
            right = tmp_right
            val = tmp_val

    else:
        return r - 1, val, left, right


if __name__ == '__main__':
    from operator import add
    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):
        # left
        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)

        # right
        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: Wrong Answer

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


def two_pointers(ary, l, r, split, ary_func, comb_func, comp_func):
    '''
    This function is supposed to be repeatedly called so that 'split' keeps
    renewing, under an assumption that 'split' increases monotonously.
    ('l' and 'r' just specify the region to be searched in 'ary')
    '''

    left = ary_func(ary, l, split)
    right = ary_func(ary, split, r)
    val = comb_func(left, right)

    for i in range(split + 1, r):
        tmp_left = ary_func(ary, l, i)
        tmp_right = ary_func(ary, i, r)
        tmp_val = comb_func(tmp_left, tmp_right)

        if comp_func(val, tmp_val):
            return i - 1, val, left, right
        else:
            left = tmp_left
            right = tmp_right
            val = tmp_val

    else:
        return r - 1, val, left, right


if __name__ == '__main__':
    n = int(input())
    a = [int(_) for _ in input().split()]
    cul_ary = [0] + list(accumulate(a))

    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: Wrong Answer

Solution code:
MAX = 10 ** 10
def m():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(1,n):
        a[i] += a[i-1]
    ans = MAX
    left_i = 0
    right_i = 2
    for i in range(1,n-2):
        p,q = MAX,MAX
        r,s = MAX,MAX
        left_diff = MAX
        right_diff = MAX
        while left_i < i:
            d = abs(a[left_i] - (a[i]-a[left_i]))
            if d < left_diff:
                left_diff = d
                p = a[left_i]
                q = a[i]-a[left_i]
            else:
                break
            left_i += 1
        left_i -=1

        if right_i <= i:
            right_i = i+1

        while right_i < n-1:
            d = abs((a[right_i] - a[i]) - (a[n-1] - a[right_i]))
            if d < right_diff:
                right_diff = d
                r = a[right_i] - a[i]
                s = a[n-1] - a[right_i]
            else:
                break
            right_i += 1
        right_i -= 1

        ans = min(ans, max(p,q,r,s) - min(p,q,r,s))
    return ans

print(m())

Submission status: Wrong Answer

Solution code:
MAX = 10 ** 10
def m():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(1,n):
        a[i] += a[i-1]
    ans = MAX
    left_i = 0
    right_i = 2
    for i in range(1,n-2):
        p,q = MAX,MAX
        r,s = MAX,MAX
        left_diff = MAX
        right_diff = MAX
        while left_i < i:
            d = abs(a[left_i] - (a[i]-a[left_i]))
            if d <= left_diff:
                left_diff = d
                p = a[left_i]
                q = a[i]-a[left_i]
            else:
                break
            left_i += 1
        left_i -=1

        if right_i <= i:
            right_i = i+1

        while right_i < n:
            d = abs((a[right_i] - a[i]) - (a[n-1] - a[right_i]))
            if d <= right_diff:
                right_diff = d
                r = a[right_i] - a[i]
                s = a[n-1] - a[right_i]
            else:
                break
            right_i += 1
        right_i -= 1

        ans = min(ans, max(p,q,r,s) - min(p,q,r,s))
    return ans

print(m())

Submission status: Wrong Answer

Solution code:
MAX = 10 ** 10
def m():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(1,n):
        a[i] += a[i-1]
    ans = MAX
    left_i = 0
    right_i = 2
    for i in range(1,n-2):
        p,q = MAX,MAX
        r,s = MAX,MAX
        left_diff = MAX
        right_diff = MAX
        while left_i < i:
            d = abs(a[left_i] - (a[i]-a[left_i]))
            if d < left_diff:
                left_diff = d
                p = a[left_i]
                q = a[i]-a[left_i]
            else:
                break
            left_i += 1
        left_i -=1

        if right_i <= i:
            right_i = i+1

        while right_i < n:
            d = abs((a[right_i] - a[i]) - (a[n-1] - a[right_i]))
            if d < right_diff:
                right_diff = d
                r = a[right_i] - a[i]
                s = a[n-1] - a[right_i]
            else:
                break
            right_i += 1
        right_i -= 1

        ans = min(ans, max(p,q,r,s) - min(p,q,r,s))
    return ans

print(m())