Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
N = int(input())
A = list(map(int,input().split()))
Asum = [0]
for i in range(N):
  Asum.append(Asum[i] + A[i])
Diff = Asum[N]
m = 0; n = 2
for i in range(N-3):
  flag = True
  P = Asum[m]; Q = Asum[i+2] - Asum[m]
  while flag:
    m += 1
    if abs(Asum[i+2]-Asum[m]*2) < abs(P-Q):
      P = Asum[m]; Q = Asum[i+2] - Asum[m]
    else:
      flag = False
      m -= 1
  flag = True
  R = Asum[n] - Asum[i+2]; S = Asum[N] - Asum[n]
  while flag:
    n += 1
    if abs(Asum[N]-Asum[n]*2+Asum[i+2]) < abs(R-S):
      R = Asum[n] - Asum[i+2]; S = Asum[N] - Asum[n]
    else:
      flag = False
      n -= 1
  if max(P,Q,R,S)-min(P,Q,R,S) < Diff:
    Diff = max(P,Q,R,S)-min(P,Q,R,S)
print(Diff)

# Example run
# Input:
0
805965556
# Output:
0
N = int(input())
A = list(map(int, input().split()))
ans = pow(10,10)
for i in range(1, N - 3):
	for j in range(i + 1, N - 2):
		for k in range(j + 1, N):
			B = list(A[:i])
			C = list(A[i:j])
			D = list(A[j:k])
			E = list(A[k:])
			P = sum(B)
			Q = sum(C)
			R = sum(D)
			S = sum(E)
			ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
print(ans)


# Example run
# Input:
-47
4517
# Output:
10000000000
N = int(input())
A = list(map(int,input().split()))

S = [0]
for i,a in enumerate(A,1):
    S.append(S[i-1]+a)
Sn = S[-1]
ans = Sn

for j in range(2,N-1):
    tmpS = S[j]
    for i in range(1,j):
        if S[i] > tmpS/2:
            break
    i -= (tmpS - S[i] - S[i]) > (tmpS - S[i-1] - S[i-1])
    for k in range(j+1,N):
        if S[k]-tmpS > (Sn-tmpS)/2:
            break
    k -= (Sn-S[k] - S[k] + tmpS) > (Sn - S[k-1] - S[k-1] + tmpS)
    P = (S[i],S[j]-S[i],S[k]-S[j],S[-1]-S[k])
    ans = min(ans,max(P)-min(P))
print(ans)

# Example run
# Input:
-131787924
-1
# Output:
-1
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)


# Example run
# Input:
0
34135163
# Output:
0
N = int(input())
A = list(map(int, input().split()))

min_score = float('inf')
for i in range(1, N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            l = [sum(A[:i]), sum(A[i:j]), sum(A[j:k]), sum(A[k:])]
            score = max(l) - min(l)
            if score < min_score:
                min_score = score

print(min_score)

# Example run
# Input:
-208
506
# Output:
inf
n = int(input())
a_list = [int(x) for x in input().split()]

temp_list = [0] * (n + 1)
for i in range(1, n + 1):
    temp_list[i] = a_list[i - 1] + temp_list[i - 1]
 
l = 1
r = 3
ans = temp_list[-1]
for m in range(2, n - 1):
    gap_min = abs((temp_list[m] - temp_list[l]) - (temp_list[l] - temp_list[0]))
    while l < m:
        l += 1
        gap = abs((temp_list[m] - temp_list[l]) - (temp_list[l] - temp_list[0]))
        if gap < gap_min:
            gap_min = gap
        else:
            l -= 1
            break
    else:
        l -= 1
    
    gap_min = abs((temp_list[n] - temp_list[r]) - (temp_list[r] - temp_list[m]))
    while r < n:
        r += 1
        gap = abs((temp_list[n] - temp_list[r]) - (temp_list[r] - temp_list[m]))
        if gap < gap_min:
            gap_min = gap
        else:
            r -= 1
            break
    else:
        r -= 1
    
    num_list = sorted([temp_list[l] - temp_list[0], temp_list[m] - temp_list[l], temp_list[r] - temp_list[m], temp_list[n] - temp_list[r]])
    ans_temp = num_list[3] - num_list[0]
    if ans_temp < ans:
        ans = ans_temp
print(ans)

# Example run
# Input:
0
10
# Output:
0
def sum(ar,st,en):
    s=0
    for i in range(st,en+1):
        s+=ar[i]
    return s
max_value=999999999999999999999

def k_part(k,n,ar):
    res=max_value
    for o in range(n):
        l_min=0
        for r_min in range(l_min,n):
            min_s=sum(ar,l_min,r_min)
            dp=[[max_value for i in range(n)] for j in range(k)]
            dp[0][r_min-l_min]=min_s
            for p in range(1,k):
                for l_max in range(r_min,n):
                    for r_max in range(l_max,n):
                        max_s=sum(ar,l_max+1,r_max)
                        if max_s>=min_s:
                            dp[p][r_max]=min(dp[p][r_max],max(max_s,dp[p-1][l_max]))
            if dp[k-1][n-1]==max_value:
                continue
            res=min(res,dp[k-1][n-1]-min_s)
        tmp=[0]*n
        for i in range(n):
            tmp[(i-1+n)%n]=ar[i]
        for i in range(n):
            ar[i]=tmp[i]
    return res

k=4
n=int(input())
deps=[int(i) for i in input().strip().split(" ")]
print(k_part(k,n,deps))

# Example run
# Input:
-51
0
# Output:
999999999999999999999
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)


