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

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Starter code: class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
        

Solutions:
class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		(window, max_window) = (0, 0)
		for i in range(X):
			if grumpy[i]:
				window += customers[i]
		max_window = window
		for i in range(X, len(grumpy)):
			if grumpy[i - X]:
				window -= customers[i - X]
			if grumpy[i]:
				window += customers[i]
			if window > max_window:
				max_window = window
		sum = 0
		for i in range(len(grumpy)):
			if grumpy[i] == 0:
				sum += customers[i]
		return sum + max_window


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		ans = 0
		cust = 0
		for i in range(len(customers)):
			if grumpy[i] == 0:
				cust += customers[i]
				customers[i] = 0
		cur = 0
		best = 0
		for (i, c) in enumerate(customers):
			cur += c
			if i >= X:
				cur -= customers[i - X]
			best = max(best, cur)
		return cust + best


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		wn = min(len(customers), X)
		print(('wn', wn))
		wList = [0] * len(customers)
		for i in range(len(customers)):
			if grumpy[i]:
				wList[i] = customers[i]
			else:
				wList[i] = 0
		print(('list', wList))
		mwsum = sum(wList[0:wn])
		nws = mwsum
		print(mwsum)
		for j in range(wn, len(wList)):
			nws = nws - wList[j - wn] + wList[j] if wn > 1 else wList[j]
			mwsum = max(mwsum, nws)
			print(nws)
		for i in range(len(customers)):
			if grumpy[i] == 0:
				mwsum += customers[i]
		return mwsum


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		no_tech = [0] * len(customers)
		tech = [0] * len(customers)
		if len(customers) <= X:
			return sum(customers)
		if not grumpy[0]:
			no_tech[0] = customers[0]
		tech[0] = customers[0]
		for i in range(1, len(customers)):
			if grumpy[i]:
				no_tech[i] = no_tech[i - 1]
				tech[i] = max(sum(customers[max(0, i - X + 1):i + 1]) + no_tech[i - X], tech[i - 1], no_tech[i])
			else:
				no_tech[i] = no_tech[i - 1] + customers[i]
				tech[i] = tech[i - 1] + customers[i]
		return tech[-1]


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		base = sum((c for (c, g) in zip(customers, grumpy) if g == 0))
		ncus = [c if g == 1 else 0 for (c, g) in zip(customers, grumpy)]
		length = len(customers)
		return base + max((sum(ncus[i:i + X]) for i in range(0, length - X + 1)))


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		n = len(customers)
		res = 0
		for k in range(len(customers)):
			if grumpy[k] == 0:
				res = res + customers[k]
		diff = []
		for j in range(len(customers)):
			diff.append(customers[j] * grumpy[j])
		tem = 0
		for x in range(n - X + 1):
			tem = max(tem, sum(diff[x:x + X]))
		return res + tem


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		gc = []
		l = len(customers)
		for i in range(l):
			gc.append(customers[i] * grumpy[i])
		ms = 0
		mi = -1
		for i in range(l - X + 1):
			s = sum(gc[i:i + X])
			if s > ms:
				ms = s
				mi = i
		allowed = range(mi, mi + X)
		ans = 0
		for i in range(l):
			if grumpy[i] == 0 or i in allowed:
				ans += customers[i]
		return ans


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		base_count = 0
		bonus_array = []
		for (i, j) in zip(customers, grumpy):
			if j == 0:
				base_count += i
			bonus_array.append(i * j)
		bonus = 0
		for i in range(len(customers) - X + 1):
			tmp_bonus = 0
			tmp_bonus = sum(bonus_array[i:i + X])
			bonus = max(bonus, tmp_bonus)
		return base_count + bonus


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		if X > len(customers):
			return sum(customers)
		sum1 = [customers[0]]
		sum2 = []
		if grumpy[0] == 0:
			sum2.append(customers[0])
		else:
			sum2.append(0)
		for i in range(1, len(customers)):
			sum1.append(sum1[-1] + customers[i])
			if grumpy[i] == 0:
				sum2.append(sum2[-1] + customers[i])
			else:
				sum2.append(sum2[-1])
		maxi = sum1[X - 1] + (sum2[-1] - sum2[X - 1])
		for i in range(1, len(customers) - X + 1):
			if sum1[i + X - 1] - sum1[i - 1] + (sum2[-1] - sum2[i + X - 1] + sum2[i - 1]) > maxi:
				maxi = sum1[i + X - 1] - sum1[i - 1] + (sum2[-1] - sum2[i + X - 1] + sum2[i - 1])
		print(sum1, sum2)
		return maxi


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		inital_sum = 0
		tmp_sum = 0
		res_sum = 0
		length = len(customers)
		for i in range(0, len(customers)):
			if grumpy[i] == 0:
				inital_sum += customers[i]
		tmp_sum = inital_sum
		for j in range(0, X):
			if grumpy[j] == 1:
				tmp_sum = tmp_sum + customers[j]
		res_sum = max(tmp_sum, res_sum)
		k = 1
		while k + X - 1 < length:
			if grumpy[k - 1] == 1:
				tmp_sum = tmp_sum - customers[k - 1]
			if grumpy[k + X - 1] == 1:
				tmp_sum = tmp_sum + customers[k + X - 1]
			k += 1
			res_sum = max(tmp_sum, res_sum)
		return res_sum


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		totalCusts = 0
		for (idx, custs) in enumerate(customers):
			if grumpy[idx] == 0:
				totalCusts += customers[idx]
				customers[idx] = 0
		rollingSum = 0
		maxSum = 0
		for (i, n) in enumerate(customers):
			rollingSum += n
			if i - X >= 0:
				rollingSum -= customers[i - X]
			maxSum = max(maxSum, rollingSum)
		return maxSum + totalCusts


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		curr_sum = sum([i * abs(j - 1) for (i, j) in zip(customers, grumpy)])
		max_sum = curr_sum
		for i in range(X):
			curr_sum += customers[i] * grumpy[i]
			max_sum = max(max_sum, curr_sum)
		for i in range(1, len(customers) - X + 1):
			max_sum = max(max_sum, curr_sum)
			curr_sum -= customers[i - 1] * grumpy[i - 1]
			curr_sum += customers[i + X - 1] * grumpy[i + X - 1]
		return max(max_sum, curr_sum)


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		i = win_of_make_satisfied = satisfied = max_make_satisfied = 0
		for (c, g) in zip(customers, grumpy):
			satisfied += (1 - g) * c
			win_of_make_satisfied += g * c
			if i >= X:
				win_of_make_satisfied -= grumpy[i - X] * customers[i - X]
			max_make_satisfied = max(win_of_make_satisfied, max_make_satisfied)
			i += 1
		return satisfied + max_make_satisfied


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		satisfiedCustomers = 0
		for i in range(len(customers)):
			if grumpy[i] == 0:
				satisfiedCustomers += customers[i]
				customers[i] = 0
		i = 0
		unsatisfiedWindow = 0
		while i < X:
			unsatisfiedWindow += customers[i]
			i += 1
		maxUnsatisfiedWindow = unsatisfiedWindow
		while i < len(customers):
			unsatisfiedWindow -= customers[i - X]
			unsatisfiedWindow += customers[i]
			maxUnsatisfiedWindow = max(maxUnsatisfiedWindow, unsatisfiedWindow)
			i += 1
		return satisfiedCustomers + maxUnsatisfiedWindow


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		max_satisfaction = sum(customers)
		actual_satisfaction = sum((int(not g) * s for (g, s) in zip(grumpy, customers)))
		max_s_x = sum(customers[:X])
		actual_s_x = sum((int(not g) * s for (g, s) in zip(grumpy[:X], customers[:X])))
		ans = actual_satisfaction - actual_s_x + max_s_x
		for i in range(X, len(customers)):
			max_s_x += customers[i] - customers[i - X]
			actual_s_x += customers[i] * int(not grumpy[i]) - customers[i - X] * int(not grumpy[i - X])
			ans = max(ans, actual_satisfaction - actual_s_x + max_s_x)
		return ans


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		mp = lp = sum((customers[i] for i in range(X) if grumpy[i]))
		mi = 0
		for i in range(1, len(grumpy) - X + 1):
			n = customers[i + X - 1] if grumpy[i + X - 1] else 0
			o = customers[i - 1] if grumpy[i - 1] else 0
			lp += n - o
			if lp > mp:
				mp = lp
				mi = i
		res = sum([customers[i] for i in range(len(grumpy)) if not grumpy[i]])
		return res + mp


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		tmpCustomers = customers.copy()
		totalSatisfied = 0
		for i in range(len(grumpy)):
			if grumpy[i] == 0:
				totalSatisfied += tmpCustomers[i]
				tmpCustomers[i] = 0
		window = 0
		best = 0
		for i in range(len(tmpCustomers)):
			window += tmpCustomers[i]
			if i >= X:
				window -= tmpCustomers[i - X]
			best = max(window, best)
		return totalSatisfied + best


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		(grumpy, grum_sum, cus_sum) = ([i ^ 1 for i in grumpy], [0] * len(customers), [0] * len(customers))
		grumpy_customers = [customers[i] * grumpy[i] for i in range(len(customers))]
		for (i, n) in enumerate(customers):
			cus_sum[i] = n + (cus_sum[i - 1] if i > 0 else 0)
		for (i, n) in enumerate(grumpy_customers):
			grum_sum[i] = n + (grum_sum[i - 1] if i > 0 else 0)
		return max(((grum_sum[i - 1] if i > 0 else 0) + cus_sum[i + X - 1] - (cus_sum[i - 1] if i > 0 else 0) + grum_sum[len(customers) - 1] - grum_sum[i + X - 1] for i in range(0, len(customers) - X + 1)))


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		if X == len(customers):
			return sum(customers)
		sum_not_grumpy = sum(customers[:X])
		sum_normal = sum([x * (1 - y) for (x, y) in zip(customers, grumpy)][X:])
		max_customers = sum_not_grumpy + sum_normal
		for i in range(1, len(customers) - X + 1):
			sum_not_grumpy -= customers[i - 1]
			sum_not_grumpy += customers[i + X - 1]
			sum_normal += customers[i - 1] * (1 - grumpy[i - 1])
			sum_normal -= customers[i + X - 1] * (1 - grumpy[i + X - 1])
			max_customers = max(max_customers, sum_not_grumpy + sum_normal)
		return max_customers


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		satisfied = 0
		n = len(customers)
		grumpySum = 0
		for i in range(X):
			satisfied += customers[i] if grumpy[i] == 0 else 0
			saved = customers[i] if grumpy[i] == 1 else 0
			grumpySum += saved
		noGrump = grumpySum
		for i in range(X, n):
			satisfied += customers[i] if not grumpy[i] else 0
			saved = customers[i] if grumpy[i] else 0
			abandon = customers[i - X] if grumpy[i - X] else 0
			grumpySum = grumpySum + saved - abandon
			noGrump = max(noGrump, grumpySum)
		return satisfied + noGrump


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		gain = 0
		for i in range(X):
			if grumpy[i]:
				gain += customers[i]
		max_gain = gain
		for i in range(X, len(customers)):
			gain = gain + customers[i] * grumpy[i] - customers[i - X] * grumpy[i - X]
			max_gain = max(max_gain, gain)
		statify = 0
		for i in range(len(customers)):
			statify += customers[i] * (1 - grumpy[i])
		return statify + max_gain


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		(n, window_sum) = (len(customers), 0)
		for i in range(n):
			if i < X:
				window_sum += customers[i]
			else:
				window_sum += (1 - grumpy[i]) * customers[i]
		result = window_sum
		(left, right) = (0, X)
		while right < n:
			if grumpy[right] == 1:
				window_sum += customers[right]
			if grumpy[left] == 1:
				window_sum -= customers[left]
			result = max(result, window_sum)
			left += 1
			right += 1
		return result


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		satisfy = sum((cust for (cust, grump) in zip(customers, grumpy) if grump == 0))
		max_extra = extra = sum((cust for (cust, grump) in zip(customers[:X], grumpy[:X]) if grump == 1))
		(start, end) = (0, X)
		n = len(customers)
		while end < n:
			extra += grumpy[end] * customers[end]
			extra -= grumpy[start] * customers[start]
			max_extra = max(max_extra, extra)
			start += 1
			end += 1
		return satisfy + max_extra


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		n = len(customers)
		cnt = 0
		acc = [0]
		for i in range(n):
			if grumpy[i]:
				acc.append(acc[-1] + customers[i])
			else:
				acc.append(acc[-1])
				cnt += customers[i]
		ans = cnt
		for i in range(n - X + 1):
			ans = max(ans, cnt + acc[i + X] - acc[i])
		return ans


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		ans = 0
		L = len(grumpy)
		if X >= L:
			return sum(customers)
		for i in range(L):
			if grumpy[i] == 0:
				ans += customers[i]
		res = cur_sum = 0
		for end in range(X):
			if grumpy[end] == 1:
				cur_sum += customers[end]
		res = cur_sum
		for end in range(X, L):
			if grumpy[end] == 1:
				cur_sum += customers[end]
			if grumpy[end - X] == 1:
				cur_sum -= customers[end - X]
			res = max(res, cur_sum)
		return ans + res


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		already_happy = sum((c for (c, h) in zip(customers, grumpy) if not h))
		running = sum((c for (c, h) in zip(customers[:X], grumpy[:X]) if h))
		max_happy = running
		for i in range(1, len(customers) - X + 1):
			if grumpy[i - 1] == 1:
				running -= customers[i - 1]
			if grumpy[i + X - 1] == 1:
				running += customers[i + X - 1]
			max_happy = max(running, max_happy)
		return max_happy + already_happy


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		L = len(grumpy)
		if L == X:
			return sum(customers)
		grummpyCustomer = [0 if grumpy[i] == 1 else customers[i] for i in range(L)]
		for i in range(1, L):
			customers[i] += customers[i - 1]
		for i in range(1, L):
			grummpyCustomer[i] += grummpyCustomer[i - 1]
		result = 0
		maxSum = grummpyCustomer[-1]
		for i in range(X, L):
			result = max(result, customers[i] - customers[i - X] + maxSum - grummpyCustomer[i] + grummpyCustomer[i - X])
		for i in reversed(list(range(1, L))):
			customers[i] -= customers[i - 1]
		grummpyCustomer = [0 if grumpy[i] == 1 else customers[i] for i in range(L)]
		for i in reversed(list(range(L - 1))):
			customers[i] += customers[i + 1]
		for i in reversed(list(range(L - 1))):
			grummpyCustomer[i] += grummpyCustomer[i + 1]
		maxSum = grummpyCustomer[0]
		for i in reversed(list(range(L - X))):
			result = max(result, customers[i] - customers[i + X] + maxSum - grummpyCustomer[i] + grummpyCustomer[i + X])
		return result


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], k: int) -> int:
		n = len(customers)
		res = sum([customers[i] * (1 - grumpy[i]) for i in range(n)])
		best_gain = sum([customers[i] * grumpy[i] for i in range(k)])
		gain = best_gain
		for i in range(k, n):
			gain += customers[i] * grumpy[i] - customers[i - k] * grumpy[i - k]
			best_gain = max(gain, best_gain)
		return res + best_gain


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		curr = 0
		max1 = 0
		left = 0
		for i in range(len(customers)):
			if i < X:
				curr += customers[i]
			elif grumpy[i] == 0:
				curr += customers[i]
		max1 = curr
		for i in range(X, len(customers)):
			if grumpy[i] == 1:
				curr += customers[i]
			if grumpy[left] == 1:
				curr -= customers[left]
			left += 1
			max1 = max(max1, curr)
		return max1


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		if X == len(customers):
			return sum(customers)
		for i in range(len(grumpy)):
			grumpy[i] = 0 if grumpy[i] == 1 else 1
		mults = [x * y for (x, y) in zip(customers, grumpy)]
		sum_not_grumpy = sum(customers[:X])
		not_grumpy = [sum_not_grumpy]
		for i in range(1, len(customers) - X + 1):
			sum_not_grumpy -= customers[i - 1]
			sum_not_grumpy += customers[i + X - 1]
			not_grumpy.append(sum_not_grumpy)
		sum_normal = sum(mults[X:])
		normal_custs = [sum_normal]
		for i in range(1, len(mults) - X + 1):
			sum_normal += mults[i - 1]
			sum_normal -= mults[i + X - 1]
			normal_custs.append(sum_normal)
		print(not_grumpy)
		print(normal_custs)
		return max([x + y for (x, y) in zip(not_grumpy, normal_custs)])


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		old = 0
		for i in range(len(customers)):
			if grumpy[i] == 0:
				old += customers[i]
		(l, r, res) = (0, 0, 0)
		while r < len(customers):
			if grumpy[r] == 1:
				old += customers[r]
			if r >= X:
				if grumpy[l] == 1:
					old -= customers[l]
				l += 1
			res = max(res, old)
			r += 1
		return res


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		if len(customers) == X:
			return sum(customers)
		maxLoss = 0
		total = sum([customers[i] * (1 - grumpy[i]) for i in range(len(grumpy))])
		print(total)
		loss = sum([grumpy[i] * customers[i] for i in range(X)])
		maxLoss = loss
		for i in range(X, len(customers)):
			loss += grumpy[i] * customers[i]
			loss -= grumpy[i - X] * customers[i - X]
			maxLoss = max(maxLoss, loss)
		total += maxLoss
		return total


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		if not customers:
			return 0
		can_be_always_happy = X == len(customers)
		customers_lost = [0] * (len(customers) + 1)
		total_customers_lost = 0
		total_satisfied = 0
		for (idx, customer) in enumerate(customers):
			if grumpy[idx] == 1 and (not can_be_always_happy):
				total_customers_lost += customers[idx]
			else:
				total_satisfied += customers[idx]
			customers_lost[idx + 1] = total_customers_lost
		max_gain = 0
		for i in range(X, len(customers_lost)):
			gain = customers_lost[i] - customers_lost[i - X]
			max_gain = max(gain, max_gain)
		return total_satisfied + max_gain


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		saved = 0
		max_saved = 0
		sumTotal = 0
		for (i, value) in enumerate(customers):
			if i - X >= 0 and grumpy[i - X]:
				saved -= customers[i - X]
			if grumpy[i]:
				saved += value
			else:
				sumTotal += value
			max_saved = max(max_saved, saved)
			print((saved, max_saved))
		return sumTotal + max_saved


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		to_ret = sum([c for (c, g) in zip(customers, grumpy) if g == 0])
		mt = mf = sum([c for (c, g) in zip(customers[:X], grumpy[:X]) if g == 1])
		for t in range(X, len(customers)):
			if grumpy[t] == 1:
				mt += customers[t]
			if grumpy[t - X] == 1:
				mt -= customers[t - X]
			mf = max(mf, mt)
		return to_ret + mf


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		satisfiedCount = 0
		for i in range(len(customers)):
			if grumpy[i] == 0:
				satisfiedCount += customers[i]
				customers[i] = 0
		maxPotentialCount = 0
		val = 0
		for i in range(len(customers)):
			if i < X:
				val += customers[i]
				continue
			maxPotentialCount = max(maxPotentialCount, val)
			val -= customers[i - X]
			val += customers[i]
		maxPotentialCount = max(maxPotentialCount, val)
		return satisfiedCount + maxPotentialCount


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		(lb, ub) = (0, X - 1)
		total = sum([customers[i] * (1 - grumpy[i]) for i in range(len(customers))])
		saved = 0
		for i in range(X):
			if grumpy[i]:
				saved += customers[i]
		ans = total + saved
		while ub + 1 < len(grumpy):
			(lb, ub) = (lb + 1, ub + 1)
			if grumpy[lb - 1]:
				saved -= customers[lb - 1]
			if grumpy[ub]:
				saved += customers[ub]
			ans = max(ans, total + saved)
		return ans


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		gains = [x if grumpy[i] == 1 else 0 for (i, x) in enumerate(customers)]
		fact = [x if grumpy[i] == 0 else 0 for (i, x) in enumerate(customers)]
		if X > len(gains):
			return sum(customers)
		current_sum = sum(gains[:X])
		max_gain = current_sum
		for i in range(1, len(gains) - X + 1):
			current_sum = current_sum - gains[i - 1] + gains[i + X - 1]
			max_gain = max(max_gain, current_sum)
		return sum(fact) + max_gain


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		n = len(grumpy)
		if X >= n:
			return sum(customers)
		init = sum([customers[i] * (1 - grumpy[i]) for i in range(n)])
		for j in range(X):
			if grumpy[j] == 1:
				init += customers[j]
		max_l = init
		temp = init
		for i in range(1, n - X + 1):
			temp -= grumpy[i - 1] * customers[i - 1]
			temp += grumpy[i + X - 1] * customers[i + X - 1]
			max_l = max(max_l, temp)
		return max_l


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		initial = sum((num for (day, num) in enumerate(customers) if grumpy[day] == 0))
		curr_tricked = 0
		tricked = 0
		for (ind, num) in enumerate(customers):
			if ind >= X and grumpy[ind - X] == 1:
				curr_tricked -= customers[ind - X]
			if grumpy[ind] == 1:
				curr_tricked += customers[ind]
			tricked = max(tricked, curr_tricked)
		return initial + tricked


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		t = 0
		for i in range(len(grumpy)):
			if grumpy[i] == 0:
				t += customers[i]
				customers[i] = 0
		n = sum(customers[:X])
		m = n
		for i in range(1, len(customers) - X + 1):
			m = m + customers[i + X - 1] - customers[i - 1]
			n = max(m, n)
		return n + t


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		satisfied = 0
		for i in range(len(grumpy)):
			if grumpy[i] == 0:
				satisfied += customers[i]
		windowMax = 0
		curr = 0
		for i in range(len(customers)):
			curr += grumpy[i] * customers[i]
			if i >= X:
				curr -= grumpy[i - X] * customers[i - X]
			windowMax = max(windowMax, curr)
		return satisfied + windowMax


