Cod sursa(job #847581)
Utilizator | Dumitrascu Mihai dumitrascumihai | Data | 4 ianuarie 2013 11:26:04 |
---|---|---|---|
Problema | Energii | Scor | 55 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.49 kb |
#include <fstream>
using namespace std;
const int a=2000000000;
int main()
{
int v[500002], G, W, vmin=a,eg[10002],cg[10002];
int i, j;
ifstream f("energii.in");
ofstream g("energii.out");
f>>G>>W;
for(i=1;i<=G;i++)
f>>eg[i]>>cg[i];
for(i=1;i<5002;i++)
v[i]=a;
v[0]=0;
for(i=1;i<=G;i++)
for(j=W;j>=0;j--)
if(v[j]!=a && v[j+eg[i]]>v[j]+cg[i])
v[j+eg[i]]=v[j]+cg[i];
for(i=W;i<5001;i++)
if(v[i]<vmin)
vmin=v[i];
if(vmin!=a)
g<<vmin;
else
g<<"-1";
return 0;
}