Cod sursa(job #216784)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 25 octombrie 2008 21:20:58
Problema Ghiozdan Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#include <math.h>

#define inf 31313

long n, s, best[80000], nr[300], a[22222], t[80000];

int main() {
    freopen("ghiozdan.in", "r", stdin);
    freopen("ghiozdan.out", "w", stdout);
    long i, j, k;
    scanf("%ld%ld", &n, &s);
    for (i = 0; i < n; ++i) {
        scanf("%ld", &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;
    long 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("%ld %ld\n", s, best[s]);
    while (s) {
		printf("%ld\n", t[s]);
		s -= t[s];
	}
    return 0;
}