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:
N = int(raw_input())
a = list(map(int,raw_input().split()))
b = []
ANS = []
x = 0
for i in range(N):
  x += a[i]
  b.append(x)
for j in range(1,N-1):
  A = b[j]
  bnew = list(map(lambda x: abs(2*x-A)))
  c = bnew.index(min(bnew))
  B = b[N]-b[j]
  bnew2 = list(map(lambda x: abs(2*x-2*A-B)))
  d = bnew2.index(min(bnew2))
  kire = [b[c],b[j]-b[c],b[d]-b[j],b[N]-b[d]]
  ans = max(kire)-min(kire)
  ANS.append(ans)
print min(ANS)

Submission status: Runtime Error

Solution code:
cum = np.cumsum(a)
total = np.sum(a)
def find(b, total):
    assert sum(b)==total
#     print("b: ", b)
    thre = total/2
    b = np.cumsum(b)
    out = np.argmin(np.abs(b-thre))
#     print("out:", out)
    return out
#     return np.min(np.where(b>thre)[0])

best = total
for i in range(1,N-2):
    left = cum[i]
    right = total - left
    ileft = find(a[:(i+1)], left)
    iright = find(a[(i+1):], right) + i + 1
    z1 = np.sum(a[:(ileft+1)])
    z2 = left - z1
    z3 = np.sum(a[(i+1):(iright+1)])
    z4 = np.sum(a[(iright+1):])  # right - z3
    M = max([z1,z2,z3,z4])
    m = min([z1,z2,z3,z4])
    best = min(best, M-m)
#     print([z1,z2,z3,z4])
best

Submission status: Runtime Error

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

from itertools import accumulate


ans = float("inf")
if N == 4:
    ans = min(ans, (max(A) - min(A)))
else:
    cs = accumulate(A)
    for i in range(2, N - 2):
        left_cs = cs[:i]
        right_cs = cs[i:]
        for l, v in enumerate(left_cs):
            if v + left_cs[l + 1] >= left_cs[-1]:
                P = left_cs[l]
                Q = left_cs[-1] - P
                break
        for r, v in enumerate(right_cs):
            if v + right_cs[r + 1] >= right_cs[-1]:
                R = right_cs[r]
                S = right_cs[-1] - R
                break
        ans = min(ans, (max(P, Q, R, S) - min(P, Q, R, S)))

print(ans)

Submission status: Runtime Error

Solution code:
mp.put(ps.RunID,ps);

Submission status: Runtime Error

Solution code:
a=int(input())
for i in range(1,10000000):
  pass
print(a+b)

Submission status: Runtime Error

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

l, r = a[:2]
m = 1
b = [(l,r)]
for i in range(2, n-2):
    r += a[i]
    for j in range(m, i):
        nl, nr = l+a[j], r-a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m += 1
    b.append((l,r))

l, r = a[-2:]
m = n-2
c = [(l,r)]
for i in range(2, n-2)[::-1]:
    l += a[i]
    for j in range(i+1, m+1)[::-1]:
        nl, nr = l-a[j], r+a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m -= 1
    c.append((l,r))

r = 10**9
for i in range(n-3):
    x = max(*b[i], *c[-i-1])
    y = min(*b[i], *c[-i-1])
    r = min(r, x-y)
print(r,flush=True)

Submission status: Runtime Error

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

l, r = a[:2]
m = 1
b = [(l,r)]
for i in range(2, n-2):
    r += a[i]
    for j in range(m, i):
        nl, nr = l+a[j], r-a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m = j
    else:
        m += 1
    b.append((l,r))

l, r = a[-2:]
m = n-2
c = [(l,r)]
for i in range(2, n-2)[::-1]:
    l += a[i]
    for j in range(i+1, m+1)[::-1]:
        nl, nr = l-a[j], r+a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m = j
    else:
        m -= 1
    c.append((l,r))

r = 10**9
for i in range(n-4):
    x = max(*b[i], *c[-i-1])
    y = min(*b[i], *c[-i-1])
    r = min(r, x-y)

print(r)

Submission status: Runtime Error

Solution code:
from itertools import accumulate

# bisectはどっちでも（どちらに等号をつけても）うまくいくっぽい
from bisect import bisect_right, bisect_left

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

# 累積和を前計算
cumsum = list(accumulate(A))
cumsum.insert(0, 0)  # out of index 対策


