Fundamente XI - Etalon - 209

#include <bits/stdc++.h>

using namespace std;

inline void drum(int k, vector < int >& t) {
    if(k != 0) {
        cout << t[k] << ' ';
        drum(k - t[k], t);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector < int > a(n + 1);
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    vector < bool > dp(k + 1); // dp[i] - pot cantari greutatea i?
    vector < int > t(k + 1); // t[x] - greutatea ultimului etalon folosit pentru a masura greutatea x
    // pentru a evita folosirea unui etalon de mai multe ori parcurg dp invers
    dp[0] = true;
    int mx = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = mx; j >= 0; --j)
            if(dp[j] &&  j + a[i] <= k && !dp[j + a[i]]) {
                dp[j + a[i]] = true;
                t[j + a[i]] = a[i];
                mx = max(mx, j + a[i]);
            }
    if(!dp[k])
        cout << "Imposibil";
    else
        drum(k, t);
}