Grazing on the Run
Time limit1sMemory limit128 MB
Bessie starts at position L and walks a line to eat N grass clumps; minimize the sum of times at which each clump is eaten.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Intervals, Greedy
- Solved
- No attempts yet
Problem
Picture a long, straight pasture as a number line. On this line there are clumps of grass () at distinct integer positions; treat each clump as a single point on the line.
Bessie the cow starts at an integer position () and travels along the line, moving freely in either direction (reversing whenever she likes) until she has eaten every clump. She moves at a constant speed of one unit of distance per unit of time, and she eats a clump the instant she reaches its position.
A clump that goes uneaten for a while grows stale. The staleness of a clump is the amount of time that passes from the moment Bessie starts moving until she eats that clump. Bessie wants to minimize the total staleness of all the clumps.
Find the minimum possible total staleness once every clump has been eaten.
Input
The first line contains two space-separated integers and .
Each of the next lines contains one integer (), the position of a clump. All positions are distinct.
Output
Print, on a single line, the minimum total staleness Bessie can achieve after eating all of the clumps.