### PROBLEM LINK:

**Authors:** Vaibhav Tulsyan, Aditya Sarode

**Tester:** Vaibhav Tulsyan

**Editorialist:** Vaibhav Tulsyan

### DIFFICULTY:

EASY

### PREREQUISITES:

### PROBLEM:

Given the marks for N questions and the corresponding time to solve, find the maximum marks that can be scored in given time T. Marks for any one particular question can be doubled.

### QUICK EXPLANATION:

Maintain two 2D DP arrays, one being solution to the problem without doubling marks, and another being solution with doubling of marks. For a certain state (i,j), choose max between the value with doubling marks for i’th Question and the value without doubling.

### EXPLANATION:

Consider two DP arrays dp1[i][j] and dp2[i][j].

dp1[i][j] represents the solution without doubling the marks of any question.

dp2[i][j] represents the solution with exactly one question’s marks doubled will now.

Now, for dp2[i][j]:

We have two options: Either reject the previously doubled marks, because doubling marks for current ‘i’ is more profitable, or continue with previously doubled value.

That is, we choose the maximum between 2 choices -

- Double marks of current i ----> ( dp1 [ i - 1 ] [ j - t [ i ] ] ) + 2 * m [ i ] … ( A )
- Dont double marks of current i ----> max( dp2 [ i - 1 ] [ j ], ( dp2 [ i - 1 ][ j - t [ i ] ] + m [ i ] ) … (B)

Hence, dp2 [ i ][ j ] = max ( A , B )

Therefore, the answer is dp2[ N ][ T ] ( 1 - indexed array ).

** Complexity: O( N*T ) **