Sua's Candy Baskets
Time limit1sMemory limit512 MB
Given baskets on a line each decaying one candy per time unit, find the maximum total candy collectible starting from position 0 with optimal movement order.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Greedy, Array
- Solved
- No attempts yet
Problem
Sua starts at coordinate 0 on the x-axis. There are n candy baskets on the x-axis, and each basket initially contains m candies. The basket positions are x_1, x_2, ..., x_n.
For every 1 unit of time that passes, each basket loses 1 candy. When Sua reaches a basket, she can instantly eat all candies remaining in that basket. Moving distance 1 along the x-axis takes 1 unit of time.
Compute the maximum number of candies Sua can eat.
Input
The first line contains n and m. Each of the next n lines contains one basket position x_i.
- 0 <= n <= 300
- 1 <= m <= 1,000,000
- -10,000 <= x_i <= 10,000
- All basket positions are distinct.
Output
Print the maximum number of candies Sua can eat.