Cod sursa(job #832302)
Utilizator | Data | 10 decembrie 2012 12:21:14 | |
---|---|---|---|
Problema | Energii | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.87 kb |
#include<stdio.h>
#define INF 2000000000
int w[10002];
int main(){
freopen("energii.in","r",stdin);
freopen("energii.out","w",stdout);
int n,wmin,g,e,smax=0;
scanf("%d%d",&n,&wmin);
w[0]=0;
for(int i=1;i<=10002;i++){
w[i]=INF;
}
for(int i=1;i<=n;i++){
scanf("%d%d",&e,&g);
for(int j=smax;j>=0;j--){
if(w[j]!=INF){
if(j+e>=wmin){
if(w[j]+e<w[wmin]){
w[wmin]=w[j]+g;
}
}
else{
if(w[j+e]>w[j]+g){
w[j+e]=w[j]+g;
}
}
smax=smax+e;
if(smax>wmin){
smax=wmin;
}
}
}
}
printf("%d\n",w[wmin]);
return 0;
}