Cod sursa(job #140546)

Utilizator za_wolfpalianos cristian za_wolf Data 21 februarie 2008 22:55:35
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<stdio.h>
#define NMAX 100101
long i,in,sf,j,a,poz,max,s,n,b,k,m,rez,y[NMAX];
struct deque
{
	long I,C;
};
deque q[NMAX];
struct kkt
{
	long C,X;
};
kkt x[NMAX];
int main()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%ld%ld%ld",&n,&s,&k);
	for (i=1;i<=n;i++)
		scanf("%ld%ld",&x[i].C,&x[i].X);
	rez=x[1].C*x[1].X;
	in=1;
	sf=0;
/*	q[1].I=1;
	q[1].C=x[1].C+(n-1)*s; */
	for (i=1;i<=n;i++)
	{
		while (in<=sf&&i-q[in].I>=k)
			in++;
		while (in<=sf&&q[sf].C>x[i].C+(n-i)*s)
			sf--;
		q[++sf].C=x[i].C+(n-i)*s;
		q[sf].I=i;
		y[i]=q[in].C-(n-q[in].I)*s;
	}
	for (i=2;i<=n;i++)
	{
		if (y[i]==y[i+1])
		{
			a=0;
			j=i;
			while (y[i]==y[i+1])
			{
				a+=(x[i+1].X)*(i+1-j);
				b+=x[i+1].X;
				i++;
			}
			rez+=a*s;
			rez+=(b+x[j].X)*x[j].C;
		} else
		rez+=y[i]*x[i].X;
	}
	printf("%ld\n",rez);



	return 0;
}