Problem CX
víRUs
Languages
en
is
You have discovered a new computer virus calling itself víRUs and it seems to have been written by a student from Reykjavík University. The virus has now infected all the computers at the university, but so far no one else seems to have noticed, since it is very discreet and only makes small changes at a time. More preciesly it only makes one operation a day, which is to reverse all bits from some memory location $a$ to some memory location $b$ on the hard drive.
The virus has the goal of overturning all data on the hard drive such that all zeroes will come before all ones. You have been following the changes the virus makes the last few days and noticed the virus will always choose $a$ and $b$ such that it maximizes the length of any substring consisting of zeroes followed by ones.
To stop the virus you need to find out the length of this substring consisting of zeroes followed by ones it could create today.
Input
The input contains one line with a bitstring which is the content of the hard drive.
Output
Print one line with the length of the substring which maximizes the damage the virus could do today.
Scoring
|
Group |
Points |
Constraints |
|
1 |
15 |
The length of the bitstring is at most $50$ |
|
2 |
15 |
The length of the bitstring is at most $350$ |
|
3 |
40 |
The length of the bitstring is at most $2 \cdot 10^3$ |
|
4 |
30 |
The length of the bitstring is at most $10^5$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
11010 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
010011 |
6 |
| Sample Input 3 | Sample Output 3 |
|---|---|
0110101001 |
5 |
