Editorial for DMOPC '17 Contest 1 P4 - Quests
Submitting an official solution before solving the problem yourself is a bannable offence.
For subtask 1, brute-force all possible choices of NPCs. After checking the gold and time obtained from reaching the NPC, the problem becomes unbounded knapsack.
For subtask 2, the problem is exactly unbounded knapsack.
For the final subtask, consider the NPCs one by one. For each NPC, you have the choice to go to it or not. Say is the answer given hours and not going to the NPC and is the answer given hours and going to the NPC. Then is the maximum of and . So the answer can be computed using this.