Problem:


Score : 900 points

Problem Statement

Takahashi has an empty string S and a variable x whose initial value is 0.

Also, we have a string T consisting of 0 and 1.

Now, Takahashi will do the operation with the following two steps |T| times.

Insert a 0 or a 1 at any position of S of his choice.

Then, increment x by the sum of the digits in the odd positions (first, third, fifth, ...) of S. For example, if S is 01101, the digits in the odd positions are 0, 1, 1 from left to right, so x is incremented by 2.

Print the maximum possible final value of x in a sequence of operations such that S equals T in the end.

Constraints

1 \leq |T| \leq 2 \times 10^5

T consists of 0 and 1.

Input

Input is given from Standard Input in the following format:

T

Output

Print the maximum possible final value of x in a sequence of operations such that S equals T in the end.

Sample Input 1

1101

Sample Output 1

5

Below is one sequence of operations that maximizes the final value of x to 5.

Insert a 1 at the beginning of S. S becomes 1, and x is incremented by 1.

Insert a 0 to the immediate right of the first character of S. S becomes 10, and x is incremented by 1.

Insert a 1 to the immediate right of the second character of S. S becomes 101, and x is incremented by 2.

Insert a 1 at the beginning of S. S becomes 1101, and x is incremented by 1.

Sample Input 2

0111101101

Sample Output 2

26



Sample input:
1101


Sample output:
5

Submission status: Accepted

Solution code:
t = input()
before_is_zero = True
n0 = 0
n1 = 0
seq1 = 0
ans = 0
for i, x in enumerate(t):
    if x == '0':
        n0 += 1
        before_is_zero = True
    elif before_is_zero:
        tmp_add = -(n0 - (i+1)%2)//2
        ans += tmp_add
        n1 += 1
        before_is_zero = False
    else:
        ans -= tmp_add
        n1 += 1
        seq1 += 1
        before_is_zero = True
