Therefore, the subproblem can be solved in an \(O(N)\) time.

Let \(f(W)\) be the answer to this subproblem; then the answer to the original problem is the minimum \(W\) with \(f(W)\leq M\).

Since \(f\!\left(-1+\sum _ i(1+L _ i)\right)=1\), the answer is between \(\max _ iL _ i\) and \(-1+\sum _ i(1+L _ i)\), inclusive.

Since \(f(W)\) is a monotonically decreasing function, the problem has been solved with a binary search.

The time complexity is \(O(N\log\sum L _ i)\).

A sample code follows. The implementation might be simpler by prepending a space at the initial position of every word, so that there is no need to add a space between words. (Note that the answer exactly differs by one in this solution.)

#include <vector>
#include <algorithm>
#include <iostream>
#include <ranges>
#include <numeric>

int main() {
    using namespace std;

    int N, M;
    cin >> N >> M;
    vector<long> L(N);
    for (int i = 0; i < N; ++i) {
        cin >> L[i];
        ++L[i]; // Prepend a space
    }

    long lower = ranges::max(L) - 1; // The answer is at least max L[i]
    long upper = reduce(begin(L), end(L)); // The answer is at most ∑ L[i]

    // Binary search
    while (lower + 1 < upper) {
        long middle = (lower + upper) / 2;

        int rows = 1; // Index of current line
        long length = 0; // Position in the line
        for (int i = 0; i < N; ++i) {
            length += L[i]; // Try to append to the end of the line
            if (length > middle) { // If it sticks out
                ++rows; // add a newline
                length = L[i]; // and append to the beginning
            }
        }

        if (rows > M) // If the height is large enough
            lower = middle; // then the answer is strictly greater than middle;
        else // 足りていれば
            upper = middle; // otherwise, the answer is less than or equal to middle
    }

    // Print the answer subtracted by one
    cout << upper - 1 << endl;

    return 0;
}

In C++20 and later, one can pass ranges::iota_view and the decision function to the std::ranges::partition_point function to do the binary search. When using this function, the decision function must evaluate to true for the initial elements, and false for the remaining.

#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>
#include <numeric>

int main() {
    using namespace std;

    unsigned N, M;
    cin >> N >> M;
    vector<unsigned long> L(N);
    for(auto&& l : L){
        cin >> l;
        ++l; // Prepend a space
    }

    // Decision function of the binary search
    // It returns true when the answer is strictly greater than W
    // => the answer is the minimum value that evaluates to false
    const auto check{[L, M](unsigned long W) -> bool {
        unsigned long length = 0;
        unsigned rows = 1;
        for (const auto l : L) {
            length += l;
            if (length > W) {
                ++rows;
                length = l;
            }
        }
        return rows > M;
    }};

    // ranges::partition_point(r, f) returns the first element within the range r for which f returns false
    // (Here, r must be partitioned by f, i.e. every element for which f evaluates to true must be prior to an element that evaluates to false).
    cout << *ranges::partition_point(views::iota(ranges::max(L), reduce(begin(L), end(L))), check) - 1 << endl;

    return 0;
}