A straight timber plank spans from position 0 to position L. It must be cut at a fixed set of m distinct interior mark positions (each strictly between 0 and L). Every cut is a full crosscut through whichever single piece currently contains that mark, and it costs the current length of that piece (the distance between the two ends of that piece).
You may perform the required cuts in any order; a cut only ever affects the piece it lands in. Choose the order of cuts that minimizes the total cost, and report that minimum.
Line 1: two integers L and m, the plank length and the number of cut marks.
Line 2: m space-separated distinct integers, the interior mark positions (each in the range 1..L-1). This line is empty when m is 0.
A single integer: the minimum total cutting cost (0 when there are no marks).
Example 1
Input
7 4 1 3 4 5
Expected
16
Explanation
Choosing a good order of the four cuts on a length-7 plank yields a minimum total cost of 16.
Example 2
Input
9 5 5 6 1 4 2
Expected
22
Explanation
The marks may arrive out of order; sorted they are 1,2,4,5,6, and the best cutting order costs 22 in total.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →