Pagini recente » Cod sursa (job #2014213) | Cod sursa (job #1995146) | Cod sursa (job #1708626) | Cod sursa (job #52543) | Cod sursa (job #54480)
Cod sursa(job #54480)
#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;
}