Problem:


Score : 600 points

Problem Statement

Snuke has an integer sequence A of length N.

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

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

Constraints

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

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

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

Sample Input 1

5
3 2 4 1 2

Sample Output 1

2

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

Sample Input 2

10
10 71 84 33 6 47 23 25 52 64

Sample Output 2

36

Sample Input 3

7
1 2 3 1000000000 4 5 6

Sample Output 3

999999994



Sample input:
5
3 2 4 1 2


Sample output:
2

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
#N = 7
#A = list(map(int,"1 2 3 1000000000 4 5 6".split()))
AA = [0  for x in range(N)]
for i,a in enumerate(A):
    AA[i] = sum(A[:i]) + a
ans = 99999999999999999
ed = 2
st = 0
_bc = AA[-1]
_de = AA[-1]
for i in range(1,N-2):
    for j in range(st,i):
        B = AA[j]
        C = AA[i] - AA[j]
        if abs(B -C) <= _bc:
            _bc = abs(B -C)
        else:
            st = j -1
            _bc = abs(2 * AA[j-1] - AA[i+1])
            B = AA[j-1]
            C = AA[i] - AA[j-1]
            break
    for k in range(ed,N-1):
        D = AA[k] - AA[i]
        E = AA[-1] - AA[k]
        if _de >= abs(D-E):
            _de = abs(D-E)
        else:
            ed = k 
            _de = abs(2 * AA[k-1] - AA[i+1] -AA[-1])
            D = AA[k-1] - AA[i]
            E = AA[-1] - AA[k-1]
            break
    sample = max([abs(B-C),abs(B-D),abs(B-E),abs(C-D),abs(C-E),abs(D-E)])
    print(sample)
    if ans > sample:
        ans = sample
        #print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
#N = int(input())
#A = list(map(int,input().split()))
N = 7
A = list(map(int,"1 2 3 1000000000 4 5 6".split()))
AA = [0  for x in range(N)]
for i,a in enumerate(A):
    AA[i] = sum(A[:i]) + a
ans = 99999999999999999
ed = 2
st = 0
_bc = AA[-1]
_de = AA[-1]
for i in range(1,N-2):
    for j in range(st,i):
        B = AA[j]
        C = AA[i] - AA[j]
        if abs(B -C) <= _bc:
            _bc = abs(B -C)
        else:
            st = j -1
            _bc = abs(2 * AA[j-1] - AA[i+1])
            B = AA[j-1]
            C = AA[i] - AA[j-1]
            break
    for k in range(ed,N-1):
        D = AA[k] - AA[i]
        E = AA[-1] - AA[k]
        if _de >= abs(D-E):
            _de = abs(D-E)
        else:
            ed = k 
            _de = abs(2 * AA[k-1] - AA[i+1] -AA[-1])
            D = AA[k-1] - AA[i]
            E = AA[-1] - AA[k-1]
            break
    sample = max([abs(B-C),abs(B-D),abs(B-E),abs(C-D),abs(C-E),abs(D-E)])
    print(sample)
    if ans > sample:
        ans = sample
        #print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
#N = 10
#A = list(map(int,"10 71 84 33 6 47 23 25 52 64".split()))
AA = []
for i,a in enumerate(A):
    if i == 0:
        AA.append(a)
    else:
        AA.append(AA[-1] + a)
ans = 99999999999999999
ed = 2
st = 0
_bc = AA[-1]
_de = AA[-1]
for i in range(1,N-2):
    for j in range(st,i):
        B = AA[j]
        C = AA[i] - AA[j]
        if abs(B -C) <= _bc:
            _bc = abs(B -C)
        else:
            st = j -1
            _bc = abs(2 * AA[j-1] - AA[i+1])
            B = AA[j-1]
            C = AA[i] - AA[j-1]
            break
    for k in range(ed,N-1):
        D = AA[k] - AA[i]
        E = AA[-1] - AA[k]
        if _de >= abs(D -E):
            _de = abs(D-E)
        else:
            ed = k
            _de = abs(2 * AA[k-1] - AA[i+1] -AA[-1])
            D = AA[k-1] - AA[i]
            E = AA[-1] - AA[k-1]
            break
    sample = max([abs(B-C),abs(B-D),abs(B-E),abs(C-D),abs(C-E),abs(D-E)])
    if ans > sample:
        ans = sample
        bB = B
        bC = C
        bD = D
        bE = E
