Treasure Hunt problem asked in Trilogy Innovations

Revision en3, by Prashant94157, 2022-05-15 21:40:48

In front of you ,there is a treasure containing many gems, soon you realize that they contain bad luck and are not precious as well. You have the power to destroy gems but can destroy 1 gem per sec. You can destroy gems in any order and wanted to destroy maximum bad luck. You have given a 2D matrix, where for i'th gem , it takes arr[i][0] seconds to give arr[i][1] units of bud luck and you can decide in which order you want to receive the bad luck. There is no time lapse in the process. Although while receiving bad luck, you can destroy bad luck. Once gem started giving bad luck , cannot be stopped until it is destroyed of its own after giving bad luck. You have to print maximum bad luck you can destroy.

Constraints

1 <= n <= 10^3 1 <= arr[i][0] <= 10^3 1 <= arr[i][0] <= 10^6

Testcase 1:
Input:
4
0 10
1 4
1 3
1 20
Output: 30
Explanation:
You can get maximum 30 when you choose to destroy 0th and 3rd while receiving bad luck from 1st and 2nd gems. 2 gems require 2 seconds to destroy while 1st and 2nd take 2seconds to give bad luck.
Testcase 2:
Input:
7
3 5
6 5
0 8
8 8
7 4
10 3
8 6
Output:
34
Tags dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Prashant94157 2022-05-15 21:40:48 8
en2 English Prashant94157 2022-05-15 21:40:10 28
en1 English Prashant94157 2022-05-15 21:37:50 1201 Initial revision (published)