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()))
def check(x):
  d = [0] * 4
  p = 0
  for i in range(N):
    d[p] += a[i]
    if d[p] >= x: p += 1
    if p > 3: p -= 1
  return min(d) >= x
def solve(l, r):
  d=[0]*4
  p=0
  for i in range(N):
    d[p] += a[i]
    if d[p] > r:
      d[p] -= a[i]
      p+=1
      if p > 3: return False
      d[p]+=a[i]
  return min(d[: p+1])>=l
ok = 0
ng = N * max(a)
m = 0
while ng - ok > 1:
  m = (ok + ng) // 2
  if check(m):
    ok = m
  else: ng = m
mn = ok+0
ng = max(mn, max(a)) - 1
ok = N * max(a)
m = 0
while ok - ng > 1:
  m = (ok + ng) // 2
  if solve(mn, m):
    ok = m
  else: ng = m
print(ok-mn)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

S = [0]*N
S[0] = A[0]
for i in range(1, N):
    S[i] = A[i]+S[i-1]
    
ans = 2*10**14
l = 0
temp = 2*10**14
r = 2
for i in range(2, N):
    if abs(S[-1]-2*S[i]+S[1]) < temp:
        temp = abs(S[-1]-2*S[r]+S[1])
        r = i
        
for i in range(2, N-1):
    while l+1 < i-1 and abs(S[i-1]-2*S[l]) > abs(S[i-1]-2*S[l+1]):
        l += 1
    while r+1 < N-1 and abs(S[N-1]-2*S[r]+S[i-1])  > abs(S[N-1]-2*S[r+1]+S[i-1]):
        r += 1
    t = max(S[N-1]-S[r], S[r]-S[i-1], S[i-1]-S[l], S[l]) - min(S[N-1]-S[r], S[r]-S[i-1], S[i-1]-S[l], S[l])
    ans = min(ans, t)
    
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

S = [0]*N
S[0] = A[0]
for i in range(1, N):
    S[i] = A[i]+S[i-1]
    
ans = 10**14
l = 0
temp = 10**14
r = 2
for i in range(2, N):
    if abs(S[-1]-2*S[i]+S[1]) < temp:
        temp = abs(S[-1]-2*S[r]+S[1])
        r = i
        
for i in range(2, N-1):
    while l+1 < i-1 and abs(S[i-1]-2*S[l]) > abs(S[i-1]-2*S[l+1]):
        l += 1
    while r < N-1 and abs(S[N-1]-2*S[r]+S[i-1])  > abs(S[N-1]-2*S[r+1]+S[i-1]):
        r += 1
    t = max(S[N-1]-S[r], S[r]-S[i-1], S[i-1]-S[l], S[l]) - min(S[N-1]-S[r], S[r]-S[i-1], S[i-1]-S[l], S[l])
    ans = min(ans, t)
    
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

S = [0]*N
S[0] = A[0]
for i in range(1, N):
    S[i] = A[i]+S[i-1]
    
ans = 10**14
l = 0
temp = 10**14
r = 2
for i in range(2, N):
    if abs(S[-1]-2*S[i]+S[1]) < temp:
        temp = S[-1]-2*S[r]+S[1]
        r = i
        
for i in range(2, N-1):
    while l+1 < i-1 and abs(S[i-1]-2*S[l]) > abs(S[i-1]-2*S[l+1]):
        l += 1
    while r < N-1 and abs(S[N-1]-2*S[r]+S[i-1])  > abs(S[N-1]-2*S[r+1]+S[i-1]):
        r += 1
    t = max(S[N-1]-S[r], S[r]-S[i-1], S[i-1]-S[l], S[l]) - min(S[N-1]-S[r], S[r]-S[i-1], S[i-1]-S[l], S[l])
    ans = min(ans, t)
    
print(ans)

Submission status: Wrong Answer

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])
la.append(10**16)
la.append(10**16)
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: Wrong Answer

