Cod sursa(job #2803722)
| Utilizator | Data | 20 noiembrie 2021 13:06:09 | |
|---|---|---|---|
| Problema | Energii | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 0.64 kb |
#include <fstream>
using namespace std;
int d[50005];
ifstream fin("energii.in");
ofstream fout("energii.out");
int main()
{
int n,g,i,p,c,j,mi=1000005;
fin>>n>>g;
for(i=1;i<=g;++i){
d[i]=-1;
}
for(i=1;i<=n;++i){
fin>>c>>p;
for(j=g;j>=g-c;--j){
if(d[j]!=-1 && d[j]+p<mi){
mi=d[j]+p;
}
}
for(j=g-c-1;j>=0;--j){
if(d[j]!=-1 && (d[j+c]==-1 || d[j+c]>d[j]+p)){
d[j+c]=d[j]+p;
}
}
}
if(mi==1000005){
fout<<"-1";
} else {
fout<<mi;
}
return 0;
}
