Cod sursa(job #770903)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("energii.in");
ofstream g("energii.out");
#define nmax 1005
#define Gmax 5005
int n, G, energie[nmax], cost[nmax], dp[nmax][Gmax];
void citeste(){
f >> n >> G;
for(int i=1; i<=n; i++) f >> energie[i] >> cost[i];
}
void rezolva(){
//dp[i][j] = costul minim de a obtine j energie din primii i generatori
for(int i=0; i<nmax; i++)
for(int j=1; j<Gmax; j++) dp[i][j] = (1<<30);
//coloana cu 0 o las cu val 0
dp[0][0] = 0;
for(int i=1; i<=n; i++){
for(int j=0; j<=G; j++){
dp[i][j] = dp[i-1][j];//nu adaug generatorul i;
//dar daca energie[i] > j atunci il pot face pe j cu ajutorul lui i
if (j < energie[i]) dp[i][j] = min(dp[i][j], cost[i]);
if (j >= energie[i]){//adaug generatorul i
dp[i][j] = min(dp[i][j], dp[i-1][j-energie[i]] + cost[i]);
}
}
}
if (dp[n][G] != (1<<30) ) g << dp[n][G] << "\n";
else g << "-1" << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}