DMOPC '14 Contest 3 P6 - Not Enough Time! - DMOJ: Modern Online Judge

DMOPC '14 Contest 3 P6 - Not Enough Time!

Points: 10 (partial)

Time limit: 1.4s

Memory limit: 64M

Author:

Problem type

Amagi Brilliant Contests runs a business making and hosting contests on its online platform for competitive programmers who want to run their own contests.

After several weeks and dozens of contests later, word got around about how great Amagi Brilliant Contests was, and now ABC is facing an unforeseen problem: business is booming and it has too many potential customers who wish to purchase problemsets!

For each of the $N$ ~N~ customers, there are three possible problemsets to sell to them: Poor, Average, Good. Each problemset has two attributes: $P$ ~P~, the preparation time, in minutes, and $V$ ~V~, the monetary worth of the problemset, in dollars. Of course, the names of the problemsets imply that $P_{Poor} \le P_{Average} \le P_{Good}$ ~P_{Poor} \le P_{Average} \le P_{Good}~ and $V_{Poor} \le V_{Average} \le V_{Good}$ ~V_{Poor} \le V_{Average} \le V_{Good}~.

While Amagi Brilliant Contests wants to provide each customer with a Good problemset, it has strict deadlines to meet — namely, ABC has at most $T$ ~T~ minutes in total to prepare problemsets for their customers. In this state of emergency, the management has decided that if necessary, they will sell some of the Poor and Average problemsets in order to make the most money. Sometimes, ABC will even have to turn customers down, if selling to them won't let ABC make the most money.

You are the head of the optimization problems department at Amagi Brilliant Contests, and so you have been tasked with determining the maximum profit ABC can make.

Constraints

$1 \le N \le 2\,000$ ~1 \le N \le 2\,000~

$1 \le T \le 10\,000$ ~1 \le T \le 10\,000~

For each problemset,

$1 \le P \le 10\,000$ ~1 \le P \le 10\,000~

$1 \le V \le 1\,000\,000$ ~1 \le V \le 1\,000\,000~

For test cases worth 25% of the total marks, $1 \le N \le 5$ ~1 \le N \le 5~.

For test cases worth an additional 25% of the total marks, $1 \le N \le 1\,000$ ~1 \le N \le 1\,000~.

Input Specification

The first line of input will have $N$ ~N~, $T$ ~T~ separated by a single space.

The next $N$ ~N~ lines each contain six integers: $P_{Poor}, V_{Poor}, P_{Average}, V_{Average}, P_{Good}, V_{Good}$ for the problemsets offered to that customer.

Output Specification

The first and only line of output should contain the maximum amount of money ABC can earn from the customers.

Sample Input 1

2 300
100 10 200 20 300 30
100 20 400 80 600 120

Sample Output 1

Explanation for Sample Output 1

ABC will give the first customer an Average problemset and the second customer a Poor problemset. 40 dollars is the most money ABC can make from these two customers.

Sample Input 2

2 250
100 30 150 30 200 30
50 5 200 10 400 15

Sample Output 2

Explanation for Sample Output 2

One way to obtain 35 dollars is to give the first customer a Good problemset and the second customer a Poor problemset.

Comments

12

kevinyang commented on Oct. 31, 2020, 7:18 a.m.

You have some nice variable names there. https://dmoj.ca/submission/3101910

0

pro commented on Dec. 27, 2017, 3:32 a.m.

How do I fix out of memory error?

1

Machine_A_Rajeunir commented on Jan. 28, 2019, 7:55 p.m. ← edit 2 →

Concerning this problem, you only care about the previous DP state. Therefore, there is no need to have an array $N$ ~N~ by $K$ ~K~ size. $K$ ~K~ or $2$ ~2~ by $K$ ~K~ array with modulo operations to check for previous DP state will suffice.

-1

31501357 commented on Oct. 31, 2020, 3:18 a.m. ← edited →

I have an array of size $N \times T$ ~N \times T~.