Cod sursa(job #708608)

Utilizator misinoonisim necula misino Data 6 martie 2012 23:08:34
Problema Energii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream> 
using namespace std;
ifstream f("energii.in");
ofstream g("energii.out"); 
int   N, S, v[1001], cost[5001]; 
int   c[5001]; 
int   Minim = 999999999; 
int main(void) 
{ int i, j; 
 f >> N >> S; 
 for (int k=1; k<=N; ++k) 
 f >> v[k] >> cost[k];   
 
for (j=1; j<=S; ++j) c[j] = -1; 
c[0] = 0; 
for (i=1; i<=N; ++i) 
for (j=S; j>=0; --j)        
if (c[j] != -1) 
{if (j + v[i] > S) 
   if (Minim > c[j] + cost[i]) 
Minim = c[j] + cost[i];              
if (j + v[i] <= S)
if (c[j + v[i]] > c[j] + cost[i] || c[j + v[i]] == -1)
c[j + v[i]] = c[j] + cost[i];
}
if (Minim == 999999999) 
	g << -1; 
else
	if(Minim<c[S])
		g<<Minim;
	else
		if(c[S]==-1)
			g<<Minim;
		else
			g<<c[S];

g.close(); 
return 0; 
}