Cod sursa(job #138016)

Utilizator savimSerban Andrei Stan savim Data 17 februarie 2008 19:39:49
Problema Energii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <stdio.h>
long long i,j,n,s,min;
long long a[5010][2],b[5010][2],g[5010][2];

int main()
{
    
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    scanf("%lld",&n);
    scanf("%lld",&s);    

	min=4000000001;
	for (i=1; i<=n; i++)
		scanf("%lld%lld",&g[i][0],&g[i][1]);

	for (i=1; i<=5001; i++)
		a[i][1]=4000000001;
	a[0][0]=1;
	for (i=1; i<=n; i++)
	{
		for (j=1; j<=s; j++)
		{
			a[j][0]=b[j][0];
			if (b[j][1]!=0) a[j][1]=b[j][1];
		}
		for (j=0; j<=s; j++)
			if (a[j][0]!=0)
			{
			   if (j+g[i][0]>=s && a[j][1]+g[i][1]<min) min=a[j][1]+g[i][1];
			   if (j+g[i][0]<s && a[j][1]+g[i][1]<a[j+g[i][0]][1])
			   {
					b[j+g[i][0]][1]=a[j][1]+g[i][1];
					b[j+g[i][0]][0]=1;
			   }
			}
	}
	if (min!=4000000001) printf("%lld\n",min);
    else printf("-1\n");
        
    return 0;    
}