# Example run
# Input:
1
548754427
# Output:
548754427
N=int(input())
A=[int(i) for i in input().split()]
S=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=S[i]+A[i]
B=A[::-1]
T=[0 for i in range(N+1)]
for i in range(N):
    T[i+1]=T[i]+B[i]
F=[0 for i in range(N)]
G=[0 for i in range(N)]
for i in range(N):
    LS=S[i+1]
    k=0
    if i!=0:
        k=F[i-1]
    if k!=0:
        k-=1
    tmp=LS
    for j in range(k,i+1):
        L=S[j]
        R=LS-S[j]
        if abs(R-L)<=tmp:
            F[i]=j
        else:
            break
        tmp=abs(R-L)
    if F[i]<=0:
        F[i]=0
for i in range(N):
    RS=T[i+1]
    k=0
    if i!=0:
        k=G[i-1]
    if k!=0:
        k-=1
    tmp=LS
    for j in range(k,i+1):
        L=T[j]
        R=RS-T[j]
        if abs(R-L)<=tmp:
            G[i]=j
        else:
            break
        tmp=abs(R-L)
    if G[i]<=0:
        G[i]=0
ans=S[N]
for i in range(N):
    A=[0 for i in range(4)]
    k=0
    if i!=0:
        k=F[i-1]
    A[0]=S[k]
    A[1]=S[i]-S[k]
    A[2]=T[N-i]-T[G[N-i-1]]
    A[3]=T[G[N-i-1]]
    score=max(A)-min(A)
    if ans>score:
        ans=score
print(ans)


# Example run
# Input:
0
16
# Output:
0
N = int(input())
H = [int(i) for i in input().split()]
S = [0 for i in range(N)]
S[0] = H[0]
for i in range(1,N):
    S[i] = H[i] + S[i-1]
left = 0
right = 2
D = S[N-1]
for center in range(1,N-2):
    while  abs(S[center]/2-S[left+1]) <= abs(S[center]/2-S[left]) :
        if left+1 == center:
            break
        else:
            left += 1
    if center == right:
        right += 1
    while  abs(S[N-1]+S[center]-2*S[right+1]) <= abs(S[N-1]+S[center]-2*S[right]) :
        if right == N-2:
            break
        else:
            right += 1 
    D = min(
            max(S[left],S[center]-S[left],S[right]-S[center],S[N-1]-S[right])-
            min(S[left],S[center]-S[left],S[right]-S[center],S[N-1]-S[right])
            ,D)
print(D)

# Example run
# Input:
1
21507
# Output:
21507
l = int(input())
edge = []
for i in range(1, 19):
    edge.append((i, i + 1, 1 << (i - 1)))
    edge.append((i, i + 1, 0))
sm = 0
for i in range(19, 0, -1):
    v = 1 << (i - 1)
    while l >= v:
        edge.append((i, 20, sm))
        sm += v
        l -= v
print(20, len(edge))
for x, y, z in edge:
    print(x, y, z)

# Example run
# Input:
-16371
# Output:
20 36
1 2 1
1 2 0
2 3 2
2 3 0
3 4 4
3 4 0
4 5 8
4 5 0
5 6 16
5 6 0
6 7 32
6 7 0
7 8 64
7 8 0
8 9 128
8 9 0
9 10 256
9 10 0
10 11 512
10 11 0
11 12 1024
11 12 0
12 13 2048
12 13 0
13 14 4096
13 14 0
14 15 8192
14 15 0
15 16 16384
15 16 0
16 17 32768
16 17 0
17 18 65536
17 18 0
18 19 131072
18 19 0