Cod sursa(job #2192194)
Utilizator | Digori Parascovia Digori04 | Data | 4 aprilie 2018 22:20:03 |
---|---|---|---|
Problema | Ghiozdan | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.65 kb |
#include<bits/stdc++.h>
using namespace std;
ifstream fin("ghiozdan.in");
ofstream fout("ghiozdan.out");
int n,g,x,dp[100005],v[1005],t[100005],i,w,j;
int main()
{
fin>>n>>g;
for(i=1;i<=n;++i)fin>>x,v[x]++;
dp[0]=1;
for(w=200;w>=1;w--)
{
if(v[w])
{
for(i=g-w;i>=0;i--)
{
if(dp[i])
{
for(j=1;j<=v[w] && i+j*w<=g && !dp[i+j*w];j++)
{
dp[i+j*w]=dp[i]+j;
t[i+j*w]=w;
}
}
}
}
}
for(i=g;i>=1;i--)
if(dp[i])
{
fout<<i<<" "<<dp[i]-1<<endl;
while(i)
{
fout<<t[i]<<endl;
i-=t[i];
}
break;
}
return 0;
}