New update is available. Click here to update.

Last Updated: 19 Mar, 2021

Moderate

```
βNβ = 6, βKβ = 3
βEXPβ = [1, 4, 2, 2, 3, 6]
βBUSYβ = [0, 1, 1, 0, 0, 1]
To get the maximum experience ninja has to focus on the last β3β days. The maximum experience gained will be = 1 + 2 + 3 + 6 = 12. So, the answer is 12.
```

```
The first line of input contains an integer βTβ which denotes the number of test cases. Then, the βTβ test cases follow.
The first line of each test case contains two space-integer βNβ and βKβ denoting the course duration and the number of days ninja can focus on the course.
The second line of each test case contains βNβ space-separated integers representing the array βEXPβ.
The third line of each test case contains βNβ space-separated integers representing the array βBUSYβ.
```

```
For every test case, print a single line containing a single integer denoting the maximum experience that the ninja can gain from this course.
The output of each test case will be printed in a separate line.
```

```
You do not need to print anything; it has already been taken care of. Just implement the function.
```

```
1 <= T <= 100
1 <= N <= 1000
0 <= K <= N
0 <= EXP[i] <= 10 ^ 6
BUSY[i] = {0, 1}
Time limit: 1 second.
```

Approaches

Use βresβ to store the maximum experience that ninja can gain. Initially, ninja focuses on attending the first βKβ days starting from day β0β (to βK - 1β). Calculate the total experience gained and store it in βresβ. Now, focus on the next βKβ days starting from day β1β (to βKβ), and if the total experience gained is more than βresβ, then update βresβ. Similarly, find the experience gained for each such combination until the last βKβ days, each time updating the value of βresβ.

Find the experience gained without requiring any focus(non-busy days) and store it in βdirectExpβ.To find the experience gained after focusing on any βKβ days, iterate through the βKβ days and only add experiences of those days when ninja was busy to βdirectExpβ (as βdirectExpβ already stores the experience gained on non-busy days).

- Initialize βresβ to βINT_MINβ. Use βresβ to store the answer. βINT_MINβ is the lowest possible integer value.
- Initialize βdirectExp = 0β. Use to store the experience gained on non-busy days.
- Run a loop where βiβ ranges from β0β to βn - 1β:
- If βBUSY[i]β is equal to 0, then:
- βdirectExp += EXP[i]β

- If βBUSY[i]β is equal to 0, then:
- Run a loop where βiβ ranges from β0β to βN - Kβ:
- βcurExp = directExpβ. Use to find the experience gained from busy days if ninja focusses from the day βiβ to βi + K - 1β.
- Run a loop where βjβ ranges from βiβ to βi + K - 1β:
- If βBUSY[j]β is equal to 1, then:
- βcurExp += EXP[j]β

- If βBUSY[j]β is equal to 1, then:
- If βcurExpβ is greater than βresβ, then:
- βres = curExpβ.

- Return βresβ as the answer.

Let βdirectExpβ be the experience gained without requiring any focus (non-busy days), and βfocusExpβ be the maximum experience gained on busy days from a window of βKβ consecutive days. So, the maximum experience that ninja can gain is equal to βdirectExp + focusExpβ. Calculate βdirectExpβ and after that for all non-busy days set βEXP[i] = 0β.

As βEXP[i] = 0β for non-busy days, the experience gained on busy days from:

Day 0 to βK - 1β = βcurExpβ = βsummation of EXP[i]β where βiβ ranges from 0 to βK - 1β.

Day 1 to βKβ = βcurExp - EXP[0] + EXP[k]β

Update βcurExp = curExp - EXP[0] + EXP[k]β.

Day 2 to βK + 1β = βcurExp - EXP[1] + EXP[K + 1]β, and so on.

Similarly, move this window of βKβ days until the last βKβ days and store the maximum value of βcurExpβ in βfocusExpβ.

- Initialize βdirectExp = 0β. Use to store the experience gained on non-busy days.
- Run a loop where βiβ ranges from β0β to βN - 1β:
- If βBUSY[i]β is equal to 0, then:
- βdirectExp += EXP[i]β
- βEXP[i] = 0β

- If βBUSY[i]β is equal to 0, then:
- Initialize βfocusExpβ to β0β. Use it to store the maximum experience gained on busy days from a window of βKβ consecutive days.
- βcurExp = summation of EXP[i]β where βiβ ranges from 0 to βK - 1β.
- βfocusExp = curExpβ.
- Run a loop where βiβ ranges from β1β to βN - Kβ:
- βcurExp = curExp - EXP[i -1] + EXP[i + K - 1]β
- If βcurExpβ is greater than βfocusExpβ, then:
- βfocusExp = curExpβ.

- Return βdirectExp + focusExpβ as the answer.