class Solution {
public:
    int maximizeSweetness(vector<int>& sweetness, int K) {
        int low, high, cuts, sum;
        low = INT_MAX; sum = 0;
        for(int &num: sweetness){
            sum += num;
            low = min(low, num);
        }
        high = sum/(K+1);
        
        while(low < high){
            int mid = (low+high+1)/2;
            sum = 0;
            cuts = 0;
            for(int &x: sweetness){
                sum += x;
                if(sum >= mid){
                    sum = 0;
                    cuts++;
                }
                if(cuts == K+1) break;
            }
            if(cuts > K)
                low = mid;
            else
                high = mid-1;
        }
        return low;
    }
};