Problem p03310 (python)

Fixed submission:
# encoding: utf-8
import math
N = int(input())
A = list(map(int, input().split()))

def binsearch(seq, l, r, tar):
    # print("##", l, r, LmR[l:r + 1], tar)
    m = l + (r - l) // 2
    if l >= r: return l
    elif seq[m] < tar: return binsearch(seq, m + 1, r, tar)
    else: return binsearch(seq, l, m, tar)

# sum(A[i:j]) == Asum[j] - Asum[i]
Asum = [0]
tmp = 0
for Ai in A:
    tmp += Ai
    Asum.append(tmp)

LmR = []
for SAi in Asum[:-1]:
    LmR.append(-Asum[-1] + 2 * SAi)

b1, b3 = (1, 3)
parts = [A[0], A[1], A[2], Asum[N] - Asum[3]]
ans = max(parts) - min(parts)
for b2 in range(2, N - 1):
    parts[1] -= A[b2]
    parts[2] += A[b2]
    if b3 == b2: b3 = b2 + 1
    # b1
    for btmp in range(b1, b2):
        bfr = math.fabs((Asum[b2] - Asum[btmp]) - (Asum[btmp] - Asum[0]))
        aft = math.fabs((Asum[b2] - Asum[btmp + 1]) - (Asum[btmp + 1] - Asum[0]))
        if aft < bfr: continue
        else: break
    b1 = btmp
    # b3
    for btmp in range(b3, N):
        bfr = math.fabs((Asum[N] - Asum[btmp]) - (Asum[btmp] - Asum[b2]))
        aft = math.fabs((Asum[N] - Asum[btmp + 1]) - (Asum[btmp + 1] - Asum[b2]))
        if aft < bfr: continue
        else: break
    b3 = btmp
    # update
    parts = [Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[N] - Asum[b3]]
    if ans > max(parts) - min(parts): ans = max(parts) - min(parts)

print(ans)

# TLE
# # find b2 initial position (sub-optimal)
# tar = 0
# b2 = binsearch(LmR, 2, N - 2, tar)
# if tar - LmR[b2 - 1] < LmR[b2] - tar: b2 = max((2, b2 - 1))
# # b1
# tar = -(Asum[N] - Asum[b2])
# b1 = binsearch(LmR, 1, b2 - 1, tar)
# if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
# # b3
# tar = Asum[b2]
# b3 = binsearch(LmR, b2 + 1, N - 1, tar)
# if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))

# parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
# ans = max(parts) - min(parts)
# b2_init = b2

# # sweep b2
# for b2 in range(2, N - 1):
#     # escape
#     if b2 == b2_init: continue
#     elif LmR[b2] < -2 * ans: continue
#     elif LmR[b2] > 2 * ans: break
#     # b1
#     tar = -(Asum[N] - Asum[b2])
#     b1 = binsearch(LmR, 1, b2 - 1, tar)
#     if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
#     # escape
#     if math.fabs((Asum[b2] - Asum[b1]) - (Asum[b1])) >= ans: continue
#     # b3
#     tar = Asum[b2]
#     b3 = binsearch(LmR, b2 + 1, N - 1, tar)
#     if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))
#     parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
#     if max(parts) - min(parts) < ans: ans = max(parts) - min(parts)
    
# print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
import math
N = int(input())
A = list(map(int, input().split()))

def binsearch(seq, l, r, tar):
    # print("##", l, r, LmR[l:r + 1], tar)
    m = l + (r - l) // 2
    if l >= r: return l
    elif seq[m] < tar: return binsearch(seq, m + 1, r, tar)
    else: return binsearch(seq, l, m, tar)

Asum = [0]
tmp = 0
for Ai in A:
    tmp += Ai
    Asum.append(tmp)

LmR = []
for SAi in Asum[:-1]:
    LmR.append(-Asum[-1] + 2 * SAi)

# find b2 initial position (sub-optimal)
tar = 0
b2 = binsearch(LmR, 1, N - 1, tar)
if tar - LmR[b2 - 1] < LmR[b2] - tar: b2 = max((2, b2 - 1))
# b1
tar = -(Asum[N] - Asum[b2])
b1 = binsearch(LmR, 1, b2 - 1, tar)
if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
# b3
tar = Asum[b2]
b3 = binsearch(LmR, b2 + 1, N - 1, tar)
if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))

parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
ans = max(parts) - min(parts)
b2_init = b2

# sweep b2
for b2 in range(2, N - 1):
    # escape
    if b2 == b2_init: continue
    elif LmR[b2] < -2 * ans: continue
    elif LmR[b2] > 2 * ans: break
    # b1
    tar = -(Asum[N] - Asum[b2])
    b1 = binsearch(LmR, 1, b2 - 1, tar)
    if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
    # escape
    if math.fabs((Asum[b2] - Asum[b1]) - (Asum[b1])) >= ans: continue
    # b3
    tar = Asum[b2]
    b3 = binsearch(LmR, b2 + 1, N - 1, tar)
    if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))
    parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
    if max(parts) - min(parts) < ans: ans = max(parts) - min(parts)
    
print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
import math
N = int(input())
A = list(map(int, input().split()))

def binsearch(seq, l, r, tar):
    # print("##", l, r, LmR[l:r + 1], tar)
    m = l + (r - l) // 2
    if l >= r: return l
    elif seq[m] < tar: return binsearch(seq, m + 1, r, tar)
    else: return binsearch(seq, l, m, tar)

Asum = [0]
tmp = 0
for Ai in A:
    tmp += Ai
    Asum.append(tmp)

LmR = []
for SAi in Asum[:-1]:
    LmR.append(-Asum[-1] + 2 * SAi)

# find b2 initial position (sub-optimal)
tar = 0
b2 = binsearch(LmR, 1, N - 1, tar)
if tar - LmR[b2 - 1] < LmR[b2] - tar: b2 = max((1, b2 - 1))
# b1
tar = -(Asum[N] - Asum[b2])
b1 = binsearch(LmR, 1, b2 - 1, tar)
if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
# b3
tar = Asum[b2]
b3 = binsearch(LmR, b2 + 1, N - 1, tar)
if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))

parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
ans = max(parts) - min(parts)
b2_init = b2

# sweep b2
for b2 in range(2, N - 1):
    # escape
    if b2 == b2_init: continue
    elif LmR[b2] < -2 * ans: continue
    elif LmR[b2] > 2 * ans: continue
    # b1
    tar = -(Asum[N] - Asum[b2])
    b1 = binsearch(LmR, 1, b2 - 1, tar)
    if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
    # escape
    if math.fabs((Asum[b2] - Asum[b1]) - (Asum[b1])) >= ans: continue
    # b3
    tar = Asum[b2]
    b3 = binsearch(LmR, b2 + 1, N - 1, tar)
    if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))
    parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
    if max(parts) - min(parts) < ans: ans = max(parts) - min(parts)
    
print(ans)