Cherchez vol 2 - Paragrafare Optimala - pag 201

#include <bits/stdc++.h>
#define p3(x) ((x) * (x) * (x))

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector < string > a(N + 2);
    vector < int > lg(N + 2);
    for(int i = 1; i <= N; ++i) {
        cin >> a[i];
        lg[i] = lg[i - 1] + a[i].size();
    }
    vector < int > dp(N + 2), last(N + 2);
    last[N] = N;
    for(int i = N - 1; i > 0; --i)
        if(lg[N] - lg[i - 1] + N - i <= M) {
            dp[i] = 0;
            last[i] = N;
        }
        else {
            dp[i] = p3(M - lg[i] + lg[i - 1]) + dp[i + 1];
            last[i] = i;
            for(int j = i + 1; j < N; ++j) {
                if(lg[j] - lg[i - 1] + j - i > M)
                    break;
                if(dp[i] > dp[j + 1] + p3(M - (lg[j] - lg[i - 1] + j - i))) {
                    dp[i] = dp[j + 1] + p3(M - (lg[j] - lg[i - 1] + j - i));
                    last[i] = j;
                }
            }
        }
    cout << dp[1] << '\n';
    int poz = 0;
    while(poz < N) {
        for(int i = poz + 1; i < last[poz + 1]; ++i)
            cout << a[i] << ' ';
        cout << a[last[poz + 1]] << '\n';
        poz = last[poz + 1];
    }
}