32281번 - 유리구슬 (Glass Bead)

문제

투명한 유리구슬처럼 보이지만

그렇게 쉽게 깨지진 않을 거야

사랑해 너만을 변하지 않도록

영원히 널 비춰줄게

유리구슬로 깨지지 않을 구조물을 만들고자 한다.

구조물은 다음과 같은 피라미드 격자의 $(x,y)$에 유리구슬을 놓아 만들어진다. ($x, y$는 0ドル$ 이상의 정수)

$y>0$인 좌표의 구조물이 깨지지 않도록 하기 위해서, 구조물은 다음 조건을 충족해야 한다.

• $(x,y)$에 유리구슬이 있으려면 $(x,y-1),ドル $(x+1,y-1)$에 모두 유리구슬이 있어야 한다.

구조물의 $y=0$ 부분의 정보가 주어졌을 때, $y>0$인 곳에 유리구슬을 적절히 놓아 만들 수 있는 구조물의 유리구슬 개수의 최댓값을 구하여라.

입력

첫째 줄에 정보가 주어질 범위 $N$이 주어진다.

둘째 줄에 구조물의 $y=0$인 곳의 정보가 길이 $N$의 문자열 형식으로 주어진다.

문자열의 $i$번째 문자가 1이라면 $(i-1,0)$에 유리구슬이 있고, 아니라면 유리구슬이 없다. (1ドル\leq i\leq N$)

범위를 벗어나는 $(x,0)$ $(x\geq N)$에는 유리구슬이 없다.

출력

첫째 줄에 구조물의 유리구슬 개수의 최댓값을 출력한다.

제한

• 1ドル\leq N\leq 200000$

노트

[フレーム]

답이 C++의 int 범위를 넘어갈 수 있으므로 long long 자료형을 사용하는 것을 추천한다.