DMOPC '17 Contest 1 P4 - Quests

View as PDF

Submit solution

Points:12 (partial)
Time limit:2.0s
Memory limit:64M

Problem type

In a distant kingdom, there lived a certain knight. What did this knight do? Play video games of course!

In his most recent video game, there are N NPCs, each of whom offers a distinct repeatable quest. It takes the knight h_i hours to reach the i^{\text{th}} NPC and and he gains g_i gold along the way. Once he reaches an NPC, he can perform its quest as many times as he likes. Doing the i^{\text{th}} quest takes him t_i hours and rewards him with q_i gold. This knight wishes to obtain as much gold as he can, however he cannot log more than H hours, lest his lord find out and fire him. Can you help this knight find out the maximum amount of gold he can obtain?


For all subtasks, 1 \le g_i, q_i \le 10^9, 1 \le h_i, t_i \le H, and 1\le H \le 5\,000.

Subtask 1 [30%]

1\le N \le 8

Subtask 2 [30%]

g_i=q_i and h_i=t_i for all 1\leq i \leq N
1 \le N \le 5\,000

Subtask 3 [40%]

1 \le N \le 5\,000

Input Specification

The first line of input will have two space separated integers, N and H.
The next N lines of input will each have four space separated integers, g_i, h_i, q_i, and t_i in that order.

Output Specification

A single integer, the maximum amount of gold the knight can get after H hours.

Sample Input 1

3 6
6 1 3 1
7 1 1 1
3 1 9 2

Sample Output 1


Explanation for Sample 1

The knight should go to the second NPC but not do its quest. Then, he should go to the third NPC and do its quest twice. This gives him 7+3+9+9 gold and takes him 1+1+2+2 hours.

Sample Input 2

5 7
8 2 10 2
9 1 7 1
1 2 8 1
5 3 2 1
7 1 4 3

Sample Output 2


Explanation for Sample 2

The knight should go to the second NPC and do its quest six times.

Sample Input 3

5 557
819777 142 467177 150
647198 31 265541 155
903546 115 261596 138
757957 84 108764 101
935057 137 532908 164

Sample Output 3



  • 1
     commented on Oct. 12, 2017

    Hi, the result of my submission to this problem seems strange. This is the only submission I did during the contest, and the page says the result was "Compilation Error". But according to the ranking page I got 100 points on this problem. Besides, when I submitted the same code again after the contest, it got WA. Is this a bug of the judge system, or did I just misunderstand something?

    • 0
       commented on Oct. 13, 2017

      I'm not entirely sure about the compilation error, but the reason why it went from 100 points to WA is likely because of our pretest system, where we only run your submission on a subset of the test cases. You likely passed the pretests, but then failed the system tests, which is run on the full set of test data.