print(ans)

Submission status: Wrong Answer

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

ans = float('inf')
i1, i3 = 1, 3
s = [aaa[0], aaa[1], aaa[2], sum(aaa[3:])]
for i2 in range(2, n - 1):
    if i2 == i3:
        i3 += 1
        s[2] += aaa[i3]
        s[3] -= aaa[i3]
    while i1 < i2 - 1 and abs(s[0] - s[1]) > abs(s[0] - s[1] + 2 * aaa[i1]):
        s[0] += aaa[i1]
        s[1] -= aaa[i1]
        i1 += 1
    while i3 < n - 1 and abs(s[2] - s[3]) > abs(s[2] - s[3] + 2 * aaa[i3]):
        s[2] += aaa[i3]
        s[3] -= aaa[i3]
        i3 += 1
    ans = min(ans, max(s) - min(s))
    s[1] += aaa[i2]
    s[2] -= aaa[i2]

print(ans)

Submission status: Wrong Answer

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

# cumsum from left
a = 0
A_left = []
for i in range(N):
    a += A_list[i]
    A_left.append(a)
    
# cumsum from right
a = 0
A_right = []
for i in range(N):
    a += A_list[N-1-i]
    A_right.append(a)

def binary_search(a_list, s):
    m = 0
    l = 0
    r = len(a_list) - 1
    
    ### cond ###
    if a_list[m] <= s and a_list[m+1] > s:
        r = l+1
        
    while l < r - 1:
        m = (l + r) // 2
        
        if a_list[m] <= s and a_list[m+1] > s:
            break
        elif a_list[m] <= s:
            l = m
        else:
            r = m
    if s - a_list[m] <= a_list[m+1] - s:
        return m
    else:
        return m+1
    
# B | C split
res = A_left[N-1]
for s in range(2, N-1):
    
    m_l = binary_search(A_left[:s], A_left[s-1]/2)
    a, b = A_left[m_l], A_left[s-1] - A_left[m_l]
    r = N - s 
    m_r = binary_search(A_right[:r], A_right[r-1]/2)
    c, d = A_right[m_r], A_right[r-1] - A_right[m_r]
    
    r = max([a,b,c,d]) - min([a,b,c,d])
    if r < res:
        res = r
if N == 4:
    res = max(A_list) - min(A_list)
print(res)

Submission status: Wrong Answer

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


N = int(input())
A = [0] + list(map(int, input().split()))


def check(mid, base): # b is max-value
    if mid < base:
        l = imos[mid-1]
        r = imos[base-1] - imos[mid-1]
        return abs(r-l)
    else:
        l = imos[mid] - imos[base-1]
        r = imos[N] - imos[mid]
        return abs(r-l)
        
        

def ternarySearchInt(small, big, i):
    if big - small <= 2:  # 終了条件
        mid = (big + small) // 2
        if check(small, i) <= check(mid, i):
            return small
        else:
            return mid if check(mid, i) <= check(big, i) else big
    else:
        midl = (big + small) // 2
        midr = midl + 1
        if check(midl, i) >= check(midr, i):
            return ternarySearchInt(midl, big, i)
        else:
            return ternarySearchInt(small, midr, i)



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

ans = int(1e18)
for i in range(3, N):
    l = ternarySearchInt(1, i-1, i)
    r = ternarySearchInt(i, N, i)
    P = imos[l-1]
    Q = imos[i-1] - P
    R = imos[r] - imos[i-1]
    S = imos[N] - imos[r]
    hoge = [P,Q,R,S]
    ans = min(ans, max(hoge) - min(hoge))


print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
n = int(input())
a = [int(x) for x in input().split()]
 
r = 0
s = []
for i in a:
  r += i
  s.append(r)

def bs(x,y):
  b = bisect(x, y)
  if abs(x[b-1] - y) < abs(x[b] - y):
    b = b-1
  return b
 
m = 10**20
for i in range(2, n-1):
  k = bs(s, s[i] / 2)
  l = bs(s, (s[n-1] + s[i]) / 2)
  s4 = [s[k],s[i]-s[k],s[l]-s[i],s[n-1]-s[l]]
  m = min(m, max(s4) - min(s4))

