DMOPC '18 Contest 2 P2 - Booster Cushions

View as PDF

Submit solution

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

Problem type

At the Nova Theatre, the balcony seats can be seen as a grid with M rows and N columns. The plays are popular and K people have bought tickets to see the next one. However, these tickets do not have set seats yet. Administration has decided to start selling booster cushions and will be rearranging people's seats to maximize their profit. In particular, an audience member can only see the play if their height is strictly more than the person in the seat directly in front. Otherwise, they will purchase cushions until they can. Each cushion increases their height by exactly 1 centimeter. Note that an audience member who is in the front row or not seated directly behind anyone has no need for cushions. Given the heights of the K people in centimeters, find the maximum number of cushions that can be sold.


1\le K \le 200\,000
K\le M\times N
The heights in centimeters are guaranteed to be integers from 50 to 250

Subtask 1 [30%]

1\le M\le 200\,000

Subtask 2 [30%]

1\le M, N\le 1\,000

Subtask 3 [40%]

1\le M, N\le 200\,000

Input Specification

The first line will contain three space-separated integers, M, N, K.
The next line will contain K space-separated integers, the heights of the people in centimeters.

Output Specification

Output the maximum number of cushions that can be sold after arranging people's seats.

Sample Input 1

2 7 4
250 200 150 100

Sample Output 1


Explanation for Sample 1

Seat the audience like so:

250  200  X  X  X  X  X
150  100  X  X  X  X  X

Then the two in the back two seats must each purchase 101 cushions, giving an answer of 202.

Sample Input 2

5 1 4
100 100 100 100

Sample Output 2


Explanation for Sample 2

Seat the audience like so:


The first person has nobody in front of them, so they purchase 0 cushions.
The next person must purchase 1 cushion and now has a height of 101.
Then the third person must purchase 2 cushions and now has a height of 102.
Finally, the last person must purchase 3 cushions and now has a height of 103.


There are no comments at the moment.