Cod sursa(job #1174298)
Utilizator | Data | 22 aprilie 2014 14:56:51 | |
---|---|---|---|
Problema | Energii | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.6 kb |
#include<fstream>
using namespace std;
ifstream in("energii.in");
ofstream out("energii.out");
int E[1002],C[1002],a[1002],b[1002],N,G;
int main()
{
in>>N>>G;
int i,j;
for(i = 1 ; i <= N ; i++)
in>>E[i]>>C[i];
for(i = 1 ; i <= G ; i++)
b[i] = 20000;
for(i = 1 ; i <= N ; i++)
{
for( j = 1 ; j <= G ; j++)
{
if(E[i] >= j) a[j] = min(C[i],b[i]);
else a[j] = min(b[i],b[j-E[i]]+C[i]);
}
for(j = 1 ; j <= G ; j++)
b[i] = a[i];
}
if(a[N] == 20000) out<<-1;
else out<<a[G];
return 0;
}