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

Difficulty: interview

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:
        # feel like its sliding window max
        
        window, max_window = 0, 0
        
        # init first window
        for i in range(X):
            if grumpy[i]: window += customers[i]
        max_window = window
        
        # Sliding 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]
                
            # print(customers[max(0, (i-X) + 1) : i+1])
            
            # print(tech)
            # print(no_tech)
            # print()
                
        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:
        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])
            
        # print(gc)
        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]
                
        # print(ans)
        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
        
        # first one, check all
        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:
#     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
  
  
    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:]) #sum(mults[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:
        # sliding window of possible grumping times
        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)
        if n == 0:
            return 0
        
        running_sum = 0
        
        for i in range(n):
            if i < X:
                running_sum += customers[i]
            else:
                running_sum += customers[i] * (1-grumpy[i])
                
        left, right = 0, X
        ans = running_sum
        
        while right < n:
            if grumpy[right] == 1:
                running_sum += customers[right]
            right += 1
            
            if grumpy[left] == 1:
                running_sum -= customers[left]
            
            left += 1
        
            ans = max(ans, running_sum)
            
        return ans

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:
        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
        print (tmp_sum)
        for j in range(0, X):
            if grumpy[j] == 1:
                tmp_sum = tmp_sum + customers[j]
        print (tmp_sum)
        res_sum = max(tmp_sum, res_sum)
        print (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:
        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)
        # print(L,X)
        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])
            # print(result)
            
    
        for i in reversed(list(range(1,L))):
            customers[i] -= customers[i-1]
        # print(customers)
        
        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))):
            # print(i)
            grummpyCustomer[i] += grummpyCustomer[i+1]
        
        # print(customers[0] - customers[0+X] + grummpyCustomer[0+X])
        maxSum = grummpyCustomer[0]
        for i in reversed(list(range(L-X))):
            # print(i,'ok')
            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)])    # the customers you can obtain while non grumpy
        best_gain=sum([customers[i]*grumpy[i] for i in range(k)])    # first window
        gain=best_gain
        for i in range(k,n):
            gain+=customers[i]*grumpy[i]-customers[i-k]*grumpy[i-k]  # add new, kick out old
            best_gain=max(gain,best_gain)    
        return res+best_gain

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
        print(max_satisfaction, actual_satisfaction)
        print('sssssssss')
        for i in range(X, len(customers)):
            print(max_s_x, actual_s_x, customers[i], customers[i - X])
            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:
        curr = 0
        max1 = 0
        left =0
        for i in range(len(customers)):
            if i <X:
                curr += customers[i]
            else:
                if 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:
        # we want to find the biggest loss of satisfaction in a X-hr period throughout the day.
        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:
        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])
        sum_normal = sum(mults[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 += mults[i-1]
            sum_normal -= mults[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:
        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] 
        sum_normal = sum(mults[X:])
        #normal_custs = [sum_normal]
        
        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 += mults[i-1]
            sum_normal -= mults[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:
        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))
            # print(saved, max_saved, sumTotal)
        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:
        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:
        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:
        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[X:],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
        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 = sum(customers) - sum(np.multiply(customers,grumpy))
        
        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
        #print(total, add, res)
        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)
            #print(total, add, res)
        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)
            # print(i,j,s,res)
        return res+s

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:
        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(X)])
        gain=best_gain
        for i in range(X,n):
            gain+=customers[i]*grumpy[i]-customers[i-X]*grumpy[i-X]
            best_gain=max(best_gain,gain)
        return res+best_gain

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] 
        sum_normal = sum(mults[X:])
        normal_custs = [sum_normal]
        
        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 += mults[i-1]
            sum_normal -= mults[i+X-1]
            normal_custs.append(sum_normal)
        
        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:
        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:
       
        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:
        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)
        #print(maxsum)
        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 means happy customer as well 
        happy_owner_cust = 0 
        
        for pos in range(len(customers)):
            if grumpy[pos] == 0: #happy owner 
                happy_owner_cust += customers[pos]
                customers[pos] = 0 
        
        
        #then build upon using the grumpy owner power. 
        
        calming_owner_cust = 0 
        best_calmed_cust = 0 
        
        for end in range(len(customers)): 
            calming_owner_cust += customers[end]
  
            
            
            if end >= X: #subtract out the extra calming technique from the owner 
                calming_owner_cust -= customers[end - X]
                
            best_calmed_cust = max(best_calmed_cust, calming_owner_cust)
            
            
            
            
        return happy_owner_cust + best_calmed_cust
    
# #TRY 8/10/2020 
# class Solution:
#     def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
#         #Input: Customers[i] how many customers enter for that exact minute 
            
#         #Constraint 
#         #owner -> opens store up to customers.len()
#         #Every minute there are customers entering the store. And all those customers leave after the end of the minute 
        
#         #If owner is grumpy on i-th minute grumpy[i] = 1 else grumpy[i] = 0. When the bookstore owner is angry 
#         #The customers of that minute aren't satisfied else if owner isn't grumpy then customers are happy. 
        
#        # Bookstore owner can be NOT angry for X minutes but can use it ONLY once. 
       
#         #WANT: max number of customers that are happy throughout the day. 
        
        
#         minutes_opened = len(customers) 
#         customer_happy_time = 0 
        
#         #Try to basically keep your grumpy minutes down based on the highest number of customers there are. 
        
