leetcode 1052 - Grumpy Bookstore Owner

https://leetcode.com/problems/grumpy-bookstore-owner/

Today, the bookstore owner has a store open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

Example 1:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes.
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

Note:

1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[i] <= 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
int size = customers.size();

vector<int> satisfied(size+1);
vector<int> satisfied_not_grumpy(size+1);

satisfied[0] = satisfied_not_grumpy[0] = 0;

for (int len = 1; len <= size; len++) {
int s = 0;
if (grumpy[len-1] == 0)
s = customers[len-1];

satisfied[len] = satisfied[len-1] + s;
satisfied_not_grumpy[len] = satisfied_not_grumpy[len-1] + customers[len-1];
}

int max_satisfied = 0;

for (int i = 0; i <= size - X; i++) {
int part0 = satisfied[i];
int part1 = satisfied_not_grumpy[i+X] - satisfied_not_grumpy[i];
int part2 = satisfied[size] - satisfied[i+X];

max_satisfied = max(max_satisfied, part0 + part1 + part2);
}

return max_satisfied;
}
};