Cod sursa(job #159603)

Utilizator nicucelviteazniculcioiu andrei nicucelviteaz Data 14 martie 2008 11:41:09
Problema Energii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<stdio.h>
int e,n,i,j,max,min;
int b[1000000],energ[1002],c[1000000],cost[1002];
int main(void)
{
	freopen("energii.in","r",stdin);
	freopen("energii.out","w",stdout);
	scanf("%d%d",&n,&e);
	for(i=1;i<=n;i++)
		scanf("%d%d",&energ[i],&cost[i]);
	max=0;
	c[0]=0;
	b[0]=1;
	for(i=1;i<=n;i++)
		for(j=max;j>=0;j--)
			if(b[j]&&j<e)
			{
				if(b[j+energ[i]]==0)
				{
					b[j+energ[i]]=1;
					c[j+energ[i]]=c[j]+cost[i];
					if(j+energ[i]>max)
						max=j+energ[i];
				}
				else
					if(c[j]+cost[i]<c[j+energ[i]])
						c[j+energ[i]]=c[j]+cost[i];
			}
		  min=32000;
	for(i=max;i>=e;i--)
	{
		if(b[i])
		if(c[i]<min)
		min=c[i];
	}	
	if(min!=32000)
		printf("%d\n",min);
	else
		printf("-1\n");
	return 0;
}