print(m)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))



def solve(x):
  def h(i,j):
    m = (C[j]+C[i])//2
    k = bisect(C, m, lo=i+1,hi=j)

    _,a,b = min((abs(m-C[x]),C[x]-C[i],C[j]-C[x]) for x in (k-1,k))
    return a,b

  L = h(0,x)+h(x,N)
  return max(L)-min(L)

m = bisect(C,C[N]//2,hi=2,lo=N-2)

best = solve(m)

i = m+1
while i < N-1 and abs(abs(C[N]-C[i])-abs(C[i])) < best*2:
  best = min(best, solve(i))
  i += 1

i = m-1
while i > 1 and abs(abs(C[N]-C[i])-abs(C[i])) < best*2:
  best = min(best, solve(i))
  i -= 1


print(best)

Submission status: Wrong Answer

Solution code:
_ = input()
aa = list(map(int, input().split()))

diff = 1000000000
for i in range(1, len(aa) - 3):
    p = sum(aa[:i])
    j = i + 1
    k = len(aa) - 2
    while j < k:
        q0 = sum(aa[i:j])
        r0 = sum(aa[j:k])
        s0 = sum(aa[k:len(aa)])
        bottom0 = min(p, q0, r0, s0)
        up0 = max(p, q0, r0, s0)
        diff0 = abs(up0 - bottom0)

        next_j = j + 1
        q1 = sum(aa[i:next_j])
        r1 = sum(aa[next_j:k])
        s1 = sum(aa[k:len(aa)])
        bottom1 = min(p, q1, r1, s1)
        up1 = max(p, q1, r1, s1)
        diff1 = abs(up1 - bottom1)

        next_k = k - 1
        q2 = sum(aa[i:j])
        r2 = sum(aa[j:next_k])
        s2 = sum(aa[next_k:len(aa)])
        bottom2 = min(p, q2, r2, s2)
        up2 = max(p, q2, r2, s2)
        diff2 = abs(up2 - bottom2)
        if diff1 < diff0 and diff1 < diff2:
            j = next_j
            diff = min(diff1, diff)
        elif diff2 < diff0 and diff2 < diff1:
            k = next_k
            diff = min(diff2, diff)
        else:
            diff = min(diff0, diff)
            j = k  # break

print(diff)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
Acum = A.cumsum()
total = Acum[-1]

best = float('inf')

a_idx = (N-4, N-3)
for i in range(N-3):
    if Acum[i] > total / 4:
        a_idx = (i-1, i)
        break
for a in a_idx:
    rem = total - Acum[a]
    b_idx = (N-3,N-2)
    for i in range(a, N-2):
        if Acum[i] - Acum[a] > rem / 3:
            b_idx = (i-1, i)
            break
    for b in b_idx:
        rem = total - Acum[b]
        c_idx = (N-2,N-1)
        for i in range(b, N-1):
            if Acum[i] - Acum[b] > rem / 2:
                c_idx = (i-1, i)
                break
        for c in c_idx:
            q = [Acum[a], Acum[b]-Acum[a], Acum[c]-Acum[b], total - Acum[c]]
            score = max(q) - min(q)
            best = min(best, score)
print(best)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
l1,l2,l3=1,2,3
b1,b2,b3=0,0,0
count=0
ans=10**7
while  b1!=l1 and b2!=l2 and b3!=l3: 
    b1,b2,b3=l1,l2,l3
    sa=sum(a[:l1])
    sb=sum(a[l1:l2])
    sc=sum(a[l2:l3])
    sd=sum(a[l3:])
    mn=min(sa,sb,sc,sd)
    mx=max(sa,sb,sc,sd)
    print(sa,sb,sc,sd,mn)
    
    if sa==mn:l1+=1
    elif sb==mn:l2+=1
    elif sc==mn:l3+=1
    
    if l1==l2:l2+=1
    if l2==l3:l3+=1
    ans=min(ans,mx-mn)
    
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect_left

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))

def helper(i,j):
  m = (C[j]+C[i])//2
  k = bisect_left(C, m, lo=i+1,hi=j-1)

  if k > i+1:
    _,a,b = min((abs(m-C[x]),C[x]-C[i],C[j]-C[x]) for x in (k-1,k))
  else:
    a,b = C[k]-C[i],C[j]-C[k]
  return a,b


