Cod sursa(job #1401223)
Utilizator | Zaharia Stefan Tudor stefzah | Data | 25 martie 2015 18:31:45 |
---|---|---|---|
Problema | Energii | Scor | 85 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.58 kb |
#include <cstdio>
#include <algorithm>
using namespace std;
int Gmax,n,a[2][10000001],g[1001],v[1001],i,j,k;
int main()
{freopen("energii.in","r",stdin);
freopen("energii.out","w",stdout);
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
{scanf("%d%d",&v[i],&g[i]);
Gmax=Gmax+g[i];
}
for(i=1;i<=n;i++)
{for(j=1;j<=Gmax;j++)
{if(g[i]>j) a[1][j]=a[0][j];
else{a[1][j]=max(a[0][j],v[i]+a[0][j-g[i]]);
}
if((a[1][j]>=k)&&(j<Gmax)) Gmax=j;
}
for(j=1;j<=Gmax;j++)
a[0][j]=a[1][j];
}
printf("%d",Gmax);
}