Fundamente XI - 6 / 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, S;
    cin >> N >> S;
    vector < int > a(N);
    for(int& x : a)
        cin >> x;
    vector < int > dp(S + 1, INF), t(S + 1);
    dp[a[0]] = 1;
    t[a[0]] = a[0];
    for(int i = 1; i < N; ++i) {
        for(int j = S - a[i]; j >= 0; --j)
            if(dp[j] && dp[j] + 1 < dp[j + a[i]]) {
                dp[j + a[i]] = dp[j] + 1;
                t[j + a[i]] = a[i];
            }
        if(dp[a[i]] == INF) {
            dp[a[i]] = 1;
            t[a[i]] = a[i];
        }
    }
    cout << dp[S] << '\n';
    vector < int > sol;
    while(S > 0) {
        sol.emplace_back(t[S]);
        S -= t[S];
    }
    reverse(sol.begin(), sol.end());
    for(int it : sol)
        cout << it << ' ';
}