Last Updated: 19 Nov, 2020

SHOPKEEPER

Moderate

Solve now

Problem statement

You are the owner of an ice cream parlour that opens for ‘N’ minutes in a day. Every minute, some number of customers enter the store, and each of them leaves after the end of that minute.

During some minutes of the day, you are very short-tempered and when you are short-tempered, the customers of that minute are not satisfied; otherwise, they are satisfied.

You know a secret technique to keep yourself calm for ‘X’ minutes straight. This secret technique can only be used once during the day.

A good shopkeeper doesn't want his customers to be unsatisfied, so you want to find the maximum number of customers that can be satisfied throughout the day.

Input Format :

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains two single space-separated integers ‘N’ and ‘X’, respectively.

The second line of each test case contains ‘N’ single space-separated integers representing the number of customers that enter the bookstore on the i-th minute.

The third line of each test case contains ‘N’ single space-separated integers representing whether you are short-tempered on the i-th minute or not. If the value is 1, then you are short-tempered on that minute, and if it is 0, then you are not.

Output Format :

For each test case, the only line of output will print the maximum number of customers that can be satisfied throughout the day.  

Print the output of each test case in a separate line.

Note :

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 100
1 <= N <= 5000
1 <= X <= N
0 <= customers[i] <= 10^5
0 <= tempered[i] <= 1

Time limit: 1 sec

Solve now

Approaches

01 Approach

We have a simple brute force solution to this problem. First, we will traverse over the ‘customers’ array and calculate the sum of customers when the shopkeeper is calm. These many customers are already satisfied with the shopkeeper, so we will add them directly to our answer.

Then, we will calculate the maximum sum of all subarrays of size ‘X’ when the shopkeeper is short-tempered. This is because we can satisfy all the customers in a subarray of size 'X' when the shopkeeper is short-tempered by using our secret technique.

Finally, we return the sum of both of them.

Solve now

02 Approach

We can improve our previous approach with the help of a sliding window. First, we will traverse over the ‘customers’ array and calculate the sum of customers when the shopkeeper is calm and store it in variable ‘calm’.

Then, we will use the sliding window technique to find the maximum sum of customers when the shopkeeper is short-tempered for each subarray of size ‘X’.

The sliding window of size ‘X’ is maintained while traversing the array/list left to right and including the current element in the window and removing the leftmost element if the size of the window exceeds ‘X’.

Following is the algorithm for this approach:

We store the sum of customers for which the shopkeeper is short-tempered of the first window/subarray of size ‘X’ in ‘currWindowSum’.
We initialise ‘maxWindowSum’ to ‘currWindowsum’’.
We now traverse the rest of the array.
1. We will compute ‘currWindowSum’ by
  1. removing the leftmost element i.e. customers[i-X], if tempered[i-X] = 1.
  2. including the current element i.e. customers[i], if tempered[i] = 1.
2. We set ‘maxWindowSum’ to the maximum of ‘maxWindowSum’ and ‘currWindowSum’.
Finally, we return the sum of ‘maxWindowSum’ and ‘calm’.

Solve now