SHOPKEEPER

Moderate

0/80

Average time to solve is 15m

Contributed by

22 upvotes

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

1
6 2
4 6 1 2 1 1 
0 1 0 1 0 1

Sample output 1 :

Explanation of Sample output 1:

You keep yourself calm for the starting 2 minutes. The maximum number of customers that can be satisfied = 4 + 6 + 1 + 1  = 12.

Sample Input 2 :

Sample output 2 :

7
8

Hint 1

Hint 2

Naively check for each subarray of size ‘X’ to use the secret technique.

Approaches (2)

Approach 1

Approach 2

BRUTE FORCE

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.

Time Complexity

O(N * X), where ‘N’ is the number of minutes for which ice cream parlour is opened, and ‘X’ is the number of minutes for which you can keep yourself calm.

For an array/list of size ‘N’, we have (N - X + 1) subarrays of size ‘X’, and we are linearly traversing each of them. So, the overall time complexity is O(N * X).

Space Complexity

O(1), i.e. constant space complexity.

(100% EXP penalty)

SHOPKEEPER

Console