Cod sursa(job #2394649)
Utilizator | Data | 1 aprilie 2019 19:22:14 | |
---|---|---|---|
Problema | Energii | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.63 kb |
#include <fstream>
#define e first
#define c second
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
int i,j,W,G,total,maxi,sol,sc,D[10000001];
pair<int,int> v[1001];
int main(){
fin>>G>>W;
for(i=1;i<=G;i++){
fin>>v[i].e>>v[i].c;
total+=v[i].e;
}
if(total<W){fout<<-1;return 0;}
for(i=1;i<=total;i++)D[i]=1000000000;
for(i=1;i<=G;i++)
for(j=W;j>=0;j--){
sc=j+v[i].e;
if(D[j]!=-1){
if(sc>=W)sc=W;
D[sc]=min(D[sc],D[j]+v[i].c);
}
}
fout<<D[W];
return 0;
}