# CFR 795 L. Bars ( Binary Search )

Problem - L - Codeforces

The first line contains two integers n and k (2 ≤ n ≤ 200 000, 2 ≤ k ≤ n) — the length of the workday in minutes and the number of chocolate bars, which Polycarp has in the beginning of the workday.
The second line contains the string with length n consisting of zeros and ones. If the i-th symbol in the string equals to zero, Polycarp has no important things to do in the minute i and he can eat a chocolate bar. In the other case, Polycarp is busy in the minute i and can not eat a chocolate bar. It is guaranteed, that the first and the last characters of the string are equal to zero, and Polycarp always eats chocolate bars in these minutes.

O( N lg N ) / O( N )

```<?php
// ( \$N, \$K ) is not allowed........... claimed by compiler being parsing error
list(\$N, \$K) = explode(" ", fgets(STDIN));
\$N = (int) \$N;
\$K = (int) \$K - 2;
\$seq = fgets(STDIN);
\$rp = array(); // rp[ i ] : maximum j such that j ≤ i and seq[ j ] == 0
for(\$i = 0, \$prev = 0; \$i < \$N; ++\$i) {
if(\$seq[\$i] == '0') {
\$prev = \$i;
}
array_push(\$rp, \$prev);
}
\$lb = 0;
\$ub = \$N - 2;
\$ans = \$ub;
while(\$lb <= \$ub) {
\$mid = floor((\$lb + \$ub) / 2);
\$cost = 0;
for(\$i = 1, \$prev = 0; \$i + 1 < \$N; ++\$i) {
\$lim = \$prev + \$mid + 1;
if(\$lim >= \$N - 1) break;
if(\$seq[\$i] == '1') {
if(\$lim == \$i) {
\$cost = \$K + 1;
}
}
if(\$rp[\$lim] == \$i) {
++\$cost;
\$prev = \$i;
}
}
if(\$cost <= \$K) {
\$ans = \$mid;
\$ub = \$mid - 1;
} else {
\$lb = \$mid + 1;
}
}
echo \$ans;
?>
```