Cod sursa(job #2182406)
Utilizator | Data | 22 martie 2018 12:49:00 | |
---|---|---|---|
Problema | Cel mai lung subsir comun | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include <iostream>
#include <fstream>
using namespace std;
int g, w, i, j, a[1001], b[1001], d[5001];
int main(){
ifstream in("energii.in");
ofstream out("energii.out");
in >> g >> w;
for(i = 1; i <= g; i++)
in >> a[i] >> b[i];
for(i = 1; i <= w; i++)
d[i] = 1e9;
for(i = 1; i <= g; i++)
for(j = w; j >= 1; j--)
if(j < a[i])
d[j] = min(d[j], b[i]);
else
d[j] = min(d[j], d[j - a[i]] + b[i]);
if(d[w] != 1e9)
out << d[w];
else
out << "-1";
return 0;
}