values and integers parts and spread. Cut the array into exactly parts non-empty contiguous pieces so that every element lands in exactly one piece. The cost of a piece is its **first** element, and the cost of the cut is the sum of the piece costs.
There is one rule: piece starts must stay close together. If the second piece starts at index i₁ and the last piece starts at index iₖ₋₁, then iₖ₋₁ − i₁ ≤ spread must hold.
Return the minimum cost of a valid cut.values=[4, 9, 2, 7, 1, 8], parts=3, spread=2 → 7
Cut into [4, 9], [2, 7], [1, 8]: the second piece starts at index 2, the third at 4, a gap of 2 ≤ spread. The cost is 4 + 2 + 1 = 7.
values=[5, 1, 6, 6, 1], parts=3, spread=1 → 12
Both 1s cannot be used: indices 1 and 4 differ by 3 > 1. The best is [5], [1], [6, 6, 1] or [5, 1, 6], [6], [1], costing 5 + 1 + 6 = 12.
values=[3, 3, 3, 3], parts=4, spread=2 → 12
values) ≤ 10⁵values[i] ≤ 10⁹parts ≤ len(values)parts − 2 ≤ spread ≤ len(values) − 2values=[4, 9, 2, 7, 1, 8], parts=3, spread=2
7
Run checks the first 3 tests in your browser. Submit checks all 184 tests on the server, hidden ones included.