Problem p02667 (python)

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

t = input()
s = t.replace("0", "")
q = len(s) # 1の数
n = len(t)
ps = [None]*(q+1)
c = 0
j = 0
for tmp in t:
    if tmp=="1":
        ps[j] = c
        j += 1
        c = 0
    else:
        c += 1
ps[-1] = c

dp = [0] * q # インデックスqの1までのベストな配置のときの奇数の個数
pp = [0] * (q+1) # 上を実現するために使うpsの個数
if not dp:
    print(0)
else:
    dp[0] = 1
    j = 1 # j : トータルのインデックス(1はじまり)
    for i in range(1,q):
        j += 1
        p = ps[i]
        if j%2:
            pp[i] = 0
            dp[i] = dp[i-1] + 1
        elif p:
            pp[i] = 1
            j += 1
            dp[i] = dp[i-1] + 1
        else:
            pp[i] = 0
            dp[i] = dp[i-1]
    if q%2==0:
        ans = q//2 * (q//2 + 1)
    else:
        ans = q//2 * (q//2 + 1) + q//2 + 1
    
    # 1をすべて入れたあとに得られる利得
    # ppを前から順にいれていく
    j = 0
    for i in range(q+1):
        j += 1
        if not pp[i]:
            continue
        # 0を１個いれる
        j += 1
        ans += dp[i]
        if j%2:
            ans += (q-i-1) // 2
        else:
            ans += (q-i-1) // 2 + (q-i-1)%2
    
    # 残りのpsを後ろから順にいれていく
    o = 0 # 現時点より後ろの(jを0としたときの)奇数番目の1の個数
    e = 0 # 現時点より後ろの(jを0としたときの)偶数番目の1の個数
    j = q + sum(pp) # 現在地のインデックス(1はじまり)
    for i in range(q, 0, -1):
        num = ps[i] - pp[i]
        if num>0:
            ans += dp[i-1] * num
            if num%2==0:
                ans += (num//2)*o + (num//2)*e
            else:
                ans += (num//2)*o + (num//2)*e + (e if j%2==0 else o)
                e,o = o,e
        j -= 1
        if pp[i-1]:
            j -= pp[i-1]
            e += 1
        else:
            o, e = 1 + e, o

    # 最初の0を入れる
    num = ps[0] - pp[0]

    if num%2==0:
        ans += (num//2)*o + (num//2)*e
    else:
        ans += (num//2)*o + (num//2)*e + e if j%2==0 else o

    print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


t = input()
s = t.replace("0", "")
q = len(s) # 1の数
n = len(t)
ps = [None]*(q+1)
c = 0
j = 0
for tmp in t:
    if tmp=="1":
        ps[j] = c
        j += 1
        c = 0
    else:
        c += 1
ps[-1] = c

dp = [0] * q # インデックスqの1までのベストな配置のときの奇数の個数
pp = [0] * (q+1) # 上を実現するために使うpsの個数
dp[0] = 1
j = 0 # j : トータルのインデックス(1はじまり)
for i in range(q):
    j += 1
    p = ps[i]
    if j%2:
        pp[i] = 0
        dp[i] = dp[i-1] + 1
    elif p:
        pp[i] = 1
        j += 1
        dp[i] = dp[i-1] + 1
    else:
        pp[i] = 0
        dp[i] = dp[i-1]
if q%2==0:
    ans = q//2 * (q//2 + 1)
else:
    ans = q//2 * (q//2 + 1) + q//2 + 1
    
# 1をすべて入れたあとに得られる利得
# ppを前から順にいれていく
j = 0
for i in range(q+1):
    j += 1
    if not pp[i]:
        continue
    # 0を１個いれる
    j += 1
    ans += dp[i]
    if j%2:
        ans += (q-i-1) // 2
    else:
        ans += (q-i-1) // 2 + (q-i-1)%2
        
# 残りのpsを後ろから順にいれていく
ocount = 0 # 現時点より後ろの(jを0としたときの)奇数番目の1の個数
ecount = 0 # 現時点より後ろの(jを0としたときの)偶数番目の1の個数
j = q + sum(pp) # 現在地のインデックス(1始まり)
for i in range(q, 0, -1):
    num = ps[i] - pp[i]
    if num>0:
        ans += dp[i-1] * num
        if num%2==0:
            ans += (num//2)*ocount + (num//2)*ecount
        else:
            ans += (num//2)*ocount + (num//2)*ecount + ecount
        j -= 1
    if pp[i]:
        j -= pp[i]
        ecount += 1
    else:
        ocount, ecount = 1 + ecount, ocount

# 最初の0を入れる
num = ps[0] - pp[0]
if num%2==0:
    ans += (num//2)*ocount + (num//2)*ecount
else:
    ans += (num//2)*ocount + (num//2)*ecount + ocount

print(ans)