Cod sursa(job #1358232)
Utilizator | Data | 24 februarie 2015 14:38:56 | |
---|---|---|---|
Problema | Energii | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.68 kb |
#include <fstream>
#include <limits.h>
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
int g,w,a[1001],b[5001],d[10001],i,j,Cmin,ok;
int main()
{
fin>>g>>w;
for(i=1;i<=g;i++)
fin>>a[i]>>b[i];
for (i=1;i<=w;i++)
d[i]=INT_MAX;
d[0]=0;
for(i=1;i<=g;i++)
for (j=w;j>=0;j--)
if(d[j]!=INT_MAX)
if(j+a[i]>w)
{if(d[w]>d[j]+b[i])
d[w]=d[j]+b[i];
}
else
if (d[j+a[i]] > d[j]+b[i])
d[j+a[i]]=d[j]+b[i];
if (d[w]!=INT_MAX)
fout <<d[w];
else
fout <<-1;
return 0;
}