Problem B
Consulting Gigs
Languages
en
sv
In the computer-generated world Matriks, you work as a consultant for some hip IT companies that need unique slides for their cool office spaces. During the past year, you got a number of job offers at different points in time, measured in milliseconds since the start of the year. For each job you could choose to design a small, medium or humongous slide for the company, which would take $2 \cdot 10^5$, $3 \cdot 10^5$ or $4 \cdot 10^5$ milliseconds respectively, starting immediately after the offer is given (if accepted). During an assignment, you have to decline every other assignment that is offered during that time. When looking back at the year you’re not particularly dissatisfied (who can complain about designing slides?), but perhaps you could have chosen what job offers to accept in a different way to earn even more. You charge your clients $1$ cookie per $10^5$ milliseconds that you work. If you chose what assignments to accept and their lengths optimally, how many cookies could you have earned?
Input
The first line contains an integer $N$ ($1 \le N \le 10^5$), the number of job offers you got during the year.
The second and final line contains $N$ integers separated with spaces, the times at which you got job offers measured in milliseconds from the start of the year. A year consists of $31\, 556\, 926 \cdot 10^3$ milliseconds. It is guaranteed that each job offer was given at least $4 \cdot 10^5$ milliseconds before the end of the year.
Output
Output an integer, the maximum number of cookies you could have earned.
Explanation of sample 1
A possible solution is to take the first, third and fourth jobs and build a humongous slide for each one. This results in $12$ cookies. The time between the job offers is at least $4 \cdot 10^5$ milliseconds, so no assignments overlap.
Sample Input 1 | Sample Output 1 |
---|---|
4 10000 400000 500000 900000 |
12 |
Sample Input 2 | Sample Output 2 |
---|---|
5 8 10 2 1000000 30556926000 |
12 |
Sample Input 3 | Sample Output 3 |
---|---|
4 100000 400000 400000 700000 |
10 |