分数: 900 点
问题陈述
Takahashi 有一个空字符串 S 和一个变量 x 其初始值为 0.
另外,我们有一个字符串 T 组成 0 和 1.
现在,高桥将执行以下两个步骤的操作 |T| 次。
- 插入
0或1在任意位置 S 他的选择。 - 然后,递增 x 的奇数位置(第一、第三、第五……)的数字之和 S。例如,如果 S is
01101,奇数位置的数字是0,1,1从左到右,所以 x 增加 2.
打印最大可能的最终值 x 在一系列操作中,使得 S 等于 T 最后。
约束
- 1 \leq |T| \leq 2 \times 10^5
- T 包括
0和1.
输入
输入由标准输入按以下格式给出:
T
输出
打印最大可能的最终值 x 在一系列操作中,使得 S 等于 T 最后。
样本输入 1
1101
示例输出 1
5
下面是最大化最终值的一系列操作 x to 5.
- 插入
1开头 S. S 变为1,和 x 增加 1. - 插入
0位于第一个字符的右侧 S. S 变为10,和 x 增加 1. - 插入
1紧邻第二个字符的右侧 S. S 变为101,和 x 增加 2. - 插入
1开头 S. S 变为1101,和 x 增加 1.
示例输入 2
0111101101
示例输出 2
26