Cod sursa(job #1325196)
Utilizator | Mihailescu Vlad Tiberiu VladTiberiu | Data | 23 ianuarie 2015 15:04:10 |
---|---|---|---|
Problema | Energii | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.6 kb |
#include <fstream>
using namespace std;
ifstream f("energii.in");
ofstream g("energii.out");
struct asd{
int g,p;
}a[1010];
long long d[10000008],N,G,i,j,s;
int main()
{
f >> N >> G;
for(i = 1; i <= N; i++){
f >> a[i].p >> a[i].g;
//s += a[i].g;
}
for(i = 1; i <= N; i++){
for(j = 2*G; j >= a[i].g; j--){
d[j] = max(d[j],d[j-a[i].g] + a[i].p);
}
}
for(i = 1; i <= 2*G; i++){
// g << d[i] <<" ";
if(d[i] >= G){
g << i;
return 0;
}
}
g << -1;
return 0;
}