よって、この問題は \(O(N)\) 時間で解くことができます。

この問題の答えを \(f(W)\) とすると、\(f(W)\leq M\) であるような最小の \(W\) が元の問題の答えです。

\(f\!\left(-1+\sum _ i(1+L _ i)\right)=1\) なので、答えは\(\max _ iL _ i\) 以上 \(-1+\sum _ i(1+L _ i)\) 以下です。

\(f(W)\) は単調減少する関数なので、二分探索でこの問題を解くことができました。

時間計算量は \(O(N\log\sum L _ i)\) になります。

実装例は以下のようになります。 実装の際は、すべての単語の先頭にあらかじめ空白をつけておき、単語の間に間隔を開ける必要がないようにしておくとシンプルになるかもしれません（この場合、答えが \(1\) ずれることに注意してください）。

#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]; // 先頭に空白をつけておく
    }

    long lower = ranges::max(L) - 1; // 答えは max L[i] 以上
    long upper = reduce(begin(L), end(L)); // 答えは ∑ L[i] 以下

    // 二分探索
    while (lower + 1 < upper) {
        long middle = (lower + upper) / 2;

        int rows = 1; // 今の行数
        long length = 0; // 先頭から何文字目か
        for (int i = 0; i < N; ++i) {
            length += L[i]; // 行の末尾に追加してみる
            if (length > middle) { // はみ出たら
                ++rows; // 改行して
                length = L[i]; // 先頭に追加
            }
        }

        if (rows > M) // 縦幅が足りていなければ
            lower = middle; // 答えは middle より大きい
        else // 足りていれば
            upper = middle; // 答えは middle 以下
    }

    // 答えから 1 を引いて出力
    cout << upper - 1 << endl;

    return 0;
}

C++20 以降では、std::ranges::partition_point 関数に ranges::iota_view と判定関数を渡すことで二分探索を行うことができます。 この関数を用いる際、判定関数は先頭から true → false の順番になっている必要があります。

#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; // 先頭に空白を加えておく
    }

    // 二分探索の判定関数
    // 答えが W より大のとき true を返す
    // => 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) は、範囲 r のうち f が false を返す先頭の要素を求める
    // (ただし、r は f によって区分化されている(f が true を返す要素は f が false を返すどの要素よりも前にある)必要がある)
    // 答えから 1 を引いて出力
    cout << *ranges::partition_point(views::iota(ranges::max(L), reduce(begin(L), end(L))), check) - 1 << endl;

    return 0;
}