DMOPC '17 Contest 1 P4 - Quests - Olympiads Online Judge

DMOPC '17 Contest 1 P4 - Quests

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 64M

Authors:

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$ $N$ NPCs, each of whom offers a distinct repeatable quest. It takes the knight $h_i$ $h_{i}$ hours to reach the $i^\text{th}$ $i^{th}$ NPC and he gains $g_i$ $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}$ $i^{th}$ quest takes him $t_i$ $t_{i}$ hours and rewards him with $q_i$ $q_{i}$ gold. This knight wishes to obtain as much gold as he can, however he cannot log more than $H$ $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?

Constraints

For all subtasks:

$1 \le g_i, q_i \le 10^9$ $1 \leq g_{i}, q_{i} \leq 10^{9}$

$1 \le h_i, t_i \le H$ $1 \leq h_{i}, t_{i} \leq H$

$1 \le H \le 5\,000$ $1 \leq H \leq 5 000$

Subtask 1 [30%]

$1 \le N \le 8$ $1 \leq N \leq 8$

Subtask 2 [30%]

$g_i=q_i$ $g_{i} = q_{i}$ and $h_i=t_i$ $h_{i} = t_{i}$ for all $1 \le i \le N$ $1 \leq i \leq N$

$1 \le N \le 5\,000$ $1 \leq N \leq 5 000$

Subtask 3 [40%]

$1 \le N \le 5\,000$ $1 \leq N \leq 5 000$

Input Specification

The first line of input will have two space separated integers, $N$ $N$ and $H$ $H$ .

The next $N$ $N$ lines of input will each have four space separated integers, $g_i$ $g_{i}$ , $h_i$ $h_{i}$ , $q_i$ $q_{i}$ , and $t_i$ $t_{i}$ in that order.

Output Specification

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

Sample Input 1

Copy

Sample Output 1

Copy

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$ $7 + 3 + 9 + 9$ gold and takes him $1+1+2+2$ $1 + 1 + 2 + 2$ hours.

Sample Input 2

Copy

Sample Output 2

Copy

Explanation for Sample 2

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

Sample Input 3

Copy

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

Copy

Comments

2

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?

-8

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

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.

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