Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import deque
N = int(input())

alphabet = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]
unvisited = deque(alphabet[0 : N])
visited = deque()
st = deque([["a", visited, unvisited]]) # stack

while len(st) > 0:
    str, visited, unvisited = st.popleft()

    if str[-1] not in visited:
        visited.append(str[-1])
        unvisited.popleft()

    if len(str) == N:
        print(str)
    else:
        # すでに使った文字を使う
        for x in visited:
            st.append([str + x, visited.copy(), unvisited.copy()])
        # まだ使っていない文字を使う
        if len(unvisited) > 0:
            x = unvisited[0]
            st.append([str + x, visited.copy(), unvisited.copy()])


Fixed submission:
from collections import deque
N = int(input())

alphabet = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]
unvisited = deque(alphabet[0 : N])
visited = deque()
st = deque([["a", visited, unvisited]]) # stack

while len(st) > 0:
    str, visited, unvisited = st.popleft()

    if str[-1] not in visited:
        visited.append(str[-1])
        unvisited.popleft()

    if len(str) == N:
        print(str)
    else:
        # すでに使った文字を使う
        for x in visited:
            st.append([str + x, deque(visited), deque(unvisited)])
        # まだ使っていない文字を使う
        if len(unvisited) > 0:
            x = unvisited[0]
            st.append([str + x, deque(visited), deque(unvisited)])
Buggy python submission (verdict: Runtime Error):
import math
N = int(input())

n = N
ans = 0
n_dig = math.floor(math.log10(N)) + 1 # Nの桁数
mai = [0] * n_dig # 枚数

for i in range(n_dig):
    d = n % 10
    n //= 10
    if d < 1 + 10 - d:
        mai[i] = d
    else:
        mai[i] = d - 10 # おつり
        mai[i+1] = 1

    ans += min(d, 1 + 10 - d)
    if n == 0: break

print(sum([abs(m) for m in mai]))

Fixed submission:
n = "0" + input()

ans = 0
n_dig = len(n) # Nの桁数

carry = 0
d_next = int(n[n_dig - 1])

for i in range(n_dig - 1, 0, -1):  # n[0]はダミーなのでn[1]で止める
    d = d_next
    d_next = int(n[i - 1])

    if carry + d <= 4 or (carry + d == 5 and d_next <= 4):
        ans += d + carry
        carry = 0  # 繰り上がり
    else:
        ans += 10 - d - carry
        carry = 1

print(ans + carry)
Buggy python submission (verdict: Time Limit Exceeded):
# 20/4/20 Youtube解説の方法
n = int(input())
s = input()

ans = 0
for i in range(1000):
    t = list(str(i).zfill(3))
    ti = 0
    for j in range(n):
        if s[j] == t[ti]:
            ti += 1
            if ti == 3: break
    else:
        continue
    ans += 1

print(ans)

Fixed submission:
N = int(input())
S = input()

pin1 = {}
pin12 = {}
pin123 = {}

for i in range(N):
    if S[i] not in pin1:
        pin1[S[i]] = 1
        for j in range(i + 1, N):
            if S[i] + S[j] not in pin12:
                pin12[S[i] + S[j]] = 1
                for k in range(j + 1, N):
                    if S[i] + S[j] + S[k] not in pin123:
                        pin123[S[i] + S[j] + S[k]] = 1

