#P18629. Best Problem

Best Problem

Best Problem

给定一个二进制字符串 SS。你可以执行任意次数以下操作:

  • 选取一个等于 0101 的连续子串,将它替换成 1010。

求最多可以执行多少次操作。

输入格式

输入一个二进制字符串 SS。

输出格式

输出一个整数,表示最大操作次数。

数据范围

1≤∣S∣≤5×1061\le |S|\le5\times10^6。

样例输入 1

10100010011001011111

样例输出 1

5

样例输入 2

0000010101100110101101010110000110100111000010010111111100101101110101000111101111010101010010101010

样例输出 2

58

样例格式说明

原PDF第二组输入为排版而分行,并在行尾标注反斜线;实际输入没有这些换行和反斜线,上面已将完整二进制串拼成一行。