Solution code:
import itertools
import bisect
N = int(input())
A = [int(_) for _ in input().split()]
C = list(itertools.accumulate([0] + A))
ibc = bisect.bisect(C, C[-1] // 2)
iab = 1 + bisect.bisect(C[1:ibc], C[ibc] // 2)
icd = ibc + 1 + bisect.bisect(C[ibc + 1:-1], (C[-1] + C[ibc]) // 2)
ibc2 = ibc - 1
iab2 = 1 + bisect.bisect(C[1:ibc2], C[ibc2] // 2)
icd2 = ibc2 + 1 + bisect.bisect(C[ibc2 + 1:-1], (C[-1] + C[ibc2]) // 2)
ans = float('inf')
for i1, i2, i3 in [[iab, ibc, icd], [iab2, ibc2, icd2]]:
    for d1, d2, d3 in itertools.product(range(-5, 5), repeat=3):
        j1 = i1 + d1
        j2 = i2 + d2
        j3 = i3 + d3
        if 0 < j1 < j2 < j3 < N:
            D = [C[j1], C[j2] - C[j1], C[j3] - C[j2], C[-1] - C[j3]]
            ans = min(ans, max(D) - min(D))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import bisect
N = int(input())
A = [int(_) for _ in input().split()]
C = list(itertools.accumulate([0] + A))
ibc = bisect.bisect(C, C[-1] // 2)
iab = 1 + bisect.bisect(C[1:ibc], C[ibc] // 2)
icd = ibc + 1 + bisect.bisect(C[ibc + 1:-1], (C[-1] + C[ibc]) // 2)
ibc2 = ibc - 1
iab2 = 1 + bisect.bisect(C[1:ibc2], C[ibc2] // 2)
icd2 = ibc2 + 1 + bisect.bisect(C[ibc2 + 1:-1], (C[-1] + C[ibc2]) // 2)
ans = float('inf')
for i1, i2, i3 in [[iab, ibc, icd], [iab2, ibc2, icd2]]:
    for d1, d2, d3 in itertools.product(range(-50, 50), repeat=3):
        j1 = i1 + d1
        j2 = i2 + d2
        j3 = i3 + d3
        if 0 < j1 < j2 < j3 < N:
            D = [C[j1], C[j2] - C[j1], C[j3] - C[j2], C[-1] - C[j3]]
            ans = min(ans, max(D) - min(D))
print(ans)

Submission status: Wrong Answer

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

bl = []
b = 0
for a in al:
    b += a
    bl.append(b)

import bisect

#リストAに値xを入れ、xが複数になるとき、一番右の値xのインデックスを返す
x = bl[-1] // 4
p = bisect.bisect_right(bl,x)
q = bisect.bisect_right(bl,x*2)
r = bisect.bisect_right(bl,x*2)

ans = float("inf")

for i in range(-5,6):
    for j in range(-5,6):
        for k in range(-5,6):
            if 0 <= p+i < n and 0 <= q+j < n and 0 <= r+k < n:
                pp = bl[p+i] 
                qq = bl[q+j]
                kk = bl[r+k]
                if pp < qq and qq < kk:
                    ll = [pp, qq-pp,kk-qq,bl[-1]-kk]
                    tmp = max(ll) - min(ll)
                    if ans > tmp:
                        ans = tmp

print(ans)

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
N = int(input())
A = [int(a) for a in input().split()]
s = sum(A)
S = [0] * (N+1)
for i in range(N):
    S[i+1] = S[i] + A[i]

mi = 1<<100
for i in range(1, N-2):
    sl = S[i]
    sr = s - sl
    a = bl(S, sl//2)
    b = bl(S, sl + sr//2)
    L = [S[a], S[i]-S[a], S[b]-S[i], s-S[b]]
    mi = min(mi, max(L) - min(L))
    L = [S[a], S[i]-S[a], S[b-1]-S[i], s-S[b-1]]
    mi = min(mi, max(L) - min(L))
    if a-1 >= 0:
        L = [S[a-1], S[i]-S[a-1], S[b]-S[i], s-S[b]]
        mi = min(mi, max(L) - min(L))
        L = [S[a-1], S[i]-S[a-1], S[b-1]-S[i], s-S[b-1]]
        mi = min(mi, max(L) - min(L))

print(mi)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right as br
N = int(input())
A = [int(a) for a in input().split()]
s = sum(A)
S = [0] * (N+1)
for i in range(N):
    S[i+1] = S[i] + A[i]

mi = 1<<100
for i in range(1, N-2):
    sl = S[i]
    sr = s - sl
    a = br(S, sl//2)
    b = br(S, sl + sr//2)
    L = [S[a], S[i]-S[a], S[b]-S[i], s-S[b]]
    mi = min(mi, max(L) - min(L))
    L = [S[a], S[i]-S[a], S[b-1]-S[i], s-S[b-1]]
    mi = min(mi, max(L) - min(L))
    if a-1 >= 0:
        L = [S[a-1], S[i]-S[a-1], S[b]-S[i], s-S[b]]
        mi = min(mi, max(L) - min(L))
        L = [S[a-1], S[i]-S[a-1], S[b-1]-S[i], s-S[b-1]]
        mi = min(mi, max(L) - min(L))

print(mi)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

L = [1, 2, 3]
S = [A[0], A[1], A[2], sum(A[3:])]

ans = max(S) - min(S)
while True:
    if S[2] < S[3] and L[2] < N-1:
        S[2] += A[L[2]]
        S[3] -= A[L[2]]
        L[2] += 1
    elif S[1] < S[2] and L[1] + 1 < L[2]:
        S[1] += A[L[1]]
        S[2] -= A[L[1]]
        L[1] += 1
    elif S[1] < S[2] and L[2] < N-1:
        S[1] += A[L[1]]
        S[2] += A[L[2]] - A[L[1]]
        S[3] -= A[L[2]]
        L[1] += 1
        L[2] += 1
    elif S[0] < S[1] and L[0] + 1 < L[1]:
        S[0] += A[L[0]]
        S[1] -= A[L[0]]
        L[0] += 1
    elif S[0] < S[1] and L[1] + 1 < L[2]:
        S[0] += A[L[0]]
        S[1] += A[L[1]] - A[L[0]]
        S[2] -= A[L[1]]
        L[0] += 1
        L[1] += 1
    elif S[0] < S[1] and L[2] < N-1:
        S[0] += A[L[0]]
        S[1] += A[L[1]] - A[L[0]]
        S[2] += A[L[2]] - A[L[1]]
        S[3] -= A[L[2]]
        L[0] += 1
        L[1] += 1
        L[2] += 1     
    else:
        if L[0] + 1 < L[1]:
            S[0] += A[L[0]]
            S[1] -= A[L[0]]
            L[0] += 1
        elif L[1] + 1 < L[2]:
            S[0] += A[L[0]]
            S[1] += A[L[1]] - A[L[0]]
            S[2] -= A[L[1]]
            L[0] += 1
            L[1] += 1
        elif L[2] < N-1:
            S[0] += A[L[0]]
            S[1] += A[L[1]] - A[L[0]]
            S[2] += A[L[2]] - A[L[1]]
            S[3] -= A[L[2]]
            L[0] += 1
            L[1] += 1
            L[2] += 1
        else:
            break
    ans = min(ans, max(S)-min(S))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

L = [1, 2, 3]
S = [A[0], A[1], A[2], sum(A[3:])]

ans = max(S) - min(S)
while True:
    if S[2] < S[3] and L[2] < N-1:
        S[2] += A[L[2]]
        S[3] -= A[L[2]]
        L[2] += 1
    elif S[1] < S[2] and L[1] + 1 < L[2]:
        S[1] += A[L[1]]
        S[2] -= A[L[1]]
        L[1] += 1
    elif S[1] < S[2] and L[2] < N-1:
        S[1] += A[L[1]]
        S[2] += A[L[2]] - A[L[1]]
        S[3] -= A[L[2]]
        L[1] += 1
        L[2] += 1
    elif S[0] < S[1] and L[0] + 1 < L[1]:
        S[0] += A[L[0]]
        S[1] -= A[L[0]]
        L[0] += 1
    elif S[0] < S[1] and L[1] + 1 < L[2]:
        S[0] += A[L[0]]
        S[1] += A[L[1]] - A[L[0]]
        S[2] -= A[L[1]]
        L[0] += 1
        L[1] += 1
    elif S[0] < S[1] and L[2] < N-1:
        S[0] += A[L[0]]
        S[1] += A[L[1]] - A[L[0]]
        S[2] += A[L[2]] - A[L[1]]
        S[3] -= A[L[2]]
        L[0] += 1
        L[1] += 1
        L[2] += 1     
    else:
        break
    ans = min(ans, max(S)-min(S))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

L = [1, 2, 3]
S = [A[0], A[1], A[2], sum(A[3:])]

ans = max(S) - min(S)
while True:
    if S[2] < S[3] and L[2] < N-1:
        S[2] += A[L[2]]
        S[3] -= A[L[2]]
        L[2] += 1
    elif S[1] < S[2] and L[1] + 1 < L[2]:
        S[1] += A[L[1]]
        S[2] -= A[L[1]]
        L[1] += 1
    elif S[0] < S[1] and L[0] + 1 < L[1]:
        S[0] += A[L[0]]
        S[1] -= A[L[0]]
        L[0] += 1
    else:
        if L[0] + 1 < L[1]:
            S[0] += A[L[0]]
            S[1] -= A[L[0]]
            L[0] += 1
        elif L[1] + 1 < L[2]:
            S[0] += A[L[0]]
            S[1] += A[L[1]] - A[L[0]]
            S[2] -= A[L[1]]
            L[0] += 1
            L[1] += 1
        elif L[2] < N-1:
            S[0] += A[L[0]]
            S[1] += A[L[1]] - A[L[0]]
            S[2] += A[L[2]] - A[L[1]]
            S[3] -= A[L[2]]
            L[0] += 1
            L[1] += 1
            L[2] += 1
        else:
            break
    ans = min(ans, max(S)-min(S))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

L = [1, 2, 3]
S = [A[0], A[1], A[2], sum(A[3:])]

ans = max(S) - min(S)
while not (S[0] >= S[1] >= S[2] >= S[3]):
    if S[2] < S[3] and L[2] < N-1:
        S[2] += A[L[2]]
        S[3] -= A[L[2]]
        L[2] += 1
    elif S[1] < S[2] and L[1] + 1 < L[2]:
        S[1] += A[L[1]]
        S[2] -= A[L[1]]
        L[1] += 1
    elif S[0] < S[1] and L[0] + 1 < L[1]:
        S[0] += A[L[0]]
        S[1] -= A[L[0]]
        L[0] += 1
    else:
        if L[0] + 1 < L[1]:
            S[0] += A[L[0]]
            S[1] -= A[L[0]]
            L[0] += 1
        elif L[1] + 1 < L[2]:
            S[0] += A[L[0]]
            S[1] += A[L[1]] - A[L[0]]
            S[2] -= A[L[1]]
            L[0] += 1
            L[1] += 1
        elif L[2] < N-1:
            S[0] += A[L[0]]
            S[1] += A[L[1]] - A[L[0]]
            S[2] += A[L[2]] - A[L[1]]
            S[3] -= A[L[2]]
            L[0] += 1
            L[1] += 1
            L[2] += 1
        else:
            break
    ans = min(ans, max(S)-min(S))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
INF = 10**18

S = sum(A)

def dfs(ind, part, remain, prob):
    if part == 1:
        prob.append(remain)
        return max(prob)-min(prob)
    s = 0
    while s*part < remain and ind <= N-part:
        s += A[ind]
        ind += 1
    if s > A[ind-1]:
        a1 = dfs(ind-1, part-1, remain-s+A[ind-1], prob+[s-A[ind-1]])
    else:
        a1 = INF
    a2 = dfs(ind, part-1, remain-s, prob+[s])
    return min(a1, a2)

ans = dfs(0, 4, S, [])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
INF = 10**18

S = sum(A)

def dfs(ind, part, remain, prob):
    if part == 1:
        if remain == 0: return INF
        prob.append(remain)
        return max(prob)-min(prob)
    s = 0
    while s*part < remain and ind <= N-part:
        s += A[ind]
        ind += 1
    if s > A[ind-1]:
        a1 = dfs(ind-1, part-1, remain-s+A[ind-1], prob+[s-A[ind-1]])
    else:
        a1 = INF
    a2 = dfs(ind, part-1, remain-s, prob+[s])
    return min(a1, a2)

ans = dfs(0, 4, S, [])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
INF = 10**14

S = sum(A)

def dfs(ind, part, remain, prob):
    if part == 1:
        if remain == 0: return INF
        prob.append(remain)
        return max(prob)-min(prob)
    s = 0
    while s*part < remain and ind <= N-part:
        s += A[ind]
        ind += 1
    if s > A[ind-1]:
        a1 = dfs(ind-1, part-1, remain-s+A[ind-1], prob+[s-A[ind-1]])
    else:
        a1 = INF
    a2 = dfs(ind, part-1, remain-s, prob+[s])
    return min(a1, a2)

ans = dfs(0, 4, S, [])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
N = I()
A = LI()
ans = inf

sumI = [0] * N
sumI[0] = A[0]
for i in range(1,N):
    sumI[i] += sumI[i-1] + A[i]
#print(sumI)
sumPQ = int(0)
sumRS = int(0)

s = N//2
ibottom = int(0)
itop    = N-1
while True:
#    print("loop")
    Pcandi = [0]*2
    Qcandi = [0]*2
    Rcandi = [0]*2
    Scandi = [0]*2

    sumPQ = sumI[s]
    sumRS = sumI[N-1] - sumPQ
#    print(sumPQ,sumRS)
    k = int(0)
    while (k<s and sumPQ>(sumI[k]*2)):
        k +=1
    Pcandi[0] = sumI[k]
    Qcandi[0] = sumPQ - Pcandi[0]
    if k<=s:
        Pcandi[1] = sumI[k-1]
        Qcandi[1] = sumPQ - Pcandi[1]

    k = s+1
    while k<N and sumRS>(sumI[k]-sumPQ)*2:
        k +=1

    Rcandi[0] = sumI[k-1] - sumPQ
    Scandi[0] = sumRS - Rcandi[0]
    if k<N:
        Rcandi[1] = sumI[k] - sumPQ
        Scandi[1] = sumRS - Rcandi[1]

    anscandi = []
    for i1 in range(2):
        for i2 in range(2):
            a = max(Pcandi[i1],Qcandi[i1],Rcandi[i2],Scandi[i2]) \
                - min(Pcandi[i1],Qcandi[i1],Rcandi[i2],Scandi[i2])
            anscandi.append(a)

    if ans >= min(anscandi):
        ans = min(anscandi)
    else:
        break

    if sumPQ<sumRS:
        ibottom = s
        s = (itop + ibottom)//2
    else:
        itop = s
        s = (itop + ibottom) // 2


#print(Pcandi,Qcandi,Rcandi,Scandi)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
N = I()
A = LI()
ans = inf

sumI = [0] * N
sumI[0] = A[0]
for i in range(1,N):
    sumI[i] += sumI[i-1] + A[i]
#print(sumI)
sumPQ = int(0)
sumRS = int(0)

s = N//2
ibottom = int(0)
itop    = N-1
while True:
#    print("loop")
    Pcandi = [0]*2
    Qcandi = [0]*2
    Rcandi = [0]*2
    Scandi = [0]*2

    sumPQ = sumI[s]
    sumRS = sumI[N-1] - sumPQ
#    print(sumPQ,sumRS)
    k = int(0)
    while (k<s and sumPQ>(sumI[k]*2)):
        k +=1
    Pcandi[0] = sumI[k]
    Qcandi[0] = sumPQ - Pcandi[0]
    if k<=s:
        Pcandi[1] = sumI[k-1]
        Qcandi[1] = sumPQ - Pcandi[1]

    k = s+1
    while k<N and sumRS>(sumI[k]-sumPQ)*2:
        k +=1

    Rcandi[0] = sumI[k-1] - sumPQ
    Scandi[0] = sumRS - Rcandi[0]
    if k<N:
        Rcandi[1] = sumI[k] - sumPQ
        Scandi[1] = sumRS - Rcandi[1]

    anscandi = []
    for i1 in range(2):
        for i2 in range(2):
            a = max(Pcandi[i1],Qcandi[i1],Rcandi[i2],Scandi[i2]) \
                - min(Pcandi[i1],Qcandi[i1],Rcandi[i2],Scandi[i2])
            anscandi.append(a)

    if ans > min(anscandi):
        ans = min(anscandi)
    else:
        break

    if sumPQ<sumRS:
        ibottom = s
        s = (itop + ibottom)//2
    else:
        itop = s
        s = (itop + ibottom) // 2


#print(Pcandi,Qcandi,Rcandi,Scandi)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

Submission status: Wrong Answer

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]
C = []
cnt = 4
cur = 0
for i in range(1,N):
    if cnt>1 and abs(B[i]-B[cur]-(B[-1]-B[cur])//cnt)>abs(B[i-1]-B[cur]-(B[-1]-B[cur])//cnt):
        C.append(B[i-1]-B[cur])
        cur = i-1
        cnt -= 1
C = sorted(C)
print(C[-1]-C[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(str) for str in input().split()]


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

left_ix = 0
right_ix = 2
ans = 10 ** 10

for center_ix in range(1, N):
    while left_ix + 1 < center_ix and abs(sumL2R[center_ix] - 2 * sumL2R[left_ix + 1]) < abs(sumL2R[center_ix] - 2 * sumL2R[left_ix]):
        left_ix += 1

    # abs(sumL2R[N] - sumL2R[center_ix] - 2 * (sumL2R[right_ix] - sumL2R[center_ix]))
    # = abs(sumL2R[N] + sumL2R[center_ix] - 2 * sumL2R[right_ix])
    while right_ix <= center_ix or (right_ix + 1 < N and abs(sumL2R[N] + sumL2R[center_ix] - 2 * sumL2R[right_ix + 1]) < abs(sumL2R[N] + sumL2R[center_ix] - 2 * sumL2R[right_ix])):
        right_ix += 1

    sums = [sumL2R[left_ix], sumL2R[center_ix] - sumL2R[left_ix], sumL2R[right_ix] - sumL2R[center_ix], sumL2R[N] - sumL2R[right_ix]]
    aa = max(sums) - min(sums)

    if aa <= ans:
        ans = aa
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = list(accumulate(LI() + [0]))
ret = INF
for second_point in range(2, n-1):
    left_sum = L[second_point - 1]
    right_sum = L[-1] - left_sum
    if  L[bisect_left(L, left_sum/2)] - left_sum/2 < left_sum/2 - L[bisect_left(L, left_sum/2) - 1]:
        p = L[bisect_left(L, left_sum/2)]
    else:
        p = L[bisect_left(L, left_sum/2) - 1]
    q = left_sum - p
    if L[bisect_left(L, left_sum + right_sum/2)] - right_sum/2 - left_sum < left_sum + right_sum/2 - L[bisect_left(L, left_sum + right_sum/2) - 1]:
        s = L[-1] - L[bisect_left(L, left_sum + right_sum/2)]
    else:
        s = L[-1] - L[bisect_left(L, left_sum + right_sum/2) - 1]
    r = right_sum - s
    ret = min(ret, max(p, q, r, s) - min(p, q, r, s))


print(ret)

Submission status: Wrong Answer

Solution code:
from sys import stdin
n = int(stdin.readline().rstrip())
arg = list(map(int, stdin.readline().rstrip().split()))

partsum = []
temp = 0
ave = sum(arg) // 4
for i, val in enumerate(arg):
    if len(partsum) < 4:
        if abs(temp - ave) >= abs((temp + val) - ave):
            temp += val
        else:
            partsum.append(temp)
            temp = val
    else:
        temp += val
        if i == n - 1:
            partsum.append(temp)

if len(partsum) < 4:
    l = len(partsum)
    for i in range(4-l):
        partsum.append(ave)

print(abs(max(partsum) - min(partsum)))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]

for i in range(n-1):
    a[i+1]+=a[i]

j=0
k=2
ans=10**9

for i in range(1,n-1):
    while abs(a[j]*3-a[i])>abs(a[j+1]*3-a[i]):
        j+=1
    while abs(a[k]*3-a[i]-a[n-1])>abs(a[k+1]*3-a[i]-a[n-1]):
        k+=1
    t=[a[j],a[i]-a[j],a[k]-a[i],a[n-1]-a[k]]
    ans=min(ans,max(t)-min(t))
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=[sum(a[:i])+a[i] for i in range(len(a))]
j=0
k=2
ans=10**9

for i in range(1,n-1):
    while abs(a[j]*3-a[i])>abs(a[j+1]*3-a[i]):
        j+=1
    while abs(a[k]*3-a[i]-a[n-1])>abs(a[k+1]*3-a[i]-a[n-1]):
        k+=1
    t=[a[j],a[i]-a[j],a[k]-a[i],a[n-1]-a[k]]
    ans=min(ans,max(t)-min(t))
print(ans)

Submission status: Wrong Answer

Solution code:
"""n=int(input())
box=list(map(int,input().split()))
point=0
ans=[]
accumulate=[sum(box[:i])+box[i] for i in range(len(box))]
accumulate.insert(0,0)
print(accumulate)"""
n=int(input())
a=list(map(int,input().split()))
a=[sum(a[:i])+a[i] for i in range(len(a))]
j=0
k=2
ans=10**9

for i in range(1,n-1):
    while abs(a[j]*3-a[i])>abs(a[j+1]*3-a[i]):
        j+=1
    while abs(a[k]*3-a[i]-a[n-1])>abs(a[k+1]*3-a[i]-a[n-1]):
        k+=1
    t=[a[j],a[i]-a[j],a[k]-a[i],a[n-1]-a[k]]
    ans=min(ans,max(t)-min(t))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def calc(n):
    s = sum(map(int, str(n)))
    return n / s

def main():
    k = ri()
    cand = list(range(1, 10))
    last = 9
    for n in range(1, 15):
        pow10n = pow(10, n)
        for d in range(1, 10):
            lim = (d+1)*pow10n
            e = 0
            while True:
                e1 = d*pow10n+e*(last+1)+last
                if e1 >= lim:
                    break
                e2 = e1 + (last+1)
                if calc(e1) > calc(e2):
                    last = last*10+9
                    e = 0
                    continue
                cand.append(e1)
                e += 1
    print("\n".join(map(str, cand[:k])))


if __name__ == '__main__':
    main()

"""
1 1.0
2 1.0
3 1.0
4 1.0
5 1.0
6 1.0
7 1.0
8 1.0
9 1.0
19 1.9
29 2.6363636363636362
39 3.25
49 3.769230769230769
59 4.214285714285714
69 4.6
79 4.9375
89 5.235294117647059
99 5.5
199 10.473684210526315
299 14.95
399 19.0
499 22.681818181818183
599 26.043478260869566
699 29.125
799 31.96
899 34.57692307692308
999 37.0
1099 57.8421052631579
1199 59.95
1299 61.857142857142854
1399 63.59090909090909
1499 65.17391304347827
1599 66.625
1699 67.96
1799 69.1923076923077
1899 70.33333333333333
1999 71.39285714285714
2999 103.41379310344827
3999 133.3
4999 161.25806451612902
5999 187.46875
6999 212.0909090909091
7999 235.26470588235293
8999 257.1142857142857
9999 277.75
10999 392.82142857142856
11999 413.7586206896552
12999 433.3
13999 451.5806451612903
14999 468.71875
15999 484.8181818181818
16999 499.97058823529414
17999 514.2571428571429
18999 527.75
19999 540.5135135135135
20999 724.1034482758621
21999 733.3
22999 741.9032258064516
23999 749.96875
24999 757.5454545454545
25999 764.6764705882352
26999 771.4
27999 777.75
28999 783.7567567567568
29999 789.4473684210526
39999 1025.6153846153845
49999 1249.975
59999 1463.3902439024391
69999 1666.642857142857
79999 1860.4418604651162
89999 2045.4318181818182
99999 2222.2
109999 2972.945945945946
119999 3157.8684210526317
129999 3333.3076923076924
139999 3499.975
149999 3658.512195121951
159999 3809.5
169999 3953.4651162790697
179999 4090.8863636363635
189999 4222.2
199999 4347.804347826087
209999 5526.289473684211
219999 5641.0
229999 5749.975
239999 5853.634146341464
249999 5952.357142857143
259999 6046.488372093023
269999 6136.340909090909
279999 6222.2
289999 6304.326086956522
299999 6382.95744680851
309999 7948.692307692308
319999 7999.975
329999 8048.756097560976
339999 8095.214285714285
349999 8139.511627906977
359999 8181.795454545455
369999 8222.2
379999 8260.847826086956
389999 8297.851063829787
399999 8333.3125
499999 10204.061224489797
599999 11999.98
699999 13725.470588235294
799999 15384.596153846154
899999 16981.11320754717
999999 18518.5
"""

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
for i in range(1, N):
    A[i] += A[i - 1]

def calc(lst, min_num):
    total = lst[-1] - min_num
    # print (total)
    lb = -1
    ub = len(lst)
    while (ub - lb) > 1:
        mid = (lb + ub)//2
        if lst[mid] - min_num > total/2:
            ub = mid
        else:
            lb = mid
    # print ('ub', ub)
    a1, b1 = lst[ub] - min_num, lst[-1] - lst[ub]
    diff1 = abs(b1 - a1)
    # print ('diff1', diff1)
    a2, b2 = lst[ub - 1] - min_num, lst[-1] - lst[ub - 1]
    diff2 = abs(b2 - a2)
    # print ('diff2', diff2)
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1

# print (calc(A, 0))

ans = 10 ** 9
for half in range(2, N -2):
    # print (A[:half], end = ' ')
    # print (A[half:])
    P, Q = calc(A[:half], 0)
    R, S = calc(A[half:], A[half - 1])
    # print (P, Q, R, S)
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    # print (tmp)
    ans = min(tmp, ans)

# print ('ans', ans)
print (ans)

Submission status: Wrong Answer

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 index < N and A[index] - A[prev_index] < stan:
                index += 1
            PQRS[j] = A[index] - A[prev_index]
            prev_index = index
            # print (1, end = '')
        else: #基準以下にするとき
            while index < N + 1 and A[index] - A[prev_index] < stan:
                index += 1
                if index == N + 1:
                    break
            PQRS[j] = A[index - 1] - A[prev_index]
            index -= 1
            prev_index = index
            # 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)