Cod sursa(job #3164646)

Utilizator Manolea_Teodor_StefanManolea Teodor Stefan Manolea_Teodor_Stefan Data 3 noiembrie 2023 23:37:08
Problema Economie Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>
#define MAX_N 500001
using namespace std;
ifstream fin("economie.in");
ofstream fout("economie.out");
int n;
unsigned short arr[MAX_N];
bool arr_bool[MAX_N];
vector<unsigned short> ans;
vector<short> pnt_arr;
long long sum;
bool check_state(){
    for(int i = 0; i < pnt_arr.size() - 1; i++)
        if(pnt_arr[i] > pnt_arr.back())
            return false;
    sum = 0;
    for(int i : pnt_arr){
        sum+=arr[i];
        if(sum > arr[n])
            return false;
    }
    return true;
}
bool answer(){
    sum = 0;
    for(int i : pnt_arr)
        sum+=arr[i];
    if(arr_bool[sum]){
        arr_bool[sum] = false;
        pnt_arr.push_back(0);
        return true;
    }
    pnt_arr.push_back(0);
    return false;
}
void solve(){
    pnt_arr.push_back(0);
    bool ok;
    while(!pnt_arr.empty()){
        ok = true;
        if(ok && pnt_arr.back() < ans.size()+1){
            pnt_arr.back()++;
            if(check_state())
                ok = false;

        }
        if(ok)
            pnt_arr.pop_back();
        else
            if(answer());
    }
    return;
}
int main()
{
    fin>>n;
    for(int i = 1; i<=n; i++){
        fin>>arr[i];
        arr_bool[arr[i]] = true;
        if(arr[i] == 1){
            fout<<1<<'\n'<<1;
            return 0;
        }
    }
    sort(arr + 1, arr + 1 + n);
    for(int i = 1; i<=n; i++){
        if(arr_bool[arr[i]]){
            ans.push_back(arr[i]);
            solve();
        }
    }
    fout<<ans.size()<<'\n';
    for(int i : ans)
        fout<<i<<'\n';
    return 0;
}