ans += (n1 - seq1) * n0 + ((n1+1)//2) * (n1//2 + 1)
print(ans)

Submission status: Accepted

Solution code:
t = input()
before_is_zero = True
n0 = 0
n1 = 0
keeped_1 = 0
ans = 0
for i, x in enumerate(t):
    if x == '0':
        n0 += 1
        before_is_zero = True
    elif x == '1':
        if before_is_zero:
            tmp_add = -(n0 - (i+1)%2)//2
            ans += tmp_add
            n1 += 1
            before_is_zero = False
        else:
            ans -= tmp_add
            n1 += 1
            keeped_1 += 1
            before_is_zero = True
ans += (n1 - keeped_1) * n0
ans += ((n1+1)//2) * (n1//2 + 1)
print(ans)

Submission status: Accepted

Solution code:
t = input()
before_is_zero = True
keeped_ones = 0
n0 = 0
ones = [0] * int(1e5+1) # (number of zeros before 1, is_odd)
ones_index = 0
for i, x in enumerate(t):
    if x == '0':
        n0 += 1
        before_is_zero = True
    elif x == '1':
        if before_is_zero:
            ones[ones_index] = (n0, (i+1)%2)
            ones_index += 1
            before_is_zero = False
        else:
            keeped_ones += 1
            ones_index -= 1
            before_is_zero = True

if before_is_zero:
    if len(ones) > 0:
        ones = ones[:-1]

ans = keeped_ones * n0
for i in range(ones_index):
    n0_before, is_odd = ones[i]
    ans += (n0_before + is_odd)//2 + (n0 - n0_before)
ans += (keeped_ones + (ones_index+1)//2) * (keeped_ones + ones_index//2 + 1)
print(ans)

Submission status: Accepted

Solution code:

"""

なるべく各操作における奇数文字目に1をいれる
最後にたす数は確定

左端が1の時、最初に入れない理由はない
最初に必要な1を全部入れない理由、あるか？
なさそう

あとはどう0を入れていくか
1のうち、いくつが空数番目・いくつが奇数番目にいあるかを考える

0を入れると、それ以降の1の偶奇がひっくり返る
差は高々1
右端は毎回ひっくり返されるので考えなくていい
2番目は、右端で1回だけ延長できる
3番目は、2回延長できる

"""

T = input()

ans = 0
onum = 0

for i in T:

    if i == "1":
        onum += 1
        ans += (onum+1)//2

odd = []
eve = []

nodd = 0
neve = 0

#print (ans)

for i in range(len(T)-1,-1,-1):

    if T[i] == "0":
        odd.append(nodd)
        eve.append(neve)
        nodd = 0
        neve = 0
    else:
        if i % 2 == 0:
            nodd += 1
        else:
            neve += 1

#print (odd,eve)
ans += nodd * ( len(T) - onum )
#print (ans)

for i in range(len(odd)):

    now = 0
    if i == 0:
        now += len(odd)//2 * eve[i]
        now += (len(odd) - len(odd)//2) * odd[i]
    else:
        now += (len(odd)-i)//2 * eve[i]
        now += ((len(odd)-i) - (len(odd)-i)//2 ) * odd[i]
        rem = len(odd) - ( (len(odd)-i)//2 +(len(odd)-i) - (len(odd)-i)//2)
        
        now += rem * max(eve[i],odd[i])

    #print (now)
    ans += now

print (ans)

Submission status: Accepted

Solution code:
t = input()

before_and_max = [[0, 0, 0] for i in range(len(t))]

for i in range(len(t)):
    if i == 0:
        if t[0] == "0":
            before_and_max[0][0] = 0
            before_and_max[0][1] = 0
            before_and_max[0][2] = 0
        else:
            before_and_max[0][0] = 1
            before_and_max[0][1] = 1
            before_and_max[0][2] = 0
    else:
        if t[i] == "0":
            before_and_max[i][0] = before_and_max[i - 1][0] + max(before_and_max[i-1][1], before_and_max[i-1][2])
            before_and_max[i][1] = max(before_and_max[i-1][1], before_and_max[i-1][2])
            before_and_max[i][2] = max(before_and_max[i-1][1], before_and_max[i-1][2])
        else:
            before_and_max[i][0] = before_and_max[i - 1][0] + ((i + 1) // 2 + (i + 1) % 2)
            before_and_max[i][1] = before_and_max[i - 1][2] + 1
            before_and_max[i][2] = before_and_max[i - 1][1]

print(before_and_max[len(t) - 1][0])

Submission status: Accepted

Solution code:
def solve(t):
    res = 0
    length = 0
    n = len(t)
    used = [0] * n
    # insert 1 greedy
    for i in range(n):
        if t[i] == "1":
            length += 1
            res += (length + 1) // 2
            used[i] = 1

    # insert 0 greedy
    cnt_temp = 0
    for i in range(n):
        if used[i]:
            cnt_temp += 1
        elif cnt_temp % 2 == 1:
            # add 0 if it is 2, 4, 6 th
            cnt_temp += 1
            length += 1
            res += (length + 1) // 2
            used[i] = 1

    cnt_unused = n - sum(used)
    switch_count = 0
    # split by other 0
    st = 0
    cnt_1_even = 0
    cnt_1_odd = 0
    for i in range(n):
        if used[i] == 0:
            switched = (switch_count + 1) // 2
            non_switched = cnt_unused - switched
            res += cnt_1_even * non_switched + cnt_1_odd * switched
            st = i + 1
            switch_count += 1
            cnt_1_even = 0
            cnt_1_odd = 0
        if t[i] == "1":
            if (i - st) % 2 == 0:
                cnt_1_even += 1
            else:
                cnt_1_odd += 1

    # add last
    switched = (switch_count + 1) // 2
    non_switched = cnt_unused - switched
    res += cnt_1_even * non_switched + cnt_1_odd * switched

    return res


def main():
    t = input()
    res = solve(t)
    print(res)


def test():
    assert solve("1101") == 5
    assert solve("0111101101") == 26


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    # import numpy as np
    # import math
    # import random
    input = stdin.readline

    t = input()[:-1]
    n = len(t)
    count_back_1 = [0]*n
    num_of_1 = 0
    cnt = 0
    for i in range(n-1, -1, -2):
        count_back_1[i] = cnt
        if t[i] == '1':
            cnt += 1
    num_of_1 += cnt
    cnt = 0
    for i in range(n-2, -1, -2):
        count_back_1[i] = cnt
        if t[i] == '1':
            cnt += 1
    num_of_1 += cnt
    # print(num_of_1)
    # print(count_back_1)

    ans = 0

    after_first_turn = [-1]*n
    after_first_turn_index = 0

    index = 0
    count_front_1 = 0
    while index < n:
        if t[index] == '1':
            after_first_turn[after_first_turn_index] = '1'
            if index == n-1:
                after_first_turn_index += 1
                break
            after_first_turn[after_first_turn_index+1] = t[index+1]
            index += 2
            count_front_1 += 1
            after_first_turn_index += 2
        else:
            ans += count_front_1
            ans += count_back_1[index]
            index += 1

        
    len_after_first_turn = after_first_turn_index    #  - 1
    # print(after_first_turn[:len_after_first_turn])
    # print(after_first_turn)
    if len_after_first_turn % 2 == 1:
        ans += (len_after_first_turn//2+1)
        len_after_first_turn -= 1
    half = len_after_first_turn//2
    ans += half*(half+1)
    print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

T = read().rstrip().decode()

T

def f(n, r, l, z):
    # 長さnの1が座標 r から l へと移動する。
    # z回立ち止まることが許されている。
    # 獲得スコアの最大値は？
    if n % 2 == 0:
        move = r - l + z
        return (move + 1) * (n // 2)
    if r == l and r % 2 == 0:
        # ev, od, ev, od, evで固定
        k = (n - 1) // 2
        move = r - l + z
        return (move + 1) * k
    # 各地点に1回ずつ立ち寄りつつ、奇数のところでz回足踏みできる
    ev = (r // 2) - ((l - 1) // 2)
    od = (r - l + 1) - ev
    od += z
    k = (n - 1) // 2
    return ev * k + od * (k + 1)

Z = T.count('0')
one = 0
to = 0
answer = 0
for i, x in enumerate(T, 1):
    if x == '0':
        if one:
            answer += f(one, i - 1, to, Z)
            one = 0
        Z -= 1
        continue
    to += 1
    one += 1
if one:
    answer += f(one, i, to, Z)

def f(n):
    # '1' * n から減らしたときのスコア
    # ただし、最初は除く
    ret = 0
    for i in range(0, n, 2):
        ret += (n - i)
    ret -= (n + 1) // 2
    return ret

n = T.count('1')
answer += f(n)
print(answer)

Submission status: Runtime Error

Solution code:
from itertools import groupby, accumulate


def solve(t):
    if t[0] == '0':
        preceding_zeros = len(t)
        t = t.lstrip('0')
        preceding_zeros -= len(t)
    else:
        preceding_zeros = 0

    if len(t) == 0:
        return 0

    grp = [(c, len(list(itr))) for c, itr in groupby(t)]
    even_ones = 0
    zeros_splitting_odd_ones = [preceding_zeros]
    for c, cnt in grp:
        if c == '1':
            if cnt % 2 == 0:
                even_ones += cnt
            else:
                even_ones += cnt - 1
                zeros_splitting_odd_ones.append(0)
        else:
            zeros_splitting_odd_ones[-1] += cnt

    # 初期状態で加算されるか
    ad = int(zeros_splitting_odd_ones[0] % 2 == 0)
    is_added_init = [ad]
    for cnt in zeros_splitting_odd_ones[1:]:
        ad ^= (cnt % 2) ^ 1
        is_added_init.append(ad)
    is_added_init.pop()
    acc_added_init = list(accumulate(reversed(is_added_init)))  # 自分より右で、初期状態で足される1の数
    acc_added_init.reverse()

    odd_ones = len(is_added_init)

    # 先頭の0を全て除くまでのスコア
    zso = zeros_splitting_odd_ones[0]
    zso1 = zso // 2
    zso0 = zso - zso1
    ans = acc_added_init[0] * zso0
    ans += (odd_ones - acc_added_init[0]) * zso1

    # 1に挟まれた0を1箇所1つずつ残して全て除くまでのスコア
    ad = int(zeros_splitting_odd_ones[0] % 2 == 0)
    for i in range(1, odd_ones):
        zso = zeros_splitting_odd_ones[i] - 1
        zso1 = zso // 2
        zso0 = zso - zso1
        fixed_ones = i
        right_ones = odd_ones - fixed_ones
        ans += fixed_ones * zso
        if ad:
            # 除外中の0区間の次の"1"が初期状態で足されるなら、区間を操作する直前にも足される
            ans += acc_added_init[i] * zso0
            ans += (right_ones - acc_added_init[i]) * zso1
        else:
            # 除外中の0区間の次の"1"が初期状態で足されないなら、区間を操作する直前には足される
            ans += (right_ones - acc_added_init[i]) * zso0
            ans += acc_added_init[i] * zso1
        ad ^= zso % 2

    # 末尾の0を全て除くまでのスコア
    ans += zeros_splitting_odd_ones[-1] * odd_ones

    # 1に挟まれた0を右から除いていくまでのスコア
    for i in range(1, odd_ones):
        left_ones = odd_ones - i
        right_ones = i
        ans += left_ones + right_ones // 2

    # 1だけの列を1つずつ除いていくスコア
    all_ones = odd_ones + even_ones
    ao1 = all_ones // 2
    ao0 = all_ones - ao1
    ans += (ao0 * (ao0 + 1) + ao1 * (ao1 + 1)) // 2

    # 0を除いている間の、偶数個の1によるスコア
    all_zeros = len(t) - all_ones + preceding_zeros
    ans += all_zeros * (even_ones // 2)

    return ans


t = input()
print(solve(t))

Submission status: Runtime Error

Solution code:

n = input()

zero_list = []
z_count = 0
ans = 0
for i in range(len(n)):
    if n[i] == "0":
        z_count += 1
    else:
        zero_list.append(z_count)
        z_count = 0
zero_list.append(z_count)

ones = n.count("1")

for i in range(1,ones+1):
    if i % 2 == 0:
        ans += i//2
    else:
        ans += i//2 + 1
             
test_string = ""
if ones % 2 == 0:
    test_string = "10"*(ones//2)
else:
    test_string = "10"*(ones//2)+"1"

test_length = len(test_string)
test_string = int(test_string,base=2)

#flip 0 to 1
for i in range(test_length):
    if bin(test_string)[test_length-i+1] == "0" and zero_list[i] > 0:
        print("xor")
        print(int("1" * (test_length-i), base=2))
        test_string = test_string ^ int("1" * (test_length-i), base=2)
        zero_list[i] -= 1
        ans += bin(test_string).count("1")

#remove more than 1 zeros
for i in range(test_length):
    while zero_list[i] > 1:
        zero_list[i] -= 2
        ans += bin(test_string)[0:i].count("1") * 2 + test_length - i

#remove last zero from back
for i in range(test_length-1,-1,-1):
    if zero_list[i] == 1:

        test_string = test_string ^ int("1" * (test_length-i), base=2)
        zero_list[i] -= 1
        ans += bin(test_string).count("1")

print(ans)

Submission status: Runtime Error

Solution code:

n = input()

def sum_odd(b):
    total=0
    odd = True
    for s in b:
        if odd and s=="1":
            total+=1
        odd = not odd
    return total

if n == "0":
    print("0")
    exit()

    
ans = 0
s = 0
while s < len(n):
    if n[s] == "0" and n[s+1] == "0":
        n = n[0:s]+n[s+2:len(n)]
        ans += n.count("1")
        s-=2
    s+=1

s = len(n)-1
while s >= 0:
    if n[s] == "0":
        ans += sum_odd(n)  
        n = n[0:s]+n[s+1:len(n)]
    s-=1

s = len(n)-1
while s>= 0:
    ans += sum_odd(n)
    n = n[0:s]+n[s+1:len(n)]
    s-=1
print(ans)

Submission status: Runtime Error

Solution code:

n = input()

def sum_odd(b):
    total=0
    odd = True
    for s in b:
        if odd and s=="1":
            total+=1
        odd = not odd
    return total

ans = 0
s = 0
while s < len(n):
    if n[s] == "0" and n[s+1] == "0":
        n = n[0:s]+n[s+2:len(n)]
        ans += n.count("1")
        s-=2
    s+=1

s = len(n)-1
while s >= 0:
    if n[s] == "0":
        ans += sum_odd(n)  
        n = n[0:s]+n[s+1:len(n)]
    s-=1

s = len(n)-1
while s>= 0:
    ans += sum_odd(n)
    n = n[0:s]+n[s+1:len(n)]
    s-=1
print(ans)

Submission status: Runtime Error

Solution code:

n = input()

def sum_odd(b):
    total=0
    odd = True
    for s in b:
        if odd and s=="1":
            total+=1
        odd = not odd
    return total

ans = 0
s = 0
while s < len(n):
    if n[s] == "0" and n[s+1] == "0":
        n = n[0:s]+n[s+2:len(n)]
        ans += n.count("1")
        s-=2
    s+=1

s = len(n)-1
while s >= 0:
    if n[s] == "0":
        ans += sum_odd(n)  
        n = n[0:s]+n[s+1:len(n)]
    s-=1

s = len(n)-1
while s>= 0:
    ans += sum_odd(n)
    n = n[0:s]+n[s+1:len(n)]
    s-=1
print(ans)

Submission status: Runtime Error

Solution code:
T=input()
n=len(T)
i=r=a=0
for c in T:
  k=i-r
  if c=='0':
    r+=!k&1
  else:
    a+=i//2-k//2+(!k&1)*(n-i)
  i+=1
print(a)

Submission status: Runtime Error

Solution code:
T=input()
n=len(t)
i=r=a=0
for c in T:
  k=i-r
  if c=='0':
    r+=k&1
  else:
    a+=i//2-k//2+(k&1)*(n-i)
  i+=1
print(a)

Submission status: Runtime Error

Solution code:
T=input()
n=len(t)
i=r=a=0
for c in T:
  k=i-r
  if c=='0':r+=k&1
  else:a+=i//2-k//2+(k&1)*(n-i)
print(a)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
import math
import re
T=input()
x=0
Td=T
d = len(re.sub(r'0', '', Td))
x += math.ceil((d/2+1)*d/2)
spT = T.split('0')
lenT = list(map(len, spT))

tmpX = math.ceil(d/2)
bT = 0
aT = d
tmp = ''
for i in range(len(spT) - 1):
    tmp += spT[i]
    bT += lenT[i]
    aT -= lenT[i]
    if bT % 2==1:
        bT += 1
        if aT % 2 ==1:
            tmpX += 1
        x += tmpX
        tmp += '0'
    else:
        tmp +='+'
tmp += spT[-1]

spT = tmp.split('+')
vT =[]
aT = bT
bT = 0
odT = 0
for i in range(len(spT)):
    od = len(re.sub(r'0', '', spT[i][::2]))
    ev = len(re.sub(r'0', '', spT[i][::2]))
    odT += od
    vt.append(od - ev)

while len(vT) >1:
    tmpIdx = len(vT)-1
    tmpL = -sum(vT[i:])
    tmpMax = -1
    for i in range(1, len(vT)):
        if odT + tmpL > tmpMax:
            tmpIdx = i
            tmpMax = odT + tmpL
        tmpL += vt[i]
    odT = tmpMax
    x += odT
    vT[tmpIdx-1] += vT[tmpIdx]

    del vT[tmpIdx]

print(x)

Submission status: Runtime Error

Solution code:
import math
import re
T=input()
x=0
Td=T
d = len(re.sub(r'0', '', Td))
x += math.ceil((d/2+1)*d/2)
spT = T.split('0')
lenT = list(map(len, spT))

#tmpT = '1'*d
tmpX = math.ceil(d/2)
bT = 0
aT = d
tmp = ''
for i in range(len(spT) - 1):
    tmp += spT[i]
    bT += lenT[i]
    aT -= lenT[i]
    if bT % 2==1:
        bT += 1
        if aT % 2 ==1:
            tmpX += 1
        x += tmpX
        tmp += '0'
    else:
        tmp +='+'
tmp += spT[-1]

spT = tmp.split('+')
vT =[]
aT = bT
bT = 0
odT = 0
ccT = 0
for i in range(len(spT)):
    vT.append([len(re.sub(r'0', '', spT[i][::2])), len(re.sub(r'0', '', spT[i][1::2]))])
    odT += vT[-1][0]
    ccT += vT[-1][1]


while len(vT) >1:
    tmpIdx = len(vT)
    tmpL = 0
    tmpMax = 0
    for i in reversed(range(1, len(vT))):
        tmpL += vT[i][1] - vT[i][0]
        if tmpMax  < odT + tmpL:
            tmpIdx = i
            tmpMax = odT + tmpL

    for i in (range(tmpIdx, len(vT))):
        tmpVT = vT[i][1]
        vT[i][1] = vT[i][0]
        vT[i][0] = tmpVT
    odT = tmpMax
    x +=odT
    vT[tmpIdx-1][0] += vT[tmpIdx][0]
    vT[tmpIdx-1][1] += vT[tmpIdx][1]
    del vT[tmpIdx]

print(x)

Submission status: Runtime Error

Solution code:
t = input()
before_is_zero = True
keeped_ones = 0
n0 = 0
ones = [0] * int(1e5) # (number of zeros before 1, is_odd)
ones_index = 0
for i, x in enumerate(t):
    if x == '0':
        n0 += 1
        before_is_zero = True
    elif x == '1':
        if before_is_zero:
            ones[ones_index] = (n0, (i+1)%2)
            ones_index += 1
            before_is_zero = False
        else:
            keeped_ones += 1
            ones_index -= 1
            before_is_zero = True
if before_is_zero:
    if len(ones) > 0:
        ones = ones[:-1]

ans = keeped_ones * n0
for i in range(ones_index):
    n0_before, is_odd = ones[i]
    ans += (n0_before + is_odd)//2 + (n0 - n0_before)
ans += (keeped_ones + (ones_index+1)//2) * (keeped_ones + ones_index//2 + 1)
print(ans)

Submission status: Runtime Error

Solution code:
t = input()
keep = True
keeped_ones = 0
n0 = 0
ones = [0] * int(1e5) # (number of zeros before 1, is_odd)
ones_index = 0
for i, x in enumerate(t):
    if x == '0':
        n0 += 1
        keep = True
    elif x == '1':
        if keep:
            ones[ones_index] = (n0, (i+1)%2)
            ones_index += 1
            keep = False
        else:
            keeped_ones += 1
            ones_index -= 1
            keep = True
if keep:
    ones = ones[:-1]

ans = keeped_ones * n0
for i in range(ones_index):
    n0_before, is_odd = ones[i]
    ans += (n0_before + is_odd)//2 + (n0 - n0_before)
ans += (keeped_ones + (ones_index+1)//2) * (keeped_ones + ones_index//2 + 1)
print(ans)

Submission status: Runtime Error

Solution code:
t = open(0)[0][:-1]
keep = True
keeped_ones = 0
n0 = 0
ones = [] # (number of zeros before 1, is_odd)
for i, x in enumerate(t):
    if x == '0':
        n0 += 1
        keep = True
    elif x == '1':
        if keep:
            ones.append((n0, (i+1)%2))
            keep = False
        else:
            keeped_ones += 1
            ones = ones[:-1]
            keep = True

ans = keeped_ones * n0
for n0_before, is_odd in ones:
    ans += (n0_before + is_odd)//2 + (n0 - n0_before)
ans += (keeped_ones + (len(ones)+1)//2) * (keeped_ones + len(ones)//2 + 1)
print(ans)

Submission status: Runtime Error

Solution code:
#import itertools
#import numpy as np
#from scipy.sparse.csgraph import minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix

from itertools import accumulate


def main():
    T = [int(c) for c in input()]
    odd = [T[i] for i in range(len(T)) if i%2==0]
    even = [T[i] for i in range(len(T)) if i%2!=0]

    ret = 0
    acc_odd = list(accumulate(odd))
    acc_even = list(accumulate(even))
    while len(acc_even) > 0:
        score = 0
        #print(f'odd:{odd}')
        #print(f'even:{even}')
        #print(f'acc_odd:{acc_odd}')
        #print(f'acc_even:{acc_even}')
        pos = (-1, False)
        for i in range(len(odd)):
            if i==0:
                x = acc_even[-1]
                y = acc_odd[i] + acc_even[-1] - acc_even[i]
            elif i==len(odd)-1:
                x = acc_odd[i-1] + acc_even[-1] - acc_even[i-1]
                if len(acc_even) == len(acc_odd):
                    y = acc_odd[i] + acc_even[-1] - acc_even[i]
                    assert y == acc_odd[i]
                else:
                    y = 0
            else:
                x = acc_odd[i-1] + acc_even[-1] - acc_even[i-1]
                y = acc_odd[i] + acc_even[-1] - acc_even[i]
            if x > y and x > score:
                pos = (i, True)
                score = x
            elif y > x and y > score:
                pos = (i, False)
                score = y
            elif x == y and x > score:  #???
                #print(f'x==y=={x}!!!')
                if odd[i]==0:
                    pos = (i, True)
                    score = x
                else:
                    pos = (i, False)
                    score = y
        ret += score
        #print(f'pos:{pos}')
        #print(f'score:{score}')
        assert pos[0] != -1
        if pos[1]:  #oddから抜く
            odd_ = odd[:pos[0]]
            odd_.extend(even[pos[0]:])
            even_ = even[:pos[0]]
            even_.extend(odd[pos[0]+1:])
        else:  #evenから抜く
            odd_ = odd[:pos[0]+1]
            odd_.extend(even[pos[0]+1:])  #超えた場合は空リストになるっぽい
            even_ = even[:pos[0]]
            even_.extend(odd[pos[0]+1:])
        odd, even = odd_.copy(), even_.copy()
        acc_odd = list(accumulate(odd))
        acc_even = list(accumulate(even))
    if len(odd) == 1:
        ret += odd[0]
    print(ret)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
a=input()
b=int(a)
a=list(a)
m=len(a)
c=m
k=1
while k<b+1:

    if k%2==1 and k!>=m:
        a[k-1]=int(a[k-1])
        c=a[k-1]+c
    k=k+1
print(c)

Submission status: Runtime Error

Solution code:
n =input()
while True:
    for i in range(len(n)):
        if i>n:
            break
　　　　if i<n:
    　　　　v=n[0::2]
            b=sum(v)
            b=b+1
        print(b)

Submission status: Runtime Error

Solution code:
def check(M, a):
    for i,b in enumerate(M):
        a = a - int(b)
    return a

def popall(M):
    c = []
    for i in range(0,len(M)):
        if i > 0:
            a = M[0:i] + M[i+1::]
        elif i == 0:
            a = M[i+1::]
        c.append(''.join(a))
    return c

def ckall(c):
    ans = []
    for _,i in enumerate(c):
        ans.append(check(i,0))
    return ans.index(min(ans)), c[ans.index(min(ans))]

def efun(N,a):
    b = ckall(popall(N[0::2]))[0]
    if int(b) > 0:
        rN = N[0:b] + N[b+1::]
    elif int(b) == 0:
        rN = N[b+1::]
    a = a + int(ckall(popall(N[0::2]))[1])
    return rN,a

if __name__ == '__main__':
    N = list(input())
    a = 0
    while True:
        N,a = efun(N,a)
        if len(N) == 2:
            print(''.join(N))
            print(a)
            break

Submission status: Runtime Error

Solution code:
str = input()
 
str_len = len(str)
 
result_count = 0
 
for i in range(str_len):
  result_count = result_count + (i+1)//2

zero_count = 0
zero_even_count = 0
zero_odd_count = 0
for i in range(str_len):
  if(str[i] == '0'):
      zero_count = zero_count + 1
    if(i%2 == 1):
      zero_odd_count = zero_odd_count + 1
    else:
      zero_even_count = zero_even_count + 1
    result_count = result_count - zero_count - zero_odd_count + zero_even_count

print(result_count)

Submission status: Runtime Error

Solution code:
str = input()
 
str_len = len(str)
 
result_count = 0
 
for i in range(str_len):
  result_count = result_count + (i+1)//2

zero_count = 0
zero_even_count = 0
zero_odd_count = 0
for i in range(str_len):
  if(str[i] == '0'):
      zero_count = zero_count + 1
    if(i%2 == 1):
      zero_odd_count = zero_odd_count + 1
    else:
      zero_even_count = zero_even_count + 1
      
  result_count = result_count - zero_count - zero_odd_count + zero_even_count

print(result_count)

Submission status: Runtime Error

Solution code:
str = input()
 
str_len = len(str)
 
result_count = 0
 
for i in range(str_len):
  result_count = result_count + (i+1)//2

zero_count = 0
zero_even_count = 0
zero_odd_count = 0
for i in range(str_len):
  if(str[i] == '0'):
      zero_count = zero_count + 1
    if(i%2 == 1):
      zero_odd_count = zero_odd_count + 1
    else:
      zero_even_count = zero_even_count + 1
      
  result_count = result_count - zero_odd_count

print(result_count)

Submission status: Runtime Error

Solution code:
str = input()
 
str_len = len(str)
 
result_count = 0
 
for i in range(str_len):
  result_count = result_count + (i+1)//2

zero_count = 0
zero_even_count = 0
zero_odd_count = 0
for i in range(str_len):
  if(str[i] == '0'):
      zero_count = zero_count + 1
    if(i%2 == 1):
      zero_odd_count = zero_odd_count + 1
    else:
      zero_even_count = zero_even_count + 1
      
  result_count = result_count - (zero_even_count - zero_odd_count)

print(result_count)

Submission status: Runtime Error

Solution code:
str = input()
 
str_len = len(str)
 
result_count = 0
 
for i in range(str_len):
  result_count = result_count + (i+1)//2
 
zero_count = 0
for i in range(len_str):
  if(str[i] == '0'):
    if(i%2 == 1):
      zero_count = zero_count + 1
      result_count = result_count - zero_count
 
print(result_count)

Submission status: Runtime Error

Solution code:
str = input()
 
str_len = len(str)
 
result_count = 0
 
for i in range(str_len):
  result_count = result_count + (i+1)/2

zero_count = 0
for i in range(len_str):
  if(str[i] == '0'):
    if(i%2 == 1):
      zero_count = zero_count + 1
      result_count = result_count - zero_count

print(result_count)

Submission status: Runtime Error

Solution code:
str = input()
 
str_len = len(str)
 
result_count = 0
 
for i in range(str_len):
  result_count = result_count + (i+1)/2
 
zero_count = 0
for i in range(len_str):
  if(str[i] == '0'):
    if(i%2 == 1):
      zero_count = zero_count + 1
      result_count = result_count - zero_count
 
print(result_count)

Submission status: Runtime Error

Solution code:
str = input()

str_len = len(str)

result_count = 0

one_only_str = str.replace('0','')

for i in range(str_len):
  result_count = result_count + (i+1)/2

zero_count = 0
for i in range(len_str-1):
  if(str[i] === '0'):
    if(i&2 === 1):
      zero_count = zero_count + 1
      result_count = result_count - zero_count

print(result_count)

Submission status: Runtime Error

Solution code:
t = list(map(int, input()))
one = t.count(1)
print(t*(t+1)//2-1)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
t = input()
s = t

@lru_cache(maxsize=None)
def loop_cache(s):
    if len(s) == 0:
        return 0

    else:
        return max([loop_cache(s[:j]+s[j+1:]) for j in range(len(s))]) + sum([int(i) for i in list(s)[::2]])

res = loop_cache(s)
print(res)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
t = input()
s = t

@lru_cache(maxsize=2*(10**5))
def loop_cache(s):
    if len(s) == 0:
        return 0

    else:
        return max([loop_cache(s[:j]+s[j+1:]) for j in range(len(s))]) + sum([int(i) for i in list(s)[::2]])

res = loop_cache(s)
print(res)