#P13863. [nomura2020]Binary Programming

[nomura2020]Binary Programming

题目描述

高桥君有一个空字符串 SS,以及一个初始值为 00 的变量 xx。

此外,他还有一个只由 0 和 1 组成的字符串 TT。

高桥君将进行 ∣T∣|T| 次如下的两步操作:

  • 在 SS 的任意位置插入一个 0 或 1。
  • 然后,将 SS 中从左起奇数位置上的数字之和加到 xx 上。例如,如果当前 SS 为 01101,那么从左起奇数位置上的数字依次为 0、1、1,因此将 22 加到 xx 上。

请输出最终 SS 与 TT 相同的所有操作序列中,最终 xx 的最大可能值。

输入格式

输入为以下格式,从标准输入读取:

TT

输出格式

请输出最终 SS 与 TT 相同的所有操作序列中,最终 xx 的最大可能值。

输入输出样例 #1

输入 #1

1101

输出 #1

5

输入输出样例 #2

输入 #2

0111101101

输出 #2

26

说明/提示

限制条件

  • 1≤∣T∣≤2×1051 \leq |T| \leq 2 \times 10^5
  • TT 只包含字符 0 和 1。

样例解释 1

例如,以下操作序列可以使最终 xx 的值最大为 55:

  • 在 SS 的开头插入 1,SS 变为 1,xx 加 11。
  • 在 SS 的第 11 个字符后插入 0,SS 变为 10,xx 加 11。
  • 在 SS 的第 22 个字符后插入 1,SS 变为 101,xx 加 22。
  • 在 SS 的开头插入 1,SS 变为 1101,xx 加 11。