ans = float('inf')
# 真ん中を全探索
for i in range(2, N-1):  # 左側は最低2つ残さなきゃいけないから2から(0もあるので）、右も同じ理由でN-1
    # 左の真ん中
    Lmid = cumsum[i] / 2
    
    # 左真ん中がどこに入るべきか
    Lx = bisect_left(cumsum, Lx)
    
    # Lxまで取るのか、Lx-1まで取るのか（どこまで取ると望ましい値Lmidに近づくのか）
    # 左側がLmidに近づくと右側もLmidに近づく→差の絶対値が0に近づく
    if abs(cumsum[Lx-1] - Lmid) < abs(cumsum[Lx] - Lmid):
        Lmid -= 1


    # 右側処理（基本は左と同じ）
    Rmid = (cumsum[N] + cumsum[i]) / 2  # 3分探索に要領でcumsum[i]を加えてやる
    Rx = bisect_left(cumsum, Rmid)
    # 超えるべきか超えないべきか
    if abs(cumsum[Rx-1] - Rmid) < abs(cumsum[Rx] - Rmid):
        Rx -= 1
    
    
    # 左からLx個の和
    P = cumsum[Lx]
    
    # Lx番目+1から真ん中区切りiまでの和
    Q = cumsum[i]-cumsum[Lx]
    
    # 真ん中区切りのi+1番目からRx番目までの和
    R = cumsum[Rx]-cumsum[i]
    
    # Rx+1番目から最後まで
    S = cumsum[N]-cumsum[Rx]
    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n + 1)]
for i in range(n):
	b[i + 1] = b[i] + a[i]
# b[i] = sum(a[:i])

suma = sum(a)
border = suma / 4

def func1(start_index, bit):
	# bit: 0 -> border を超えない, 1 -> border を超える
	end_index = start_index + 1
	
	if bit == 0:
		while b[end_index] - b[start_index] < border:
			end_index += 1
		if end_index == start_index + 1:
			return end_index, b[end_index] - b[start_index]
		else:
			return end_index - 1, b[end_index - 1] - b[start_index]

	elif bit == 1:
		while b[end_index] - b[start_index] < border:
			end_index += 1
		return end_index, b[end_index] - b[start_index]

def func2(bits):
	# bits: 0~7
	starts = [0]
	sums = []

	for i in range(3):
		f = func1(starts[-1], bits % 2)
		bits = bits // 2
		starts.append(f[0])
		sums.append(f[1])

	sums.append(b[n] - b[f[0]])

	return max(sums) - min(sums)

candidates = []

for i in range(8):
	candidates.append(func2(i))

print(min(candidates))

Submission status: Runtime Error

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

left = 0
right = 2
p = a[0]
q = a[1]
res_left = abs(p - q)
r = a[2]
s: int = sum(a[3:])
res_right = abs(r - s)
result = max(p,q,r,s) - min(p,q,r,s)

for i in range(2, n - 2):
    q += a[i]
    r -= a[i]
    if i == right:
        right += 1
        r += a[i + 1]
        s -= a[i + 1]
    res_left = abs(p - q)
    res_right = abs(r - s)
    temp = left + 1
    x = p
    y = q
    while temp < i:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_left:
            left = temp
            p = x
            q = y
            res_left = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp = right + 1
    x = r
    y = s
    while temp < n - 1:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_right:
            right = temp
            r = x
            s = y
            res_right = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp_res = max(p, q, r, s) - min(p, q, r, s)
    if temp_res < result:
        result = temp_res

print(result)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
from bisect import bisect

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

def h(i,j):
  ci,cj = C[i],C[j]
  k = bisect(C, (ci+cj)//2, lo=i+1,hi=j)
  _,a,b = min((abs(ci+cj-2*c),cj-c,c-ci) for c in (C[k-1],C[k]))
  return a,b

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

print(min(solve(i) for i in range(2,N-2)))

Submission status: Runtime Error

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)

print(min(solve(i) for i in range(2,N-2)))

Submission status: Runtime Error

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] + s[i]) / 2)
  s4 = [s[k],s[i]-s[k],s[l]-s[i],s[n]-s[l]]
  m = min(m, max(s4) - min(s4))

print(m)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    s = 0
    SA = sum(A)//2
    for i, a in enumerate(A):
        s += a
        if s > SA:
            break
    
    def h(i):
        s = 0
        SSA = sum(A[:i])
        d = []
        for a in A[:i]:
            s += a
            # print(SSA, s)
            d.append((SSA-s, s))
        # print(d) 
        t0 = min(d, key=lambda  x: abs(x[0]-x[1]))
        s = 0
        SSA = sum(A[i:])
        d = []
        for a in A[i:]:
            s += a
            d.append((SSA-s, s))
        t1 = min(d, key=lambda  x: abs(x[0]-x[1]))

        return t0 + t1

    return min(map(lambda x: abs(max(x) - min(x)),  [h(i), h(i+1), h(i-1)]))


def main():
    N = read_int()
    A = read_int_n() 
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

i = 0
tmp = 0
B, C, D, E = [], [], [], []
while True:
    B.append(A[i])
    tmp += A[i]
    i += 1
    if tmp > X:
        #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 True:
    C.append(A[i])
    tmp += A[i]
    i += 1
    if tmp > X:
        #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 True:
    D.append(A[i])
    tmp += A[i]
    i += 1
    if tmp > X or i == N - 1:
        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: Runtime Error

Solution code:
from itertools import accumulate
from bisect import bisect
N = int(input())
A = list(map(int,input().split()))
C = [0]+list(accumulate(A))

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

  if k > 0:
    _,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

best = float('inf')

for i in range(2,N-1):
  L = (*helper(0,i),*helper(i,N))
  best = min(best,max(L)-min(L))

print(best)