Cod sursa(job #54480)

Utilizator goguGogu Marian gogu Data 24 aprilie 2007 21:29:50
Problema Ghiozdan Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>
#define inf 31313

int n, s;
unsigned short best[80000], nr[300], a[22222], t[80000];

int main()
{
    freopen("ghiozdan.in", "r", stdin);
    freopen("ghiozdan.out", "w", stdout);
    int i,j,k;
    scanf("%d %d", &n, &s);
    for (i=0; i<n; i++)
        scanf("%d", &k), nr[k]++;
    n=0;
    for (i=250; i>0; i--)
        for (j=0; j<nr[i]; j++) a[n++]=i;
    for (i=1; i<=s; i++) best[i]=inf;
    best[0]=0;
    int last=0;
    for (i=0; i<n; i++){
        k=a[i];
        last+=k;
        if (last>s) last=s;
        for (j=last; j>=k; j--)
            if (best[j-k]+1<best[j])
               best[j]=best[j-k]+1, t[j]=k;
        if (best[s]<inf) break;
    }
    while (best[s]==inf) s--;
    printf("%d %d\n", s, best[s]);
    while (s) printf("%d\n", t[s]), s-=t[s];
    return 0;
}