Fair Candy Bar Cut

Hard

A candy bar is a row of squares, and square i has tastiness tastiness[i]. You share the bar with friends friends: you make exactly friends cuts between squares and get friends + 1 pieces, each made of consecutive squares. Your friends get the better pieces and you keep the one with the smallest total tastiness. Cut the bar so that your own piece is as tasty as possible and return its total tastiness.

Example 1

tastiness=[4, 1, 2, 6, 3, 3], friends=2 → 6

Cut into [4, 1, 2], [6] and [3, 3] with totals 7, 6 and 6. You keep a piece worth 6, and no cut does better.

Example 2

tastiness=[3, 8, 2], friends=2 → 2

Three pieces from three squares allow only one cut layout; the weakest square is worth 2.

Example 3

tastiness=[5, 5, 5], friends=0 → 15

Constraints

0 ≤ friends < len(tastiness) ≤ 10⁴
1 ≤ tastiness[i] ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search

Similar problems

Median Across Two Arrays Hard Minimum of a Shifted Array With Repeats Hard Frame Around an Ink Blot Hard Smaller Values to the Right Hard Window Sums Within a Band Hard

Input

tastiness=[4, 1, 2, 6, 3, 3], friends=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 79 tests on the server, hidden ones included.