Divide Chocolate

class Solution {
public:
    int maximizeSweetness(vector<int>& sweetness, int k) {
        auto feasible = [&](int t) {
            int cuts = 0, cur = 0;
            for (int x : sweetness) {
                cur += x;
                if (cur >= t) { ++cuts; cur = 0; }
            }
            return cuts >= k + 1;
        };
        int lo = *min_element(sweetness.begin(), sweetness.end());
        int hi = accumulate(sweetness.begin(), sweetness.end(), 0) / (k + 1);
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2;
            if (feasible(mid)) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    }
};

func maximizeSweetness(sweetness []int, k int) int {
    feasible := func(t int) bool {
        cuts, cur := 0, 0
        for _, x := range sweetness {
            cur += x
            if cur >= t {
                cuts++
                cur = 0
            }
        }
        return cuts >= k+1
    }
    lo := sweetness[0]
    sum := 0
    for _, x := range sweetness {
        if x < lo {
            lo = x
        }
        sum += x
    }
    hi := sum / (k + 1)
    for lo < hi {
        mid := lo + (hi-lo+1)/2
        if feasible(mid) {
            lo = mid
        } else {
            hi = mid - 1
        }
    }
    return lo
}

from typing import List

class Solution:
    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
        def feasible(t: int) -> bool:
            cuts = 0
            cur = 0
            for x in sweetness:
                cur += x
                if cur >= t:
                    cuts += 1
                    cur = 0
            return cuts >= k + 1

        lo = min(sweetness)
        hi = sum(sweetness) // (k + 1)
        while lo < hi:
            mid = lo + (hi - lo + 1) // 2
            if feasible(mid):
                lo = mid
            else:
                hi = mid - 1
        return lo

var maximizeSweetness = function(sweetness, k) {
    const feasible = (t) => {
        let cuts = 0, cur = 0;
        for (const x of sweetness) {
            cur += x;
            if (cur >= t) { cuts++; cur = 0; }
        }
        return cuts >= k + 1;
    };
    let lo = Infinity, sum = 0;
    for (const x of sweetness) {
        if (x < lo) lo = x;
        sum += x;
    }
    let hi = Math.floor(sum / (k + 1));
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo + 1) / 2);
        if (feasible(mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
};

class Solution {
    private int[] sweetness;
    private int k;

    public int maximizeSweetness(int[] sweetness, int k) {
        this.sweetness = sweetness;
        this.k = k;
        int lo = Integer.MAX_VALUE, sum = 0;
        for (int x : sweetness) {
            if (x < lo) lo = x;
            sum += x;
        }
        int hi = sum / (k + 1);
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2;
            if (feasible(mid)) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    }

    private boolean feasible(int t) {
        int cuts = 0, cur = 0;
        for (int x : sweetness) {
            cur += x;
            if (cur >= t) { cuts++; cur = 0; }
        }
        return cuts >= k + 1;
    }
}

function maximizeSweetness(sweetness: number[], k: number): number {
    const feasible = (t: number): boolean => {
        let cuts = 0, cur = 0;
        for (const x of sweetness) {
            cur += x;
            if (cur >= t) { cuts++; cur = 0; }
        }
        return cuts >= k + 1;
    };
    let lo = Infinity, sum = 0;
    for (const x of sweetness) {
        if (x < lo) lo = x;
        sum += x;
    }
    let hi = Math.floor(sum / (k + 1));
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo + 1) / 2);
        if (feasible(mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}