import numpy as np

class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		satisfiedCustomer = 0
		for i in range(len(customers)):
			if not grumpy[i]:
				satisfiedCustomer += customers[i]
		window = 0
		for i in range(X):
			if grumpy[i] == 1:
				window += customers[i]
		res = window
		for i in range(1, len(customers) - X + 1):
			last = i - 1
			if grumpy[last] == 1:
				window -= customers[last]
			nextIdx = i + X - 1
			if grumpy[nextIdx] == 1:
				window += customers[nextIdx]
			res = max(res, window)
		return res + satisfiedCustomer


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		total = sum((c for (i, c) in enumerate(customers) if grumpy[i] == 0))
		add = sum((c for (i, c) in enumerate(customers[:X]) if grumpy[i] == 1))
		res = total + add
		for i in range(X, len(customers)):
			if grumpy[i] == 1:
				add += customers[i]
			if grumpy[i - X] == 1:
				add -= customers[i - X]
			res = max(res, total + add)
		return res


class Solution:

	def maxSatisfied(self, A: List[int], G: List[int], X: int) -> int:
		res = 0
		s = 0
		ws = 0
		left = []
		for i in range(len(A)):
			(c, g) = (A[i], G[i])
			s += (1 - g) * c
			ws += g * c
			if i >= X:
				ws -= A[i - X] * G[i - X]
			res = max(res, ws)
		return res + s


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		N = len(grumpy)
		already_happy = sum((customers[i] for i in range(N) if not grumpy[i]))
		window = sum((customers[i] for i in range(X) if grumpy[i]))
		max_bonus = window
		for r in range(X, N):
			window -= customers[r - X] if grumpy[r - X] else 0
			window += customers[r] if grumpy[r] else 0
			max_bonus = max(max_bonus, window)
		return already_happy + max_bonus


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], window_size: int) -> int:
		already_satisfied = 0
		for index in range(len(customers)):
			if grumpy[index] == 0:
				already_satisfied += customers[index]
				customers[index] = 0
		best_satisfied = 0
		satisfied = 0
		for (index, customer) in enumerate(customers):
			satisfied += customer
			if index >= window_size:
				satisfied -= customers[index - window_size]
			best_satisfied = max(best_satisfied, satisfied)
		return best_satisfied + already_satisfied


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		disSatisfy = [c * g for (c, g) in zip(customers, grumpy)]
		start = 0
		grumpy_num = 0
		for i in range(X):
			grumpy_num += disSatisfy[i]
		remaining = grumpy_num
		for j in range(X, len(customers)):
			remaining = remaining - disSatisfy[j - X] + disSatisfy[j]
			if remaining > grumpy_num:
				grumpy_num = remaining
				start = j - X + 1
		for k in range(start, start + X):
			grumpy[k] = 0
		return sum([c if g == 0 else 0 for (c, g) in zip(customers, grumpy)])


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		n = len(customers)
		start = 0
		curSatisfaction = sum((customers[i] for i in range(n) if grumpy[i] == 0))
		maxSatisfaction = 0
		for end in range(len(customers)):
			if grumpy[end] == 1:
				curSatisfaction += customers[end]
			if end - start + 1 > X:
				if grumpy[start] == 1:
					curSatisfaction -= customers[start]
				start += 1
			maxSatisfaction = max(maxSatisfaction, curSatisfaction)
		return maxSatisfaction


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		start = 0
		end = X
		ans = 0
		for i in range(len(grumpy)):
			if grumpy[i] == 0:
				ans += customers[i]
		t = 0
		for i in range(X):
			if grumpy[i] == 1:
				t += customers[i]
		maxs = 0
		while end < len(grumpy) + 1:
			if t > maxs:
				maxs = t
			if end == len(grumpy):
				break
			if grumpy[start] == 1:
				t -= customers[start]
			if grumpy[end] == 1:
				t += customers[end]
			start += 1
			end += 1
		return ans + maxs


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		total = 0
		for i in range(len(customers)):
			total += (1 - grumpy[i]) * customers[i]
			grumpy[i] *= customers[i]
		maxsum = 0
		for i in range(X):
			maxsum += grumpy[i]
		cur = maxsum
		for j in range(X, len(grumpy)):
			i = j - X
			cur += grumpy[j]
			cur -= grumpy[i]
			maxsum = max(maxsum, cur)
		return total + maxsum


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		n = len(customers)
		sum_cus = sum(customers)
		for i in range(n):
			customers[i] *= grumpy[i]
		window = 0
		max_secret_satisfied = -math.inf
		(left, right) = (0, 0)
		while right < n:
			window += customers[right]
			right += 1
			while right - left >= X:
				max_secret_satisfied = max(max_secret_satisfied, window)
				window -= customers[left]
				left += 1
		return sum_cus - (sum(customers) - max_secret_satisfied)


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		happy_owner_cust = 0
		for pos in range(len(customers)):
			if grumpy[pos] == 0:
				happy_owner_cust += customers[pos]
				customers[pos] = 0
		calming_owner_cust = 0
		best_calmed_cust = 0
		for end in range(len(customers)):
			calming_owner_cust += customers[end]
			if end >= X:
				calming_owner_cust -= customers[end - X]
			best_calmed_cust = max(best_calmed_cust, calming_owner_cust)
		return happy_owner_cust + best_calmed_cust

