Cod sursa(job #368412)

Utilizator MKLOLDragos Ristache MKLOL Data 24 noiembrie 2009 20:56:27
Problema Energii Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<stdio.h>
int b[5012000],N,S,G,ifin=99999999,W,v[1011],l[1011],max;
int main()
{
freopen("energii.in","r",stdin);
freopen("energii.out","w",stdout);
scanf("%d%d",&N,&S);
for(int i=1;i<=N;++i)
{
    scanf("%d%d",&v[i],&l[i]);
}
for(int i=1;i<=5000111;++i)
{
b[i]=9999999;
}
max=0;
for(int i=1;i<=N;++i)
    {
    for(int j=max;j>=0;--j)
    {
        if(b[j]!=9999999)
        {
        if(b[j+v[i]]>b[j]+l[i])
        b[j+v[i]]=b[j]+l[i];
        if(j+v[i]>max)
        max=j+v[i];
        }
    }
    }


for(int i=S;i<=5000000;++i)
{
    if(b[i]<ifin)
    ifin=b[i];
}
printf("%d\n",ifin);
return 0;
}