702. One Calm Spell at the Counter
A shop is open for n minutes. In minute i, c[i] customers arrive, and g[i] says
whether the owner is grumpy that minute (1) or not (0). Customers are satisfied unless the
owner is grumpy during their minute.
The owner can stay calm for one stretch of exactly k consecutive minutes. Print the largest
number of satisfied customers achievable.
c = 1 0 1 2 1 1 7 5
g = 0 1 0 1 0 1 0 1
k = 3 -> 16
## Split the total into a part that cannot change and a part that can
Customers arriving in a non grumpy minute are satisfied no matter what, so they are a FIXED base. The calm spell can only rescue customers arriving in grumpy minutes inside it.
answer = base + max over windows of length k of (customers in grumpy minutes inside)
Separating the untouchable part from the part the choice controls is the move, and it turns a question about the whole timeline into a question about one fixed window.
Without that split, people slide a window while recomputing the whole satisfied total inside
it, which is correct and O(n * k).
## The sweep
base = sum of c[i] where g[i] == 0
cur = sum of c[i] where g[i] == 1, over i in 0 .. k-1
gain = cur
for i in k .. n-1:
if g[i] == 1: cur += c[i]
if g[i-k] == 1: cur -= c[i-k]
gain = max(gain, cur)
answer = base + gain
## Why the gain is never negative
The empty gain is 0 and every window contributes at least 0, so the calm spell never hurts. That also means "use the spell" is always at least as good as not using it, and there is no case to compare against.
## Boundaries
k = n covers the whole day, and the answer is every customer.
An owner never grumpy has gain 0 and answer equal to the total.
An owner always grumpy has base 0, so the answer is the heaviest window of length k, which
is problem 111.
## Overflow
200000 minutes with up to 1000 customers each total 2 * 10^8, which fits in 32 bits, but
the base plus the gain is still safest in 64.
## Cost
Time O(n). Space O(1) beyond the input.
Constraints - `1 ≤ k ≤ n ≤ 200000` - `0 ≤ each customer count ≤ 1000` - each flag is `0` or `1`
Input
The first line contains two integers n and k.
The second line contains n integers, the customer counts.
The third line contains n integers, each 0 or 1, the grumpy flags.
Output
Print one integer, the largest number of satisfied customers.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.