Cod sursa(job #2803720)
| Utilizator | Data | 20 noiembrie 2021 13:03:13 | |
|---|---|---|---|
| Problema | Energii | Scor | 95 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 0.58 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;
}
}
}
fout<<mi;
return 0;
}
