class Solution {
private:
    bool check(vector<int>& weights, int D, int threshold) {
        int days = 1;
        int sum = 0;
        for (int w: weights) {
            if (w > threshold) {
                return false;
            }
            sum += w;
            if (sum > threshold) {
                sum = w;
                ++days;
            }
        }
        return days <= D;
    }

public:
    int shipWithinDays(vector<int>& weights, int D) {
        int l = 0;
        int r = 500 * 50000;

        while (l < r) {
            const int mid = l + r >> 1;
            if (check(weights, D, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return r;
    }
};