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

Solution (Python):
from itertools import groupby, accumulate


def solve(t):
    grp = [(c, len(list(itr))) for c, itr in groupby(t)]
    even_ones = 0
    zeros_splitting_odd_ones = [0]
    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)))  
    acc_added_init.reverse()

    odd_ones = len(is_added_init)
    ans = 0

    if odd_ones > 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

        
        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
            left_ones = i
            right_ones = odd_ones - left_ones
            ans += left_ones * zso  
            ans += left_ones + (right_ones + 1) // 2  
            if ad:
                
                ans += acc_added_init[i] * zso0
                ans += (right_ones - acc_added_init[i]) * zso1
            else:
                
                ans += (right_ones - acc_added_init[i]) * zso0
                ans += acc_added_init[i] * zso1
            ad ^= zso % 2

        
        ans += zeros_splitting_odd_ones[-1] * odd_ones

    
    all_ones = odd_ones + even_ones
    ao1 = all_ones // 2
    ao0 = all_ones - ao1
    ans += (ao0 * (ao0 + 1) + ao1 * (ao1 + 1)) // 2

    
    all_zeros = len(t) - all_ones
    ans += all_zeros * (even_ones // 2)

    return ans


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

Solution (Python):
from itertools import groupby, accumulate


def solve(t):
    grp = [(c, len(list(itr))) for c, itr in groupby(t)]
    even_ones = 0
    zeros_splitting_odd_ones = [0]
    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)))  
    acc_added_init.reverse()

    odd_ones = len(is_added_init)
    ans = 0

    if odd_ones > 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

        
        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:
                
                ans += acc_added_init[i] * zso0
                ans += (right_ones - acc_added_init[i]) * zso1
            else:
                
                ans += (right_ones - acc_added_init[i]) * zso0
                ans += acc_added_init[i] * zso1
            ad ^= zso % 2

        
        ans += zeros_splitting_odd_ones[-1] * odd_ones

        
        for i in range(1, odd_ones):
            left_ones = odd_ones - i
            right_ones = i
            ans += left_ones + (right_ones + 1) // 2

    
    all_ones = odd_ones + even_ones
    ao1 = all_ones // 2
    ao0 = all_ones - ao1
    ans += (ao0 * (ao0 + 1) + ao1 * (ao1 + 1)) // 2

    
    all_zeros = len(t) - all_ones
    ans += all_zeros * (even_ones // 2)

    return ans


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

Solution (Python):
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)))  
    acc_added_init.reverse()

    odd_ones = len(is_added_init)
    ans = 0

    if odd_ones > 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
        

        
        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:
                
                ans += acc_added_init[i] * zso0
                ans += (right_ones - acc_added_init[i]) * zso1
            else:
                
                ans += (right_ones - acc_added_init[i]) * zso0
                ans += acc_added_init[i] * zso1
            ad ^= zso % 2
        

        
        ans += zeros_splitting_odd_ones[-1] * odd_ones
        

    
    for i in range(1, odd_ones):
        left_ones = odd_ones - i
        right_ones = i
        ans += left_ones + (right_ones + 1) // 2
    

    
    all_ones = odd_ones + even_ones
    ao1 = all_ones // 2
    ao0 = all_ones - ao1
    ans += (ao0 * (ao0 + 1) + ao1 * (ao1 + 1)) // 2
    

    
    all_zeros = len(t) - all_ones + preceding_zeros
    ans += all_zeros * (even_ones // 2)

    return ans


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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    s=SI()
    n=len(s)
    n2=n//2
    ans=n2*(n2+1)+n%2*(n2+1)
    
    rem=0
    for i,c in enumerate(s):
        if c=="1":continue
        ans-=(rem+1)//2
        if rem%2==0 and i%2==0:ans-=1
        if (i-rem)%2==0:rem+=1
    print(ans)

main()

Solution (Python):
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) 
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 
pp = [0] * (q+1) 
if not dp:
    print(0)
else:
    dp[0] = 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
    
    
    
    j = 0
    for i in range(q+1):
        j += 1
        if not pp[i]:
            continue
        
        j += 1
        ans += dp[i]
        if j%2:
            ans += (q-i-1) // 2
        else:
            ans += (q-i-1) // 2 + (q-i-1)%2
    
    
    o = 0 
    e = 0 
    j = q + sum(pp) 
    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

    
    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)

Solution (Python):
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
tmpOd = True

for i in range(len(spT)):
    
    od = len(re.sub(r'0', '', spT[i][0 if tmpOd else 1::2]))
    ev = len(re.sub(r'0', '', spT[i][1 if tmpOd else 0::2]))
    odT += od
    vT.append(od - ev)
    if len(spT[i]) %2 == 1:
        tmpOd = not tmpOd

for i in reversed(range(1, len(spT))):
    odT = odT - vT[i]
    x += odT
    vT[i-1] -= vT[i]


print(x)

Solution (Python):
T=input()
i=r=a=k=0
for c in T:a+=(i//2-k//2+(~k&1)*(len(T)-i))*(c=="1");i+=1;k-=(~k&1)*(c=='0')-1
print(a)

Solution (Python):
T=input()
i=r=a=k=0
for c in T:a+=(i//2-k//2+(~k&1)*(len(T)-i))*(c=="1");i+=1;k-=(~k&1)*(c=='0')-1;
print(a)

Solution (Python):
T=input()
n=len(T)
i=r=a=0
for c in T:k=i-r;r+=(~k&1)*(c=='0');a+=(i//2-k//2+(~k&1)*(n-i))*(c=="1");i+=1
print(a)

Solution (Python):
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)

Solution (Python):
t=input()
n=len(t)
pos=[]
sum=0
for i in range(n):
  if t[i]=="1":
    sum+=1
  else:
    pos.append(sum)
x=(sum+1)//2*((sum+2)//2)
sz=len(pos)
cnt=0
res=[]
for i in range(sz):
  if ((pos[i]&1)^(cnt&1)):
    sum+=1
    cnt+=1
    x+=(sum+1)//2
  else:
    res.append(i)
res=res[::-1]
odd=0
even=0
for i in range(len(res)):
  sum+=1
  if i&1:
    odd = sz - res[i] - even
    x+=(sum+1)//2-odd
  else:
    even=sz-res[i]-odd
    x+=(sum+1)//2-even
print(x)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
t = input()
before_is_zero = True
keeped_ones = 0
n0 = 0
ones = [0] * int(1e5+1) 
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)

Solution (Python):

"""

なるべく各操作における奇数文字目に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



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


ans += nodd * ( len(T) - onum )


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])

    
    ans += now

print (ans)

Solution (Python):
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])

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

    
    cnt_temp = 0
    for i in range(n):
        if used[i]:
            cnt_temp += 1
        elif cnt_temp % 2 == 1:
            
            cnt_temp += 1
            length += 1
            res += (length + 1) // 2
            used[i] = 1

    cnt_unused = n - sum(used)
    switch_count = 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

    
    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()

Solution (Python):
if __name__ == '__main__':
    from sys import stdin
    
    
    
    
    
    
    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
    
    

    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    
    
    
    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)

Solution (Python):
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):
    
    
    
    if n % 2 == 0:
        move = r - l + z
        return (move + 1) * (n // 2)
    if r == l and r % 2 == 0:
        
        k = (n - 1) // 2
        move = r - l + z
        return (move + 1) * k
    
    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):
    
    
    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)