A foundry lines up n slag piles in a row, each with a positive integer weight. In one move you take exactly k consecutive piles and merge them into a single pile whose weight is the sum of those k piles; the move costs that summed weight. You repeat until a single pile remains.
Depending on n and k, reducing the whole row to one pile may be impossible. If it is impossible, report -1. Otherwise report the minimum total cost.
Line 1: two integers n and k, the number of piles and the merge width.
Line 2: n space-separated positive integers, the pile weights from left to right.
A single integer: the minimum total merge cost, or -1 if the row cannot be reduced to one pile.
Example 1
Input
4 2 3 2 4 1
Expected
20
Explanation
With k=2 the whole row can always be merged; the minimum total cost here is 20.
Example 2
Input
5 3 3 5 1 2 6
Expected
25
Explanation
Since (5-1) is divisible by (3-1), the row can be reduced to one pile, and the minimum total cost is 25.
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 →