class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		always_happy = 0
		for pos in range(len(customers)):
			if grumpy[pos] == 0:
				always_happy += customers[pos]
				customers[pos] = 0
		happy_use = 0
		cur_happy_customers = 0
		for pos in range(len(customers)):
			cur_happy_customers += customers[pos]
			if pos >= X:
				cur_happy_customers -= customers[pos - X]
			happy_use = max(happy_use, cur_happy_customers)
		return always_happy + happy_use


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		if len(customers) <= X:
			return sum(customers)
		satisfied_customers = 0
		current_unsatisfied_customers = 0
		max_unsatisfied_customers = 0
		for i in range(len(customers)):
			if i >= X and grumpy[i - X] == 1:
				current_unsatisfied_customers -= customers[i - X]
			if grumpy[i] == 0:
				satisfied_customers += customers[i]
			else:
				current_unsatisfied_customers += customers[i]
			max_unsatisfied_customers = max(max_unsatisfied_customers, current_unsatisfied_customers)
		return satisfied_customers + max_unsatisfied_customers


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		satisfied = 0
		for i in range(len(customers)):
			satisfied += customers[i] * (grumpy[i] == 0)
		p = X
		best_imp = sum([customers[i] for i in range(p) if grumpy[i] == 1])
		imp = best_imp
		while p < len(grumpy):
			if grumpy[p] == 1:
				imp += customers[p]
			if grumpy[p - X] == 1:
				imp -= customers[p - X]
			if imp > best_imp:
				best_imp = imp
			p += 1
		return satisfied + best_imp


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		curr_running_delta = 0
		max_delta = (-2 ** 31, None)
		for i in range(len(customers)):
			curr_running_delta += customers[i] * grumpy[i]
			if i >= X - 1:
				if curr_running_delta > max_delta[0]:
					max_delta = (curr_running_delta, i)
				if grumpy[i - (X - 1)] == 1:
					curr_running_delta -= customers[i - (X - 1)]
		max_satisfied = 0
		for i in range(len(customers)):
			if max_delta[1] - (X - 1) <= i <= max_delta[1] or grumpy[i] == 0:
				max_satisfied += customers[i]
		return max_satisfied


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		without_x = 0
		for (i, b) in enumerate(grumpy):
			if not b:
				without_x += customers[i]
		with_x = [0] * len(customers)
		extra = 0
		for (i, b) in enumerate(grumpy[:X]):
			if b:
				extra += customers[i]
		with_x[0] += extra
		for i in range(len(grumpy)):
			if i + X >= len(grumpy):
				break
			extra -= 0 if not grumpy[i] else customers[i]
			extra += 0 if not grumpy[i + X] else customers[i + X]
			with_x[i + 1] += extra
		return max(with_x) + without_x


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		already_satisfied = 0
		for i in range(len(grumpy)):
			if grumpy[i] == 0:
				already_satisfied += customers[i]
				customers[i] = 0
		best_we_can_make_satisfied = 0
		current_satisfied = 0
		for (i, customers_at_time) in enumerate(customers):
			current_satisfied += customers_at_time
			if i >= X:
				current_satisfied -= customers[i - X]
			best_we_can_make_satisfied = max(best_we_can_make_satisfied, current_satisfied)
		return already_satisfied + best_we_can_make_satisfied


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		zeroTotal = 0
		for i in range(len(customers)):
			if grumpy[i] == 0:
				zeroTotal += customers[i]
		q = deque()
		oneTotal = 0
		largest = 0
		for i in range(len(customers)):
			if grumpy[i] == 1:
				while q and i - q[0][1] >= X:
					oneTotal -= q.popleft()[0]
				q.append((customers[i], i))
				oneTotal += customers[i]
				largest = max(largest, oneTotal)
		return zeroTotal + largest


