class Solution {
public:
    int countShipDays(vector<int>& weights, int capacity){
        int usedDays = 1;
        int current = capacity;

        for(int& weight : weights){
            if(weight > capacity){
                return INT_MAX;
            }
            if(current >= weight){
                current -= weight;
            } else {
                usedDays++;
                current = capacity - weight;
            }
        }

        return usedDays;
    }
    int shipWithinDays(vector<int>& weights, int days) {
        int l = 0;
        int r = *max_element(weights.begin(), weights.end());
        int usedDays;
        int mid;

        while(l < r){
            usedDays = countShipDays(weights, r);
            if(usedDays <= days)
                break;
            l = r;
            r = r << 1;
        }

        while(l <= r){
            mid = l + (r - l) / 2;
            usedDays = countShipDays(weights, mid);

            if(usedDays == days){
                r = mid-1;
            } else if(usedDays > days){
                l = mid + 1;
            } else {
                r = mid-1;
            }
        }

        return l;
    }
};