Cod sursa(job #3308713)

Utilizator raluca1977Raluca zanfir raluca1977 Data 27 august 2025 15:39:05
Problema Economie Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin ("economie.in");
ofstream fout ("economie.out");

int n, cnt;
int b[1001], dp[50005], a[1001];

int main(){

    fin >> n;
    for (int i = 1; i <= n; i++){
        fin >> b[i];
    }
    sort(b + 1, b + n + 1);

    for (int i = 1; i <= b[n]; i++){
        dp[i] = 999999;
    }
    dp[0] = 0;

    for (int i = 1; i <= n; i++){
        if (dp[b[i]] == 999999){
            cnt++;
            a[cnt] = b[i];

            for (int j = b[i]; j <= b[n]; j++){
                if (dp[j - b[i]] != 999999){
                    dp[j] = min (dp[j], dp[j - b[i]] + 1);
                }
            }

        }
    }

    fout << cnt << "\n";
    for (int i = 1; i <= cnt; i++){
        fout << a[i];
    }

    return 0;
}