Morning Three and Evening Four
Time limit2sMemory limit128 MB
Given N banana weights, choose non-overlapping length-K blocks to move as a C-second group, minimizing total time and then the number of groups used, with output of chosen block positions.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Prefix sum, Array, Intervals
- Solved
- No attempts yet
Problem
A monkey that escaped from a zoo wants to move all N bananas placed in a line to its hideout.
The monkey can move bananas in two ways.
- Move one banana. This takes time equal to that banana's weight.
- Move K bananas that are consecutive in the original order at once. This always takes C seconds.
Returning from the hideout to the distribution place takes 0 seconds, because the monkey can teleport when it is not carrying bananas.
Given the weights of the N bananas, find the minimum time needed to move every banana. If several plans achieve the minimum time, choose one that uses the fewest grouped moves of K bananas.
Input
The first line contains the number of bananas N. N is an integer between 1 and 1,000,000, inclusive.
The second line contains K and C. Each of K and C is an integer between 1 and 10,000, inclusive.
The third line contains N positive integers, the banana weights in their original order. Each weight is between 1 and 1,000, inclusive.
Output
Print the minimum time needed to move every banana on the first line.
Print the number of grouped moves of K bananas on the second line.
On the third line, print the leftmost positions of the chosen groups in increasing order. Positions are 1-indexed. If no group is chosen, print an empty line.
If several plans satisfy both the minimum time and the minimum number of grouped moves, any one of them may be printed.