Cod sursa(job #731796)
Utilizator | Data | 9 aprilie 2012 11:18:51 | |
---|---|---|---|
Problema | Energii | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.6 kb |
#include<cstdio>
#include<algorithm>
using namespace std;
int mat[3][5010];
int main()
{
int i,n,c,e,a=1,b=2,E,s;
freopen("energii.in","r",stdin);
freopen("energii.out","w",stdout);
scanf("%d %d",&n,&s);
for(i=0;i<=s;i++) mat[1][i]=1<<31-1;
for(i=1;i<=n;i++)
{
scanf("%d %d",&e,&c);
for(E=1;E<=s;E++)
{
if(E<=e) mat[b][E]=min(mat[a][E],c);
else mat[b][E]=min(mat[a][E],mat[a][E-e]+c);
}
swap(a,b);
}
if(mat[a][s]!=1<<31-1) printf("%d",mat[a][s]);
else printf("-1");
return 0;
}