Fundamente XI - 9 / 219

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, Z, K;
    cin >> N >> Z >> K;
    vector < vector < int > > dp(N + 1, vector < int >(K + 1, INF)), t(N + 1, vector < int >(K + 1));
    /* dp[i][j] = nr. minim de zile necesare pentru a avea i persoane
                  si j perechi de persoane nascute in aceeasi zi */
    // Exista sol <=> dp[N][K] <= Z
    dp[0][0] = 0;
    dp[1][0] = t[1][0] = 1;
    for(int i = 2; i <= N; ++i)
        for(int j = 1; j <= K; ++j)
            for(int z = 1; z <= i; ++z)
                if(j - z * (z - 1) / 2 >= 0 && dp[i][j] > dp[i - z][j - z * (z - 1) / 2] + 1) {
                    dp[i][j] = dp[i - z][j - z * (z - 1) / 2] + 1;
                    t[i][j] = z;
                }
    if(dp[N][K] > Z)
        cout << "Nu exista solutie\n";
    else {
        vector < int > sol;
        while(N > 0) {
            int i = t[N][K];
            for(int j = 1; j <= i; ++j)
                sol.emplace_back(dp[N][K]);
            N -= i;
            K -= i * (i - 1) / 2;
        }
        reverse(sol.begin(), sol.end());
        for(int x : sol)
            cout << x << ' ';
    }
}