Tester: Vaibhav Tulsyan
Editorialist: Vaibhav Tulsyan
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.
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.
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 )