DMOPC '19 Contest 4 P3 - Taking Cues

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.4s
Memory limit: 128M

Problem type

Veshy has been playing too much 8-ball pool recently, so to cure his addiction, he has turned to collecting pool cue balls instead. While looking into the market for cue balls, he realizes that there is a lot of money to be made. Each month, he can buy and sell a maximum of X_i and Y_i cue balls at a price of b_i and s_i respectively for each month m_i. Cue balls, being very valuable, also cost M maintenance (per held cue ball) to upkeep per month. Being Veshy's best friend, you wish to help him maximize his profits over the course of N months. Since Veshy is looking at very long term investments, help him by writing a program!


For all subtasks:

1 \le N \le 10^4

1 \le M \le 10^4

1 \le X_i,Y_i \le 100

1 \le b_i,s_i \le 10^4

Veshy can only hold up to 100 cue balls at any time.

Veshy can borrow money to buy cue balls (go into debt), but he can never sell more cue balls than he possesses.

Veshy has to wait at least 1 month before selling the cue balls he buys.

Note for Python users: To pass this question using Python you must select the PyPy interpreter instead of the normal one.

Subtask 1 [20%]

1 \le N \le 20

Subtask 2 [30%]

1 \le N \le 10^3

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line will contain two space-separated integers, N and M. The following N lines will contain 4 space-separated integers, X_i, Y_i, b_i, and s_i for month m_i.

Output Specification

Output the maximum profit Veshy can make by the end of the N month period.

Sample Input 1

3 1
5 3 1 2
3 4 3 2
1 5 2 10

Sample Output 1


Explanation of Sample Output 1

Veshy can buy 5 cue balls on the first month for a price of 1 dollar each. He can then hold on to these cue balls until the last month, where he can sell them for a price of 10 dollars each. Since the cost of maintenance is 1 dollar, and Veshy is holding onto those 5 cue balls for 2 months, Veshy's total profit would be 50 - 5 \times 1 - 5 \times 2 = 35 dollars.

Sample Input 2

3 100
2 2 100 1
10 5 100 1
1 5 10000 1

Sample Output 2


Explanation of Sample Output 2

Here, the best move that Veshy could make is to not invest in the market at all! Buying any amount of cue balls on any month will always result in a loss.


There are no comments at the moment.