#         start = 0 
#         end = 0 
#         rush_hour = collections.deque() #this is based on the most amount of customers. 
#         calm_owner = collections.deque()
#         #Our best number of customer being happy will be based on the largest amount of customers
#         #That's our best bet. 
#         while end < minutes_opened: 
#             if customers[end] == 0: #No Customers go in owner can be angry 
#                 end += 1 
#                 continue 
                
#             cur_happy_time += customers[end]
#             if grumpy[end] == 1: #owner angry = customer angry: Just try calming here then. 
                
                
                
#             rush_hour.append(end)

# class Solution():
#     def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
#         m = s = tmp = 0
#         for i in range(len(customers)):
#             if not grumpy[i]: 
#                 s += customers[i]                # sum of satisfied customers
#                 customers[i] = 0 
#             else: tmp += customers[i]            # sum of grumpy customers 
#             if i>=X: tmp -= customers[i-X]       # remove the leftmost element to keep the sliding window with # of X
#             m = max(m, tmp)                      # max # of satisfied grumpy customers with a secret technique
#         return s+m
    
    
# class Solution:
#     def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
#         # Part 1 requires counting how many customers
#         # are already satisfied, and removing them
#         # from the customer list.
#         #These customers are those who didn't have to fight with the owner to be happy.
#         already_satisfied = 0
#         for i in range(len(grumpy)):
#             if grumpy[i] == 0: #He's happy so add the customer. 
#                 already_satisfied += customers[i]
#                 customers[i] = 0 #set you back to zero to not visit you. When doing the offset for the window 
        
#         # Part 2 requires finding the optimal number
#         # of unhappy customers we can make happy.
#         best_we_can_make_satisfied = 0
#         current_satisfied = 0
#         for i, customers_at_time in enumerate(customers):
#             # if customers[i] == 0: CAN'T DO THIS CUZ WE'RE NOT UPDATING THE WINDOW THEN AT THIS POINT (I.E THE START WINDOW)
#             #     continue
#             #Add the customer so far
#             current_satisfied += customers_at_time # Add current to rolling total
#             if i >= X: # We need to remove some from the rolling total #We need to update and try the grumpy intervals to block out owner from 
#                 #Being grumpy so we can add these happy customers but at this point
#                 #There's too much calming power used by owner so we need to remove the beginning window of the current_satisifed. 
#                 current_satisfied -= customers[i - X]
#             best_we_can_make_satisfied = max(best_we_can_make_satisfied, current_satisfied)
        
#         # The answer is the sum of the solutions for the 2 parts.
#         return already_satisfied + best_we_can_make_satisfied
    
    
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:
        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] 
        sum_normal = sum(mults[X:])
        normal_custs = [sum_normal]
        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 += 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:
        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:
        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:
        curr_running_delta = 0
        max_delta = (-2**31, None) # max sum, end idx
        
        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
    
    # time O(n)
    # space O(1)


class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
        # sliding window of possible grumping times
        satisfied = 0
        n = len(customers)
        grumpySum = [0]*(n - X + 1)
        
        for i in range(X):
            satisfied += customers[i] if grumpy[i]==0 else 0
            
            saved = customers[i] if grumpy[i]==1 else 0
            grumpySum[0] += saved

        noGrump = grumpySum[0]
        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[i - X + 1] = grumpySum[i - X] + saved - abandon
            noGrump = max(noGrump, grumpySum[i - X + 1])

        return satisfied + noGrump
       
          


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, 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])
        sum_normal = sum(mults[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]*grumpy[i-1]#mults[i-1] 
            sum_normal -= customers[i+X-1]*grumpy[i+X-1]#mults[i+X-1]
            max_customers = max(max_customers, sum_not_grumpy+sum_normal)

        return max_customers
            


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


class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
        
        
        L = len(grumpy)
        if L == X:
            return sum(customers)
        # print(L,X)
        tempCustomers = customers.copy()
        grummpyCustomer = [0 if grumpy[i] == 1 else customers[i] for i in range(L) ]
        for i in range(1,L):
            tempCustomers[i] += tempCustomers[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, tempCustomers[i] - tempCustomers[i-X] + maxSum - grummpyCustomer[i] +  grummpyCustomer[i-X])
            # print(result)
            
    
        # for i in reversed(range(1,L)):
        #     customers[i] -= customers[i-1]
        # print(customers)
        
        grummpyCustomer = [0 if grumpy[i] == 1 else customers[i] for i in range(L) ]
        
        tempCustomers = customers.copy()
        for i in reversed(list(range(L-1))):
            tempCustomers[i] += tempCustomers[i+1]
        
        for i in reversed(list(range(L-1))):
            # print(i)
            grummpyCustomer[i] += grummpyCustomer[i+1]
        
        # print(customers[0] - customers[0+X] + grummpyCustomer[0+X])
        maxSum = grummpyCustomer[0]
        for i in reversed(list(range(L-X))):
            # print(i,'ok')
            result = max(result, tempCustomers[i] - tempCustomers[i+X] + maxSum - grummpyCustomer[i] +  grummpyCustomer[i+X])
            
        return result


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)
        # if len(grumpy) != self.n:
        #     raise ValueError(f\"Customers {customers} and grumpy {grumpy} arrays must have the same length.\")
        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:
        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:
        
        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

        # print(customers)
        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
        #Base cases
        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))]
        #print(orig_satisfied_list)
        #print(grumpy_satisfied_list)
        #print(diff_list)
        #print([sum(diff_list[i:i+X]) for i in range(len(customers)-X+1)])
        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