Cod sursa(job #31483)

Utilizator razvi9Jurca Razvan razvi9 Data 16 martie 2007 09:15:49
Problema Ghiozdan Scor 54
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.5 kb
#include<stdio.h>
int g[75001],s[75001],n,G,gmax,a,i,j;
void sol(int G)
{if(G==0) return;
 sol(G-s[G]);
 printf("%d\n",s[G]);
}
int main()
{freopen("ghiozdan.in","r",stdin);
 freopen("ghiozdan.out","w",stdout);
 scanf("%d %d",&n,&G);
 for(i=1;i<=n;i++)
 {scanf("%d",&a);
  for(j=gmax;j>=0;j--)
  if(j+a<=G&&(g[j]||j==0))
   if(g[j+a]>g[j]+1||!g[j+a]) 
   {g[j+a]=g[j]+1;
    s[j+a]=a;
    if(j+a>gmax) gmax=j+a;}
  }
 printf("%d %d\n",gmax,g[gmax]);
 sol(gmax);
 fclose(stdout);
 return 0;}