Depressing Vacation
InterviewTime limit1sMemory limit512 MB
Place N ordered appointments within M vacation days to minimize the total squared depression, where each idle day lowers the mood by 1.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Implementation, Math, Greedy
- Solved
- No attempts yet
Problem
Inho is left alone in his dormitory for the vacation, and he feels depressed and lonely. Fortunately, he has N appointments during the M-day vacation, so he wants to arrange the appointment dates efficiently to minimize the total depression he feels during the vacation.
Inho's mood can be expressed as an integer. On a day when his mood is less than 0, he feels depression equal to (mood)2. If he has an appointment today, his mood is the appointment's expected happiness value Hi; if he has no appointment, his mood is yesterday's mood minus 1.
Inho can handle at most one appointment per day, and the N appointments must be handled in the given order.
The vacation starts tomorrow, and Inho's mood today is 0. Arrange the appointments appropriately to minimize the total depression Inho feels during the vacation.
Input
The first line gives the number of appointments N, a nonnegative integer, and the number of vacation days M, a positive integer, separated by a space. (0 ≤ N < M < 1000)
The second line gives N integers H1, H2, ..., HN separated by spaces. Hi is the expected happiness value of the i-th appointment. (1 ≤ H**i < 100)
Output
On the first line, output the minimum total depression Inho feels during the vacation.