length. A scale from 0 to length runs along it, and the array marks lists the points where the log has to be sawn.
Each cut splits one piece into two. A cut costs as much as the length of the piece currently under the saw. You may make the cuts in any order, but in the end the log must be sawn at every mark.
Return the smallest possible total cost of all the cuts.length=8, marks=[2, 5] → 13
Saw at mark 5 first (cost 8), then the piece of length 5 at mark 2 (cost 5): 13 in total. The other order costs 8 + 6 = 14.
length=10, marks=[1, 5, 9] → 20
Starting in the middle is best: 10 for the first cut and 5 for each of the other two, 20 in total.
length=4, marks=[3] → 4
length ≤ 10⁶marks) ≤ min(length − 1, 100)marks[i] ≤ length − 1length=8, marks=[2, 5]
13
Run checks the first 3 tests in your browser. Submit checks all 91 tests on the server, hidden ones included.