Cod sursa(job #140624)

Utilizator za_wolfpalianos cristian za_wolf Data 22 februarie 2008 00:37:46
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<stdio.h>
#define NMAX 101000
long long z[NMAX],i,in,sf,j,a,poz,max,s,n,b,k,m,rez,y[NMAX];
struct deque
{
	long long I,C;
};
deque q[NMAX],aux;
struct kkt
{
	long long C,X;
};
kkt x[NMAX];
int main()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%lld%lld%lld",&n,&s,&k);
	for (i=1;i<=n;i++)
		scanf("%lld%lld",&x[i].C,&x[i].X);
	in=1;
	sf=0;
	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;
		z[i]=q[in].I;

	}

	for (i=1;i<=n;i++)
		rez+=y[i]*x[i].X+(i-z[i])*s*x[i].X;

	printf("%lld\n",rez);



	return 0;
}