Video Game

5

3 votes
Algorithms, 4D dynamic programming, Dynamic Programming
Problem

You are playing a video game of N different levels. Initially, you are at level 1 and have at most M minutes of free time to play the game. Playing the ith level gives you an A[i] amount of happiness, and it takes V[i] minutes to play, where A and V are given in the form of an array with N elements.

Additionally, you have K skips, where 1 skip allows you to skip your current level and go directly to the next level. If you skip a level, you won’t receive happiness for that level. Also, you won’t lose any minutes while skipping the level.

If you are currently at the ith level, you can do any of the following three things:

  1. Skip the current level if you have any skips left, and go to the i+1 level.
  2. Play the current level and go to the next level, i+1.
  3. Play the current level and choose to remain on the same level. But the happiness you get next time is half of what you get now. Let’s say you got X amount of happiness by playing the current level. If you stay on the same level, you will get X2 amount of happiness next time. XY means the value of X/Y rounded down to the nearest integer.

If you try to get to the next level (N+1) when you are at level N, the game breaks, and you won’t get any other amount of happiness. Your task is to find the maximum amount of happiness you can get by playing at most M minutes of the video game.

Input Format:

  • The first line contains a single integer T denoting the number of test cases, then the test case follows.
  • The first line of each test case contains three single space-separated integers, N, M, and K.
  • The second line of each test case contains N single space-separated integers, denoting A.
  • The third line of each test case contains N single space-separated integers, denoting V.

Output Format:

For each test case, print the maximum amount of happiness you can achieve by playing the game for at most M minutes. 

Constraints:

1T10

1N,M100

0K20

1A[i]100

1V[i]20

 

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For test case 1:
You can play level 1, choose to go to the next level and play level 2. So, you will get a total of 4+2 = 6 happiness, and the time taken is 2+1 = 3, which doesn’t exceed M. Note that it is not compulsory to use all the given skips. Here we haven’t used them. Hence, the answer is 6.

For test case 2:
We can achieve 8 amounts of happiness if we play in the following manner:

  • Skip the first level. Now no more skips are left.
  • Play the first level. We will get 4 amounts of happiness again play the first level. We will get 2 amounts of happiness. So total happiness till now is 6.
  • Finally, play the third level and get 2 amounts of happiness.
  • Hence, the answer is 8.

For test case 3:
We can play the first, second, and third levels once and get 3 amounts of happiness. Playing the same level again won’t increase happiness in this case.

Editor Image

?