TSPMOHUG - Hu-Gi-Oh
Hugo Wangbros has been playing a lot of Yu-Gi-Oh recently, and he recently invented his own variation of the game: Hu-Gi-Oh!
In the world of Hu-Gi-Oh, Hugo is in a duel where he must build a power chain using a selection of magic cards. Each card has a power value and a cooldown time. Hugo wants to play cards in a sequence such that:
- He skips at least the number of rounds equal to the cooldown after using any card before using the next one.
- The total power is maximized.
Given a list of cards, each with its power and cooldown, compute the maximum power Hugo can achieve.
Note: Hugo is allowed to skip the card on any round.
Input
n: number of cards (1 ≤ n ≤ 105)
n lines follow, each containing two integers p and c:
p: power of the card (0 ≤ p ≤ 104)
c: cooldown of the card (0 ≤ c ≤ n)
n
p1 c2
p1 c2
...
pn cn
Output
output a single integer, the maximum total power Hugo can achieve.
Example
Input: 5 3 2 2 1 4 0 6 2 1 1 Output: 10
Explanation
The optimal solution is to first play card 3 (p=4, c=0), and play card 4 (p=6, c=2). Which gives 10.
hide comments
|
dpik:
2025-05-22 14:07:23
Example case explanation: If Hugo uses card one with a cooldown of 2, he cannot use card 2 AND 3 (p=2 and p=4) |
Added by: | OuiOuiBaguette |
Date: | 2025-05-22 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |