No Casino in the Mountains

The problem is basically about packing hikes into stretches of good weather.

A hike needs exactly $k$ consecutive good-weather days. After a hike, Jean cannot start another hike on the very next day, so between two hikes there must be at least one unused day.

The key thing: rainy days split the problem. A hike cannot cross a rainy day, so every maximal block of zeroes can be handled independently.

For example, if the array has a good-weather streak like:

$0\ 0\ 0\ 0\ 0\ 0\ 0$

and $k=3$, then Jean can do:

• hike on days $1,2,3$
• break on day $4$
• hike on days $5,6,7$

That gives $2$ hikes.

One zero-streak

Suppose we have a maximal streak of good weather of length $L$.

If Jean makes $x$ hikes inside this streak:

• each hike uses $k$ days, so hikes use $xk$ days total;
• between every pair of consecutive hikes, he needs one break day;
• there are $x-1$ gaps between $x$ hikes.

So the total number of days needed is:

$xk + (x-1)$

This must fit inside the streak:

$xk + (x-1) \le L$

Simplify:

$x(k+1)-1 \le L$

$x(k+1) \le L+1$

So the maximum possible $x$ is:

$\left\lfloor \frac{L+1}{k+1} \right\rfloor$

That is the whole trick. Tiny formula, very Codeforces 800, no casino required.

Why this is optimal

Inside a zero-streak, starting hikes as early as possible is never bad. If you delay a hike, you only waste good-weather days before it, and that cannot create more room later. The densest valid pattern is:

$\underbrace{k\text{ hike days}}_{\text{hike}} ,\ 1\text{ break day},\ \underbrace{k\text{ hike days}}_{\text{hike}},\ 1\text{ break day},\dots$

So each completed hike costs $k+1$ days, except the final hike does not need a break after it. That is exactly why the formula is $(L+1)/(k+1)$ instead of just $L/(k+1)$.

A common wrong idea is to count every subarray of length $k$ containing only zeroes. That overcounts badly because overlapping hikes are not allowed, and even back-to-back hikes are illegal without a break day. For $k=3$ and seven zeroes, there are five all-zero windows, but the answer is only two. Brutal, but fair.

Algorithm

Scan the array from left to right:

1. Keep a variable cur = current length of consecutive zeroes.
2. If $a_i=0$, increment cur.
3. If $a_i=1$, finish the current zero-streak by adding $\left\lfloor\frac{cur+1}{k+1}\right\rfloor$ to the answer, then reset cur=0.
4. After the loop, process the final streak the same way.

The total complexity is $O(n)$ per test case, and since the sum of all $n$ is at most $10^5$, this easily fits.