E - Binary Programming 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 900 点

問題文

高橋くんは、空文字列 S と、0 で初期化された変数 x を持っています。

また 0 および 1 のみからなる文字列 T があります。

高橋くんはこれから、以下の 2 ステップからなる操作を |T| 回繰り返します。

  • S の好きな位置に 0 または 1 を挿入する。
  • 次に、S の左から奇数番目に書かれた数字の総和を x に加算する。例えば現在 S が 01101 であるなら、S の左から奇数番目に書かれた数字は左から 0, 1, 1 なので、2 を x に加算する。

最終的に S が T に一致するような操作列における、最終的な x の値の最大値を出力してください。

制約

  • 1 \leq |T| \leq 2 \times 10^5
  • T は 0 および 1 のみからなる。

入力

入力は以下の形式で標準入力から与えられる。

T

出力

最終的に S が T に一致するような操作列における、最終的な x の値の最大値を出力せよ。

入力例 1

1101

出力例 1

5

例えば以下のような操作列が、最終的な x の値を 5 に最大化します。

  • S の先頭に 1 を挿入する。S は 1 になり、x に 1 を加算する。
  • S の 1 文字目の直後に 0 を挿入する。S は 10 になり、x に 1 を加算する。
  • S の 2 文字目の直後に 1 を挿入する。S は 101 になり、x に 2 を加算する。
  • S の先頭に 1 を挿入する。S は 1101 になり、x に 1 を加算する。

入力例 2

0111101101

出力例 2

26

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