Cod sursa(job #741170)
Utilizator | Pavel Ana-Oriana Pavel | Data | 25 aprilie 2012 16:13:46 |
---|---|---|---|
Problema | Energii | Scor | 95 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.51 kb |
#include<fstream>
using namespace std;
ifstream in("energii.in");
ofstream out("energii.out");
int e[10001],c[10001],v[15001];
int main()
{
int i,j,g,w,q;
in>>g>>w;
for(i=1;i<=g;i++)
in>>e[i]>>c[i];
for(i=1;i<=15000;i++)
v[i]=1000000000;
for(i=1;i<=g;i++)
for(j=w;j>=0;j--)
if(v[j] != 1000000000 && v[j]+c[i] < v[j+e[i]])
v[j+e[i]]=v[j]+c[i];
q=1000000001;
for(i=w;i<=15000;i++)
if(v[i]<q)
q=v[i];
if(q == 1000000001)
out<<"-1\n";
else
out<<q<<'\n';
return 0;
}