class Solution:

	def maxSatisfied(self, c: List[int], g: List[int], X: int) -> int:
		arr = [0]
		n = len(g)
		for i in range(n):
			arr.append(arr[-1] + (1 - g[i]) * c[i])
		c = [0] + c
		for i in range(n):
			c[i + 1] = c[i] + c[i + 1]
		m = -1
		for i in range(X, n + 1):
			m = max(m, c[i] - c[i - X] - arr[i] + arr[i - X])
		print((arr, c, m))
		return arr[-1] + m


import numpy as np

class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		customers = np.array(customers)
		grumpy = np.array(grumpy)
		total_customers = np.sum(customers)
		grumpy_array = customers * grumpy
		secret_array = np.convolve(grumpy_array, np.ones(X, dtype=int), 'valid')
		index = np.where(secret_array == secret_array.max())[0][0]
		grumpy_array[index:index + X] = 0
		satisfied_customers = total_customers - grumpy_array.sum()
		return satisfied_customers


import numpy as np

class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		customers = np.array(customers)
		grumpy = 1 - np.array(grumpy)
		l = []
		m = sum(customers * grumpy)
		for i in range(len(customers) - X + 1):
			if i == 0:
				best_case = sum(customers[0:X])
				diff = sum(grumpy[0:X] * customers[0:X])
				grump_days = best_case - diff
				l.append(grump_days)
			else:
				best_case = best_case - customers[i - 1] + customers[i + X - 1]
				diff = diff - grumpy[i - 1] * customers[i - 1] + grumpy[i + X - 1] * customers[i + X - 1]
				grump_days = best_case - diff
				l.append(grump_days)
		return max(l) + m


