Cod sursa(job #1267629)
| Utilizator | Data | 20 noiembrie 2014 02:29:22 | |
|---|---|---|---|
| Problema | Energii | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.53 kb |
#include <fstream>
using namespace std;
int e[15000],c[15000],v[15000];
int s,i,j,n,sum,g,sol=100000;
ifstream in("energii.in");
ofstream out("energii.out");
int main(){
in>>n>>g;
for (i=1;i<=n;i++){
in>>e[i]>>c[i];
if (s<e[i]) s=e[i];
sum+=e[i];
}
if (sum<g) out<<"-1";
else{
for(i=1;i<=g+s;i++)
v[i]=100000;
v[0]=0;
for (i=1;i<=n;i++)
for (j=g-1;j>=0;j--)
if ((v[j]!=100000)&&(v[j+e[i]]>v[j]+c[i])) v[j+e[i]]=v[j]+c[i];
for (i=g;i<=g+s;i++)
if(v[i]<sol) sol=v[i];
out<<sol;
}
}