m = bisect_left(C,C[N]//2)
if m < 2:
  m = 2
elif m > N-2:
  m = N-2

L = helper(0,m)+helper(m,N)
best = max(L)-min(L)

i = m+1
while i < N-1 and abs(abs(C[N]-C[i])-abs(C[i])) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i += 1

i = m-1
while i > 1 and abs(abs(C[N]-C[i])-abs(C[i])) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i -= 1


print(best)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = 10**10
indexm = 0
for i in range(2, n - 1):
    if m > abs(sum(a[i:]) - sum(a[:i])):
        m = abs(sum(a[i:]) - sum(a[:i]))
        indexm = i
m = 10**10
indexl = 0
for i in range(1, indexm):
    if m > abs(sum(a[i:indexm]) - sum(a[:i])):
        m = abs(sum(a[i:indexm]) - sum(a[:i]))
        indexl = i
m = 10**10
indexr = 0
for i in range(indexm, n):
    if m > abs(sum(a[i:]) - sum(a[indexm:i])):
        m = abs(sum(a[i:]) - sum(a[indexm:i]))
        indexr = i
ans = sorted([sum(a[:indexl]),sum(a[indexl:indexm]),sum(a[indexm:indexr]),sum(a[indexr:])])
print(ans[3] - ans[0])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 20

n = int(input())
alst = list(map(int, input().split()))
cums = [0]
acc = 0
for a in alst:
  acc += a
  cums.append(acc)

ans = INF
suma = acc
c1 = bl(cums, suma // 4)
c2 = bl(cums, suma // 4)
c3 = bl(cums, suma // 4)
for pos1 in range(c1 - 50, c1 + 50):
  for pos2 in range(c2 - 50, c2 + 50):
    for pos3 in range(c3 - 50, c3 + 50):
      if 1 <= pos1 < pos2 < pos3 < n:
        p = cums[pos1]
        q = cums[pos2] - cums[pos1]
        r = cums[pos3] - cums[pos2]
        s = suma - cums[pos3]
        ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def ii():
    return int(input())


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def separate2(A, min_i=0, s=None):
    if s is None:
        s = sum(A)
    k = 0
    N = len(A)
    for i in range(min_i, N-1):
        if k >= s // 2:
            if i > 0:
                kk = k - A[i-1]
                if abs(k - (s-k)) < abs(kk - (s - kk)):
                    return i, k, s-k
                else:
                    return i-1, kk, s-kk
            else:
                return i, k, s-k

        k += A[i]

    return N-1, s-A[-1], A[-1]


def max_min_diff(*args):
    return max(args) - min(args)


def main():
    N = ii()
    A = lii()
    lix = 1
    P = A[0]
    Q = A[1]
    rix, R, S = separate2(A[2:])
    rix += 2
    res = max_min_diff(P, Q, R, S)

    for ix in range(2, N-2+1):
        Q += A[ix]
        R -= A[ix]
        while True:
            if abs((P + A[lix]) - (Q - A[lix])) < abs(P - Q):
                P += A[lix]
                Q -= A[lix]
                lix += 1
            else:
                break

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

        res = min(res, max_min_diff(P, Q, R, S))

    return res


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 20

n = int(input())
alst = list(map(int, input().split()))
cums = [0]
acc = 0
for a in alst:
  acc += a
  cums.append(acc)

ans = INF
suma = acc
c1 = bl(cums, suma // 4)
c2 = bl(cums, suma // 4)
c3 = bl(cums, suma // 4)
for pos1 in range(c1 - 10, c1 + 10):
  for pos2 in range(c2 - 10, c2 + 10):
    for pos3 in range(c3 - 10, c3 + 10):
      if 1 <= pos1 < pos2 < pos3 < n:
        p = cums[pos1]
        q = cums[pos2] - cums[pos1]
        r = cums[pos3] - cums[pos2]
        s = suma - cums[pos3]
        ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
X = sum(A) / 4

i = 0
tmp = 0
B, C, D, E = [], [], [], []
while i < N - 3:
    B.append(A[i])
    tmp += A[i]
    i += 1
    if tmp > X or i == N -4:
        #print(B, tmp)
        if abs(X - (tmp - A[i-1])) < (tmp - X) and len(B) > 1:
            del B[-1]
            i -= 1
        break

tmp = 0
while i < N - 2:
    C.append(A[i])
    tmp += A[i]
    i += 1
    if tmp > X or i == N - 3:
        #print(X, tmp, C)
        if abs(X - (tmp - A[i-1])) < (tmp - X) and len(C) > 1:
            del C[-1]
            i -= 1
        break

tmp = 0
while i < N -1:
    D.append(A[i])
    tmp += A[i]
    i += 1
    if tmp > X:
        if abs(X - (tmp - A[i-1])) < (tmp - X) and len(D) > 1:
            del D[-1]
            i -= 1
        break

tmp = 0
while i < N:
    E.append(A[i])
    tmp += A[i]
    i += 1

#print(B, C, D, E)
P, Q, R, S = sum(B), sum(C), sum(D), sum(E)
print(max(P, Q, R, S) - min(P, Q, R, S))

Submission status: Wrong Answer

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

# cumsum from left
a = 0
A_left = []
for i in range(N):
    a += A_list[i]
    A_left.append(a)
    
# cumsum from right
a = 0
A_right = []
for i in range(N):
    a += A_list[N-1-i]
    A_right.append(a)

# binary search
def search_left(n):
    # 0:n
    S = A_left[n-1]
    S2 = S / 2
    
    left = 0
    right = n-1
    
    temp = abs(S2 - A_left[0])
    
    min_s = min([A_right[0], S - A_right[0]])
    max_s = S - min_s
       
    
    while left <= right:
        center = (left + right) // 2 
        
        if abs(S2 - A_left[center]) < temp:
            min_s = min([A_left[center], S - A_left[center]])
            max_s = S - min_s 
            temp = abs(S2 - A_left[center])

        if A_left[center] < S2:
            left = center+1
        else:
            right = center-1
        
    return min_s, max_s
    
def search_right(n):
    # 0:n
    S = A_right[n-1]
    S2 = S / 2
    
    left = 0
    right = n-1
    
    temp = abs(S2 - A_right[0])
    
    min_s = min([A_right[0], S - A_right[0]])
    max_s = S - min_s
    
    
    while  left <= right:
        center = (left + right) // 2
        
        if abs(S2 - A_right[center]) < temp:
            min_s = min([A_right[center], S - A_right[center]])
            max_s = S - min_s 
            temp = abs(S2 - A_right[center])

        if A_right[center] < S2:
            left = center+1
        else:
            right = center-1
            
    return min_s, max_s

# B | C split
res = A_left[N-1]
for s in range(2, N-1):
    a, b = search_left(s)
    c, d = search_right(N-s)
    r = max([a,b,c,d]) - min([a,b,c,d])
    if r < res:
        res = r
if N == 4:
    res = max(A_list) - min(A_list)
print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = 10**10
indexm = 0
for i in range(2, n - 1):
    if m > abs(sum(a[i:]) - sum(a[:i])):
        m = abs(sum(a[i:]) - sum(a[:i]))
        indexm = i
m = 10**10
indexl = 0
for i in range(1, indexm):
    if m > abs(sum(a[i:indexm]) - sum(a[:i])):
        m = abs(sum(a[i:indexm]) - sum(a[:i]))
        indexl = i
m = 10**10
indexr = 0
for i in range(indexm, n):
    if m > abs(sum(a[i:]) - sum(a[indexm:i])):
        m = abs(sum(a[i:]) - sum(a[indexm:i]))
        indexr = i
ans = sorted([sum(a[:indexl]),sum(a[indexl:indexm]),sum(a[indexm:indexr]),sum(a[indexr:])])
print(ans[3] - ans[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
X = sum(A) / 4

i = 1
tmp = 0
B, C, D, E = [], [], [], []
B.append(A[0])
while i < N - 3:
    B.append(A[i])
    tmp += A[i]
    i += 1
    if tmp > X or i == N -4:
        #print(B, tmp)
        if abs(X - (tmp - A[i-1])) < (tmp - X) and len(B) > 1:
            del B[-1]
            i -= 1
        break

tmp = 0
while i < N - 2:
    C.append(A[i])
    tmp += A[i]
    i += 1
    if tmp > X or i == N - 3:
        #print(X, tmp, C)
        if abs(X - (tmp - A[i-1])) < (tmp - X) and len(C) > 1:
            del C[-1]
            i -= 1
        break

tmp = 0
while i < N -1:
    D.append(A[i])
    tmp += A[i]
    i += 1
    if tmp > X:
        if abs(X - (tmp - A[i-1])) < (tmp - X) and len(D) > 1:
            del D[-1]
            i -= 1
        break

tmp = 0
while i < N:
    E.append(A[i])
    tmp += A[i]
    i += 1

#print(B, C, D, E)
P, Q, R, S = sum(B), sum(C), sum(D), sum(E)
print(max(P, Q, R, S) - min(P, Q, R, S))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))

def helper(i,j):
  m = (C[j]+C[i])//2
  k = bisect(C, m, lo=i+1,hi=j-1)

  if k > i+1:
    _,a,b = min((abs(m-C[x]),C[x]-C[i],C[j]-C[x]) for x in (k-1,k))
  else:
    a,b = C[k]-C[i],C[j]-C[k]
  return a,b


m = bisect(C,C[N]//2)
if m < 2:
  m = 2
elif m > N-2:
  m = N-2

L = helper(0,m)+helper(m,N)
best = max(L)-min(L)

i = m+1
while i < N-1 and abs(abs(C[N]-C[i])-abs(C[i])) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i += 1

i = m-1
while i > 1 and abs(abs(C[N]-C[i])-abs(C[i])) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i -= 1


print(best)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))

def helper(i,j):
  m = (C[j]+C[i])//2
  k = bisect(C, m, lo=i+1,hi=j-1)

  if k > i+1:
    _,a,b = min((abs(m-C[x]),C[x]-C[i],C[j]-C[x]) for x in (k-1,k))
  else:
    a,b = C[k]-C[i],C[j]-C[k]
  return a,b

m = bisect(C,C[N]//2)
if m < 2:
  m = 2
elif m > N-2:
  m = N-2

L = helper(0,m)+helper(m,N)
best = max(L)-min(L)

i = m+1
while i < N-1 and (2*C[i]-C[N]) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i += 1

i = m-1
while i > 1 and (C[N]-2*C[i]) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i -= 1


print(best)

Submission status: Wrong Answer

Solution code:

import statistics
import math



n = int(input())
A = list(map(int, input().split()))
ans = 0
for a in A:
    ans += a
med = ans/4

tmp = [0,0,0,0]
a_i = 0
for j in range(4):
    tmp[j] += A[a_i]
    a_i += 1
    while a_i < len(A) - 3 + j:
        if abs(tmp[j] - med) < abs(tmp[j] + A[a_i] - med):
            break
        tmp[j] += A[a_i]
        a_i += 1
    # print(tmp)
print(max(tmp)-min(tmp))





# while True:
#     A_2 = []
#
#     for i in range(len(A) - 1):
#         A_2.append(A[i] + A[i + 1])
#
#     A_2_min = min(A_2)
#     min_num = A_2.index(A_2_min)
#
#     A[min_num] = A_2_min
#     A.pop(min_num + 1)
#     print(A)
#     if len(A) == 4:
#         break


# print(max(A)-min(A))

Submission status: Wrong Answer

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

# cumsum from left
a = 0
A_left = []
for i in range(N):
    a += A_list[i]
    A_left.append(a)
    
# cumsum from right
a = 0
A_right = []
for i in range(N):
    a += A_list[N-1-i]
    A_right.append(a)

# binary search
def search_left(n):
    # 0:n
    S = A_left[n-1]
    S2 = S / 2
    
    left = 0
    right = n-1
    
    temp = abs(S2 - A_left[0])
    
    min_s = min([A_right[0], S - A_right[0]])
    max_s = S - min_s
    center = (left + right) // 2    
    
    while left < right - 1:

        if abs(S2 - A_left[center]) < temp:
            min_s = min([A_left[center], S - A_left[center]])
            max_s = S - min_s 
            temp = abs(S2 - A_left[center])

        if A_left[center] < S2:
            left, center = center, (center+right) // 2
        else:
            right, center = center, (center+left) // 2
            
    if abs(S2 - A_left[center]) < temp:
        min_s = min([A_left[center], S - A_left[center]])
        max_s = S - min_s 
        temp = abs(S2 - A_left[center])
    if abs(S2 - A_left[right]) < temp:
        min_s = min([A_left[right], S - A_left[right]])
        max_s = S - min_s 
        temp = abs(S2 - A_left[right])
        
    return min_s, max_s
    
def search_right(n):
    # 0:n
    S = A_right[n-1]
    S2 = S / 2
    
    left = 0
    right = n-1
    
    temp = abs(S2 - A_right[0])
    
    min_s = min([A_right[0], S - A_right[0]])
    max_s = S - min_s
    center = (left + right) // 2
    
    while left < right - 1:
        
        if abs(S2 - A_right[center]) < temp:
            min_s = min([A_right[center], S - A_right[center]])
            max_s = S - min_s 
            temp = abs(S2 - A_right[center])

        if A_right[center] < S2:
            left, center = center, (center+right) // 2
        else:
            right, center = center, (center+left) // 2
            
    if abs(S2 - A_right[center]) < temp:
        min_s = min([A_right[center], S - A_right[center]])
        max_s = S - min_s 
        temp = abs(S2 - A_right[center])
    if abs(S2 - A_right[right]) < temp:
        min_s = min([A_right[right], S - A_right[right]])
        max_s = S - min_s 
        temp = abs(S2 - A_right[right])
    return min_s, max_s

# B | C split
res = A_left[N-1]
for s in range(2, N-1):
    a, b = search_left(s)
    c, d = search_right(N-s)
    r = max([a,b,c,d]) - min([a,b,c,d])
    if r < res:
        res = r
if N == 4:
    res = max(A_list) - min(A_list)
print(res)

Submission status: Wrong Answer

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



a1 = 0
b1 = sum(l)
for i in range(N):
    c1 = abs(a1-b1)
    a1 += l[i]
    b1 -= l[i]
    if c1 < abs(a1-b1):
        break

def func(i):
    a2 = 0
    b2 = sum(l[:i])
    for j in range(i):
        c2 = abs(a2-b2)
        a2 += l[j]
        b2 -= l[j]
        if c2 < abs(a2-b2):
            a2 -=l[j]
            b2 +=l[j]
            break
    a3 = 0
    b3 = sum(l[i:])
    for k in range(i,N):
        c3 = abs(a3-b3)
        a3 += l[k]
        b3 -= l[k]
        if c3< abs(a3-b3):
            a3 -=l[k]
            b3 +=l[k]
            break
    a1 = 0
    b1 = sum(l[j:k])
    for m in range(j,k):
        c1 = abs(a1-b1)
        a1 += l[m]
        b1 -= l[m]
        if c1< abs(a1-b1):
            a1 -=l[m]
            b1 +=l[m]
            break
    return a2,a1,b1,b3,m

a2,a1,b1,b3,m = func(i)
mem = max(a2,a1,b1,b3)-min(a2,a1,b1,b3)

while 1 :
    a2,a1,b1,b3,m = func(m)
    if max(a2,a1,b1,b3)-min(a2,a1,b1,b3) == mem:
        break

print(mem)

Submission status: Wrong Answer

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

# cumsum from left
a = 0
A_left = []
for i in range(N):
    a += A_list[i]
    A_left.append(a)
    
# cumsum from right
a = 0
A_right = []
for i in range(N):
    a += A_list[N-1-i]
    A_right.append(a)

# binary search
def search_left(n):
    # 0:n
    S = A_left[n-1]
    S2 = S / 2
    
    left = 0
    right = n-1
    
    temp = abs(S2 - A_left[0])
    
    min_s = min([A_right[0], S - A_right[0]])
    max_s = S - min_s
    center = (left + right) // 2    
    
    while left < right - 1:

        if abs(S2 - A_left[center]) < temp:
            min_s = min([A_left[center], S - A_left[center]])
            max_s = S - min_s 
            temp = abs(S2 - A_left[center])

        if A_left[center] < S2:
            left, center = center, (center+right) // 2
        else:
            right, center = center, (center+left) // 2
            
    if abs(S2 - A_left[left]) < temp:
        min_s = min([A_left[left], S - A_left[left]])
        max_s = S - min_s 
        temp = abs(S2 - A_left[left])
    if abs(S2 - A_left[right]) < temp:
        min_s = min([A_left[right], S - A_left[right]])
        max_s = S - min_s 
        temp = abs(S2 - A_left[right])
        
    return min_s, max_s
    
def search_right(n):
    # 0:n
    S = A_right[n-1]
    S2 = S / 2
    
    left = 0
    right = n-1
    
    temp = abs(S2 - A_right[0])
    
    min_s = min([A_right[0], S - A_right[0]])
    max_s = S - min_s
    center = (left + right) // 2
    
    while left < right - 1:
        
        if abs(S2 - A_right[center]) < temp:
            min_s = min([A_right[center], S - A_right[center]])
            max_s = S - min_s 
            temp = abs(S2 - A_right[center])

        if A_right[center] < S2:
            left, center = center, (center+right) // 2
        else:
            right, center = center, (center+left) // 2
            
    if abs(S2 - A_right[left]) < temp:
        min_s = min([A_right[left], S - A_right[left]])
        max_s = S - min_s 
        temp = abs(S2 - A_right[left])
    if abs(S2 - A_right[right]) < temp:
        min_s = min([A_right[right], S - A_right[right]])
        max_s = S - min_s 
        temp = abs(S2 - A_right[right])
    return min_s, max_s

# B | C split
res = A_left[N-1]
for s in range(2, N-1):
    a, b = search_left(s)
    c, d = search_right(N-s)
    r = max([a,b,c,d]) - min([a,b,c,d])
    if r < res:
        res = r
if N == 4:
    res = max(A_list) - min(A_list)
print(res)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))

def helper(i,j):
  m = (C[j]+C[i])//2
  k = bisect(C, m, lo=i+2,hi=j-1)

  _,a,b = min((abs(m-C[x]),C[x]-C[i],C[j]-C[x]) for x in (k-1,k))
  return a,b

m = bisect(C,C[N]/2)
if m < 2:
  m = 2
elif m > N-2:
  m = N-2

L = helper(0,m)+helper(m,N)
best = max(L)-min(L)
i = m+1
while i < N-1 and (2*C[i]-C[N]) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i += 1
i = m-1
while i > 1 and (C[N]-2*C[i]) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i -= 1


print(best)

Submission status: Wrong Answer

Solution code:
import bisect
from itertools import accumulate


def fix(aac, l, k):
    ofs = aac[l - 1]
    sm = aac[-1] - ofs
    q = sm // k + ofs
    i = bisect.bisect(aac, q, lo=l)
    if i == l:
        i += 1
    print(l, k, sm, q, i, aac[i - 1] - ofs)
    return i


n = int(input())
aaa = list(map(int, input().split()))
aac = [0] + list(accumulate(aaa))
sm = aac[-1]

q1, q2, q3 = sm // 4, sm // 2, sm * 3 // 4

i1 = bisect.bisect(aac, q1)
i2 = bisect.bisect(aac, q2, lo=i1)
i3 = bisect.bisect(aac, q3, lo=i2)

k = 50
ans = float('inf')
for j1 in range(max(1, i1 - k), min(n + 1, i1 + k)):
    for j2 in range(max(j1 + 1, i2 - k), min(n + 1, i2 + k)):
        for j3 in range(max(j2 + 1, i3 - k), min(n + 1, i3 + k)):
            s = [
                aac[j1],
                aac[j2] - aac[j1],
                aac[j3] - aac[j2],
                aac[-1] - aac[j3]
            ]
            ans = min(ans, max(s) - min(s))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))

def helper(i,j):
  m = (C[j]+C[i])//2
  k = bisect(C, m, lo=i+1,hi=j-1)

  _,a,b = min((abs(m-C[x]),C[x]-C[i],C[j]-C[x]) for x in (k-1,k))
  return a,b

m = bisect(C,C[N]/2)
if m < 2:
  m = 2
elif m > N-2:
  m = N-2

L = helper(0,m)+helper(m,N)
best = max(L)-min(L)
i = m+1
while i < N-1 and (2*C[i]-C[N]) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i += 1
i = m-1
while i > 1 and (C[N]-2*C[i]) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i -= 1


print(best)