import itertools as it

class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		self.customers = customers
		self.grumpy = grumpy
		self.n = len(customers)
		self.cumulative_customers = list(it.accumulate(customers, initial=0))
		self.technique_length = X
		return self.satisfy(0, 1)

	@lru_cache(None)
	def satisfy(self, index: int, secret_technique: int) -> int:
		if index >= self.n:
			return 0
		satisfaction = self.customers[index] if self.grumpy[index] == 0 else 0
		if secret_technique == 0:
			return satisfaction + self.satisfy(index + 1, 0)
		ans = max(satisfaction + self.satisfy(index + 1, secret_technique), self.cumulative_customers[min(self.n, index + self.technique_length)] - self.cumulative_customers[index] + self.satisfy(index + self.technique_length, secret_technique - 1))
		return ans


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		window = [0] * X
		for a in range(X):
			if grumpy[a] == 1:
				window[a] += customers[a]
		mySum = 0
		maxAdded = sum(window)
		right = X
		for i in range(len(customers)):
			if i + X < len(customers):
				window.pop(0)
				window.append(customers[i + X] if grumpy[i + X] == 1 else 0)
				if sum(window) > maxAdded:
					maxAdded = sum(window)
			if grumpy[i] == 0:
				mySum += customers[i]
		return mySum + maxAdded


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		s = 0
		for i in range(0, len(customers)):
			if grumpy[i] == 0:
				s += customers[i]
				customers[i] = 0
		tmp = [sum(customers[:X])]
		for i in range(X, len(customers)):
			tmp = tmp + [tmp[-1] + customers[i] - customers[i - X]]
		return max(tmp) + s


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		satisfied = []
		satisfied_before = 0
		satisfied_after = sum([x[0] for x in zip(customers[X:], grumpy[X:]) if not x[1]])
		for i in range(len(customers) - X + 1):
			satisfied.append(satisfied_before + sum(customers[i:i + X]) + satisfied_after)
			if not grumpy[i]:
				satisfied_before += customers[i]
			if i + X < len(customers) and (not grumpy[i + X]):
				satisfied_after -= customers[i + X]
		return max(satisfied)


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		N = len(customers)
		satisfy = 0
		unsatisfied = []
		max_value = 0
		if not customers:
			return []
		elif not grumpy or N == 1:
			return sum(customers)
		for i in range(N):
			if grumpy[i] == 0:
				satisfy += customers[i]
				unsatisfied.append(0)
			else:
				unsatisfied.append(customers[i])
		for j in range(N - X + 1):
			sum1 = sum(unsatisfied[j:j + X])
			max_value = max(max_value, sum1)
		return satisfy + max_value


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		sums = 0
		maxs = 0
		for i in range(len(customers)):
			sums += customers[i]
			if grumpy[i] == 1:
				grumpy[i] = customers[i]
				sums -= grumpy[i]
		for i in range(len(grumpy) - X + 1):
			maxs = max(sum(grumpy[i:i + X]), maxs)
		return sums + maxs


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		orig_satisfied_list = [customers[i] * (1 - grumpy[i]) for i in range(len(customers))]
		orig_satisfied = sum(orig_satisfied_list)
		grumpy_satisfied_list = [customers[i] - orig_satisfied_list[i] for i in range(len(customers))]
		diff_list = [max(0, grumpy_satisfied_list[i] - orig_satisfied_list[i]) for i in range(len(customers))]
		return orig_satisfied + max([sum(diff_list[i:i + X]) for i in range(len(customers) - X + 1)])


class Solution:

	def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
		satisfaction = 0
		unsatisfied = []
		for i in range(len(customers)):
			if grumpy[i] == 1:
				unsatisfied.append(customers[i])
			else:
				satisfaction += customers[i]
				unsatisfied.append(0)
		max_sum = sum(unsatisfied[:X])
		for i in range(X, len(unsatisfied) + 1):
			max_sum = max(max_sum, sum(unsatisfied[i - X:i]))
		satisfaction += max_sum
		return satisfaction