## Editorial for DMOPC '17 Contest 1 P4 - Quests

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

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.

**Time complexity: **

For subtask 2, the problem is exactly unbounded knapsack.

**Time complexity: **

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.

**Time complexity: **

## Comments