DMOPC '17 Contest 1 P4 - Quests

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.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 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

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 \le i \le 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
    discoverMe  commented on Jan. 15, 2019, 8:30 p.m. edited

    can you go to an NPC more than once?

    no you can't

    • 5
      pblpbl  commented on April 13, 2020, 4:14 p.m. edited

      this is a valid point (should be in the problem statement) For example, it appears that you cannot visit the same few npcs and not do their quests if their 'visiting quest' is better.

  • 0
    fluffyowl  commented on Oct. 12, 2017, 10:47 a.m.

    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?

    • -7
      Kirito  commented on Oct. 13, 2017, 4:44 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.