print(len(pin123))
Buggy python submission (verdict: Time Limit Exceeded):
def binomial(n, k):
    num = 1
    for i in range(1, min(k, n - k) + 1):
        num = ((num * n) // i) 
        n -= 1
    return num % (10**9 + 7)

x, y = [int(a) for a in input().split()]

n, rn = divmod(2 * x - y, 3)
m, rm = divmod(2 * y - x, 3)

if rn != 0 or rm != 0 or n < 0 or m < 0:
    ans = 0
else:
    a = (2 * x - y) // 3
    b = (2 * y - x) // 3
    ans = binomial(a + b, b)

print(ans)

Fixed submission:
def binomial_p(n, k, p):
    '''
    Input: integers n, k such that n >= k >= 0, prime number p
    Output: n choose k mod p
    '''

    k = min(k, n-k)
    fct_n = 1  # factorial of n mod p = 1 * 2 * ... * n mod p
    inv = [0, 1] # inv[i] : inverse of i mod p
    invfct_k = 1 # factorial of inverse of k mod p = 1^(-1) * 2^(-1) * ... * k^(-1) mod p
    invfct_n_k = 1  # factorial of inverse of (n-k) mod p

    # Calculate inverse, factorial, factorial of inverse of i
    # all at the same time
    for i in range(2, n - k + 1):
        fct_n = (fct_n * i) % p
        inv.append(( inv[p % i] * (p - p//i) ) % p )
        invfct_n_k = invfct_n_k * inv[-1] % p
        if i == k:
            invfct_k = invfct_n_k

    for i in range(n - k + 1, n + 1):
        fct_n = (fct_n * i) % p

    return ((fct_n * invfct_k % p) * invfct_n_k) % p



x, y = [int(a) for a in input().split()]

n, rn = divmod(2 * x - y, 3)
m, rm = divmod(2 * y - x, 3)
p = 10**9 + 7

if rn != 0 or rm != 0 or n < 0 or m < 0:
    ans = 0
else:
    a = (2 * x - y) // 3
    b = (2 * y - x) // 3
    ans = binomial_p(a + b, b, p)

print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np

N = int(input())
D = np.array([int(a) for a in input().split()])

num_at_dist = np.array([1] + [0] * (N-1) + [0]) # extra 0 at the end for index -1

if D[0] != 0:
    ans = 0
else:
    ans = 1
    D = np.sort(D)
    for i in range(1, N):
        dist = D[i]
        num_at_dist[dist] += 1
        ans *= num_at_dist[dist - 1]

print(ans % 998244353)

Fixed submission:
import numpy as np

N = int(input())
D = np.array([int(a) for a in input().split()])

num_at_dist = np.array([1] + [0] * (N-1) + [0]) # extra 0 at the end for index -1

if D[0] != 0:
    ans = 0
else:
    ans = 1
    D = np.sort(D)
    for i in range(1, N):
        dist = D[i]
        num_at_dist[dist] += 1
        ans = ( ans * num_at_dist[dist - 1] ) % 998244353

print(ans % 998244353)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
D = [int(a) for a in input().split()]

num_at_dist = [1] + [0] * (N-1) + [0] # extra 0 at the end for index -1

if D[0] != 0:
    ans = 0
else:
    ans = 1
    D.sort()
    for i in range(1, N):
        dist = D[i]
        num_at_dist[dist] += 1
        ans *= num_at_dist[dist - 1]

print(ans % 998244353)

Fixed submission:
import numpy as np

N = int(input())
D = np.array([int(a) for a in input().split()])

num_at_dist = np.array([1] + [0] * (N-1) + [0]) # extra 0 at the end for index -1

if D[0] != 0:
    ans = 0
else:
    ans = 1
    D = np.sort(D)
    for i in range(1, N):
        dist = D[i]
        num_at_dist[dist] += 1
        ans = ( ans * num_at_dist[dist - 1] ) % 998244353

print(ans % 998244353)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
D = [int(a) for a in input().split()]

num_at_dist = [1] + [0] * (N-1) + [0] # extra 0 at the end for index -1

if D[0] != 0:
    ans = 0
else:
    ans = 1
    D.sort()
    for i in range(1, N):
        dist = D[i]
        num_at_dist[dist] += 1
        ans *= num_at_dist[dist - 1]

print(ans % 998244353)


Fixed submission:
import numpy as np

N = int(input())
D = np.array([int(a) for a in input().split()])

num_at_dist = np.array([1] + [0] * (N-1) + [0]) # extra 0 at the end for index -1

if D[0] != 0:
    ans = 0
else:
    ans = 1
    D = np.sort(D)
    for i in range(1, N):
        dist = D[i]
        num_at_dist[dist] += 1
        ans = ( ans * num_at_dist[dist - 1] ) % 998244353

print(ans % 998244353)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N = int(input())
L = [int(a) for a in input().split()]

L.sort()

num_triangles = 0
for i in range(0, N - 2): # 0, 1, ..., N - 3
    for j in range(i + 1, N - 1): # i+1, i+2, ..., N-2
        num_triangles += bisect.bisect_left(L[j + 1:N], L[i] + L[j])

print(num_triangles)


Fixed submission:
import bisect

N = int(input())
L = [int(a) for a in input().split()]

L.sort()

num_triangles = 0
for i in range(0, N - 2): # 0, 1, ..., N - 3
    for j in range(i + 1, N - 1): # i+1, i+2, ..., N-2
        num_triangles += bisect.bisect_left(L[j + 1:N], L[i] + L[j])

print(num_triangles)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = [int(a) for a in input().split()]

L.sort()

num_triangles = 0
for i in range(0, N - 2): # 0, 1, ..., N - 3
    for j in range(i + 1, N - 1): # i+1, i+2, ..., N-2
        for k in range(j + 1, N):
            if L[i] + L[j] <= L[k]:
                break
            else:
                num_triangles += 1

print(num_triangles)


Fixed submission:
import bisect

N = int(input())
L = [int(a) for a in input().split()]

L.sort()

num_triangles = 0
for i in range(0, N - 2): # 0, 1, ..., N - 3
    for j in range(i + 1, N - 1): # i+1, i+2, ..., N-2
        num_triangles += bisect.bisect_left(L[j + 1:N], L[i] + L[j])

print(num_triangles)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools

N = int(input())
L = [int(a) for a in input().split()]

comb_sides = list(itertools.combinations(L, 3))

num_triangles = 0
for sides in comb_sides:
    if sides[0] + sides[1] > sides[2] and sides[1] + sides[2] > sides[0] and sides[2] + sides[0] > sides[1]:
        num_triangles += 1

print(num_triangles)


Fixed submission:
import bisect

N = int(input())
L = [int(a) for a in input().split()]

L.sort()

num_triangles = 0
for i in range(0, N - 2): # 0, 1, ..., N - 3
    for j in range(i + 1, N - 1): # i+1, i+2, ..., N-2
        num_triangles += bisect.bisect_left(L[j + 1:N], L[i] + L[j])

print(num_triangles)
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = [None] * N

for i in range(0, N):
    S[i] = [int(s) for s in list(input())]

m = 0
n_partite = True

for n in range(0, N):  # try starting with every vertex
    levels = [None] * N
    levels[n] = 0

    for l in range(0, N): # max possible levels
        for i in range(0, N): # look at every vertex
            if levels[i] == l: # vertex i is at level l
                # scan column S[i]
                for j in range(0, N): # scan all vertices and look for adjacent vertex to i
                    if S[i][j] == 1: # vertex j is adjacent to i
                        if levels[j] == None:
                            levels[j] = l + 1
                        elif levels[j] == l - 1: continue
                        elif levels[j] == l + 1: continue
                        else:
                            n_partite = False
                            break
    m = max( max(levels), m)

if n_partite:
    print(m + 1)
else:
    print(-1)


Fixed submission:
N = int(input())
S = [None] * N

for i in range(0, N):
    S[i] = [int(s) for s in list(input())]


def local_max_level(S, N, n): # n is the starting vertex
    levels = [None] * N
    levels[n] = 0

    for l in range(0, N): # for each level l
        for i in range(0, N): # look at every vertex i
            if levels[i] == l: # which is at level l
                # scan column S[i]
                for j in range(0, N): # scan all vertices and look for adjacent vertex to i
                    if S[i][j] == 1: # vertex j is adjacent to i
                        if levels[j] == None:
                            levels[j] = l + 1

                        elif levels[j] == l - 1: continue
                        elif levels[j] == l + 1: continue
                        else:
                            return -1
    return max(levels)

def n_partite(S, N):

    M = 0
    for n in range(0, N):  # try starting with every vertex
        m = local_max_level(S, N, n)
        if m == -1: # not n-partite
            return -1
        else:
            M = max(M, m)
    return M + 1

print(n_partite(S, N))
Buggy python submission (verdict: Runtime Error):
N, K, Q = input().strip().split()
N, K, Q = [int(N), int(K), int(Q)]
A = [0] * (Q+1)  # index調整のため、長さQ+1のリストとする
for i in range(1, Q+1):
    A[i] = int(input())

# まず、全員が毎回負けた場合の点数は
points = [K - Q] * (N+1)

for i in range(1, Q+1) # 各ラウンドについて勝者に+1ポイント与える
    points[A[i]] += 1

for i in range(1, N+1):
    print('Yes' if points[i] > 0 else 'No')

Fixed submission:
N, K, Q = input().strip().split()
N, K, Q = [int(N), int(K), int(Q)]
A = [0] * (Q+1)  # index調整のため、長さQ+1のリストとする
for i in range(1, Q+1):
    A[i] = int(input())

# まず、全員が毎回負けた場合の点数は
points = [K - Q] * (N+1)

for i in range(1, Q+1): # 各ラウンドについて勝者に+1ポイント与える
    points[A[i]] += 1

for i in range(1, N+1):
    print('Yes' if points[i] > 0 else 'No')
Buggy python submission (verdict: Runtime Error):
# 入力を受け取る
B_MAX = 100000
N = int(input().strip())
B = input().strip().split()

# B_MAX + 1を入れておくことで 必ずmin(B[0], B[1]) = B[1], min(B[N-1], B[N]) = B[N-1]となる
B = [B_MAX + 1] + [int(b) for b in B] + [B_MAX + 1] # 整数に変換


for i in range(1, N + 1): # i = 1, 2, ..., N
    sum += min(B[i-1], B[i]) # A[i] <= min(B[i-1], B[i])

print(sum)

Fixed submission:
# 入力を受け取る
B_MAX = 100000
N = int(input().strip())
B = input().strip().split()

# B_MAX + 1を入れておくことで 必ずmin(B[0], B[1]) = B[1], min(B[N-1], B[N]) = B[N-1]となる
B = [B_MAX + 1] + [int(b) for b in B] + [B_MAX + 1] # 整数に変換

sum = 0
for i in range(1, N + 1): # i = 1, 2, ..., N
    sum += min(B[i-1], B[i]) # A[i] <= min(B[i-1], B[i])

print(sum)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

N, M = [int(x) for x in input().split()]
# 各要素がintで、indexが1からの場合
A = [None] * (N + 1)
B = [0] * (N + 1)
for i in range(1, N + 1):
    A[i], B[i] = [int(x) for x in input().split()]


total = sum(B)

S = [[] for i in range(M + 1)]  # S[j]はj日目までに実施しなければならないアルバイトの報酬のmin heap
for i in range(1, N + 1): # for each job i  --- O(Nlog(N))
    if A[i] > M:
        total -= B[i]
    else:
        heapq.heappush(S[M - A[i]], B[i]) # O(log(N))


for j in range(0, M): # for each day j = 0, 1, ..., M - 1
    while len(S[j]) > j + 1: # O(N)
        minus = heapq.heappop(S[j]) # O(logN)
        total -= minus
    for k in range(0, len(S[j])):
        s = heapq.heappop(S[j])
        heapq.heappush(S[j + 1], s)

print(total)


Fixed submission:
import heapq

######## Wrapper for Max Heap ############
class MaxHeap:
    def __init__(self, H = []):
        self.heapify(H)

    def heapify(self, H):
        self._neg_heap = [ -a for a in H ] # マイナスをかける
        heapq.heapify( self._neg_heap )

    def push(self, value):
        heapq.heappush(self._neg_heap, -value)

    def pop(self):
        return (-1) * heapq.heappop(self._neg_heap)

    def __len__(self):
        return len(self._neg_heap)

# 入力を取得
N, M = [int(x) for x in input().split()]
AB = [None] * N  # AB[i] = [報酬までの日数, 報酬]
for i in range(N):
    AB[i] = [int(x) for x in input().split()]

AB.sort(key = lambda x: x[0]) # 報酬までの日数でソート

heap = MaxHeap() # 報酬額のMax heap
total = 0
j = 0  # 仕事を指すindex

for i in range(1, M + 1):
    while j < N and (AB[j][0]) <= i:  # i日後までに報酬が得られる仕事について
        heap.push(AB[j][1]) # 報酬額をpush
        j += 1
    if len(heap) > 0:
        total += heap.pop() # 最高額をpop

print(total)
Buggy python submission (verdict: Runtime Error):
from enum import Enum

N = int(input())
H = [int(h) for h in input().split()]

# 状態
class State(Enum):
    INCREASING = 1
    DECREASED_BY_1 = 2
    FAIL = -1

state = State.INCREASING

for i in range(1, N): # i = 1, 2, ..., N - 1
    if state == State.INCREASING:
        if H[i] == H[i - 1] - 1: # 1減少
            state = State.DECREASED_BY_1
        elif H[i] <= H[i - 1] - 2: # 2以上減少
            state = State.FAIL
    elif state == State.DECREASED_BY_1:
        if H[i] > H[i - 1]: # 増加
            state = State.INCREASING
        elif H[i] < H[i - 1]: # 減少
            state = State.FAIL
    else:
        break

ans = "Yes" if state is not State.FAIL else "No"
print(ans)


Fixed submission:
N = int(input())
H = [int(h) for h in input().split()]

# 状態
INCREASING = 1
DECREASED_BY_1 = 2
FAIL = -1

state = INCREASING

for i in range(1, N): # i = 1, 2, ..., N - 1
    if state == INCREASING:
        if H[i] == H[i - 1] - 1: # 1減少
            state = DECREASED_BY_1
        elif H[i] <= H[i - 1] - 2: # 2以上減少
            state = FAIL
    elif state == DECREASED_BY_1:
        if H[i] > H[i - 1]: # 増加
            state = INCREASING
        elif H[i] < H[i - 1]: # 減少
            state = FAIL
    else:
        break

ans = "Yes" if state is not FAIL else "No"
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math

def find_divisor(num):
    q = math.floor(math.sqrt(num))

    while num % q is not 0:
        q -= 1

    return q

S = int(input())

q = find_divisor(S)

x1, y1 = [0, 0]
x2, y2 = [q, 0]
x3, y3 = [0, S//q]

print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))


Fixed submission:
S = int(input())

x1, y1 = [0, 0]
x2 = 10 ** 9
y2 = 1

if S % 10 ** 9 == 0:
    y3 = S // 10 ** 9
    x3 = 0
else:
    y3 = (S // 10 ** 9) + 1
    x3 = 10 ** 9 - (S % 10 ** 9)

print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))
Buggy python submission (verdict: Time Limit Exceeded):
# YouTube解説の方法（deque使わない）
from bisect import bisect_left
import sys
input = sys.stdin.readline

def bisect_right_reverse(L, target):
    return len(L) - bisect_left(L[::-1], target)

N = int(input())
A = [int(input()) for _ in range(N)]

L = []
for i in range(N):
    k = bisect_right_reverse(L, A[i])
    if k == len(L):
        L.append(A[i])
    else:
        L[k] = A[i]

print(len(L))

Fixed submission:
from collections import deque
from bisect import bisect_left
N = int(input())
A = [int(input()) for _ in range(N)]
que = deque()
for i in range(N):
    k = bisect_left(que, A[i])
    if k == 0:
        que.appendleft(A[i])
    else:
        que[k - 1] = A[i]

print(len(que))

Buggy python submission (verdict: Time Limit Exceeded):
# YouTube解説の方法（deque使わない）
from bisect import bisect_left

def bisect_right_reverse(L, target):
    return len(L) - bisect_left(L[::-1], target)

N = int(input())
A = [int(input()) for _ in range(N)]

L = []
for i in range(N):
    k = bisect_right_reverse(L, A[i])
    if k == len(L):
        L.append(A[i])
    else:
        L[k] = A[i]

print(len(L))

Fixed submission:
from collections import deque
from bisect import bisect_left
N = int(input())
A = [int(input()) for _ in range(N)]
que = deque()
for i in range(N):
    k = bisect_left(que, A[i])
    if k == 0:
        que.appendleft(A[i])
    else:
        que[k - 1] = A[i]

print(len(que))
Buggy python submission (verdict: Runtime Error):
N, M = [int(x) for x in input().split()]
a = [int(input()) for _ in range(M)]
p = 10 ** 9 + 7

fib = [1, 1] + [None] * (N - 1)
for i in range(2, N + 1):
    fib[i] = (fib[i - 1] + fib[i - 2]) % p

for j in range(M):
    if a[j] == N or (j + 1 < M and a[j] + 1 == a[j + 1]):
        ans = 0
        break
        
    if j == 0:
        ans = fib[a[j] - 1]
    else:
        ans *= fib[a[j] - 1 - (a[j - 1] + 1)]
        ans %= p
else:
    ans *= fib[N - a[M - 1] - 1]
    ans %= p

print(ans)


Fixed submission:
N, M = [int(x) for x in input().split()]
a = [int(input()) for _ in range(M)]
p = 10 ** 9 + 7

if M == 0:
    a = [-1]

fib = [1, 1] + [None] * (N - 1)
for i in range(2, N + 1):
    fib[i] = (fib[i - 1] + fib[i - 2]) % p

ans = 1
for j in range(M):
    if a[j] == N or (j + 1 < M and a[j] + 1 == a[j + 1]):
        ans = 0
        break

    if j == 0:
        ans = fib[a[j] - 1]
    else:
        ans *= fib[a[j] - 1 - (a[j - 1] + 1)]
        ans %= p
else:
    ans *= fib[N - a[M - 1] - 1]
    ans %= p

print(ans)
Buggy python submission (verdict: Runtime Error):
def solve(n, x):
    layers = 2 ** (n + 1) - 3  # レベルn-1バーガーの層の数
    patties = 2 ** n - 1    # レベルn-1バーガーのパティの数
    if x == 0:
        ans = 0
    elif x <= layers + 1:
        ans = solve(n - 1, x - 1)
    else:
        ans = patties + 1 + solve(n - 1, x - layers - 2)
        
    return ans

N, X = [int(x) for x in input().split()]
print(solve(N, X))

Fixed submission:
# レベルiバーガーの層数は 2^(i+2) - 3
def layers(i):
    return 2 ** (i + 2) - 3

# レベルiバーガーのパティ数は 2^(i+1) - 1
def patties(i):
    return 2 ** (i + 1) - 1

def solve(n, x):
    layers = 2 ** (n + 1) - 3  # レベルn-1バーガーの層の数
    patties = 2 ** n - 1    # レベルn-1バーガーのパティの数
    if x == 0:
        ans = 0
    elif x < layers + 1:
        ans = solve(n - 1, x - 1)
    elif x == layers + 1:
        ans = patties
    elif x == layers + 2:
        ans = patties + 1
    elif x < 2 * layers + 2:
        ans = patties + 1 + solve(n - 1, x - layers - 2)
    else:
        ans = 2 * patties + 1
    return ans

N, X = [int(x) for x in input().split()]
print(solve(N, X))
Buggy python submission (verdict: Time Limit Exceeded):
# 2つの部分列に分ける
def eqcut(start, end):
    target = (cumA[start - 1] + cumA[end]) / 2  # start = 0のときcumA[-1] = 0

    ok = start
    ng = end + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if cumA[mid] <= target:
            ok = mid
        else:
            ng = mid
    # okかok+1
    if ok == end:
        return ok
    else:
        diff1 = abs( (cumA[end] - cumA[ok]) - (cumA[ok] - cumA[start - 1]))
        diff2 = abs( (cumA[end] - cumA[ok + 1]) - (cumA[ok + 1] - cumA[start - 1]))
        if diff1 <= diff2:
            return ok
        else:
            return ok + 1
            

N = int(input())
A = [int(x) for x in input().split()]

cumA = [A[0]] + [0] * N  # 累積和  cumA[-1] = 0となるように最後にダミー
for i in range(1, N):
    cumA[i] = cumA[i - 1] + A[i]

S = [0, 0, 0, 0]
B = [0, 0]
ans = cumA[N - 1]
# 3本の境界線のうち中央を探す
for i in range(1, N - 2):
    B[0] = eqcut(0, i)  # A[0], ..., A[i]を要素の総和が最小となる2つの部分列に分ける
    S[0] = cumA[B[0]]
    S[1] = cumA[i] - cumA[B[0]]

    B[1] = eqcut(i + 1, N - 1)
    S[2] = cumA[B[1]] - cumA[i]
    S[3] = cumA[N - 1] - cumA[B[1]]

    ans = min(ans, max(S) - min(S))

print(ans)

Fixed submission:
# 2つの部分列に分ける
def eqcut(start, end):
    target = (cumA[start - 1] + cumA[end]) / 2  # start = 0のときcumA[-1] = 0

    ok = start
    ng = end + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if cumA[mid] <= target:
            ok = mid
        else:
            ng = mid
    # okかok+1
    if ok == end:
        return ok
    else:
        diff1 = abs( (cumA[end] - cumA[ok]) - (cumA[ok] - cumA[start - 1]))
        diff2 = abs( (cumA[end] - cumA[ok + 1]) - (cumA[ok + 1] - cumA[start - 1]))
        if diff1 <= diff2:
            return ok
        else:
            return ok + 1
            

N = int(input())
A = [int(x) for x in input().split()]

cumA = [A[0]] + [0] * N  # 累積和  cumA[-1] = 0となるように最後にダミー
for i in range(1, N):
    cumA[i] = cumA[i - 1] + A[i]

S = [0, 0, 0, 0]
B = [0, 0]
ans = cumA[N - 1]
# 3本の境界線のうち中央を探す
for i in range(1, N - 2):
    B[0] = eqcut(0, i)  # A[0], ..., A[i]を要素の総和が最小となる2つの部分列に分ける
    S[0] = cumA[B[0]]
    S[1] = cumA[i] - cumA[B[0]]

    B[1] = eqcut(i + 1, N - 1)
    S[2] = cumA[B[1]] - cumA[i]
    S[3] = cumA[N - 1] - cumA[B[1]]

    ans = min(ans, max(S) - min(S))

print(ans)