Pagini recente » Formatare Textile | Cod sursa (job #3269559) | Cod sursa (job #25575) | Cod sursa (job #2643727) | Cod sursa (job #216784)
Cod sursa(job #216784)
#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;
}