Cod sursa(job #2507041)

Utilizator dexter123Dexter Dex dexter123 Data 9 decembrie 2019 15:12:42
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include <fstream>
#define N 101
using namespace std;
ifstream fin ("bete.in");
ofstream fout ("bete.out");

int n, suma, a[N];
int s[10001]; /// s[i]=0 daca nu se poate face suma i
/// s[i]=1 daca se poate face suma i
int s2[10001];
int last_added[10001]; ///last_added[i]=ultimul nr adaugat la suma i
int ct=0;
void Read()
{
    fin >> n >> suma;
    for(int i=1; i<=n; i++)
        fin >> a[i];
}

void Afisare(int sum)
{
    if(last_added[sum]==0)
        fout<<ct<<"\n";
    if(last_added[sum]!=0)
    {
        ct++;
        Afisare(sum - a[last_added[sum]]);
        fout << last_added[sum] << " ";
    }

}

void Solve()
{
    int i, j;
    s[a[1]]=1;
    last_added[a[1]]=1;
    for(i=2; i<=n; i++)
    {
        s2[a[i]]=1;
        last_added[a[i]]=i;
        for(j=1; j<=10000; j++)
            if(s[j]==1)
            {
                s2[a[i]+j]=1;
                last_added[a[i]+j]=i;
            }
        ///adaug noile sume si in s
        for(j=1; j<=10000; j++)
            if(s2[j]==1)
            {
                s[j]=1;
                s2[j]=0; ///resetez s2
            }
    }

    if(s[suma]==1)
    {
        fout << "DA" <<"\n";
        Afisare(suma);
    }
    else fout << "NU";
}

int main()
{
    Read();
    Solve();
    //Afisare();
    return 0;
}