Cod sursa(job #300820)

Utilizator ilincaSorescu Ilinca ilinca Data 7 aprilie 2009 18:29:19
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <stdio.h>

#define nmax 100025
#define pr(x) fprintf(stderr, #x" = %d\n",x)

int n, t, s, c [nmax], p [nmax];


void scan ()
{
	int i;
	scanf ("%d%d%d", &n, &s, &t);
	for (i=1; i <= n; ++i)
		scanf ("%d%d", &c [i], &p [i]);
}

long long res ()
{
	long long r;
	int i, st=1, dr=1, dq [nmax];
	dq [st]=1;
	r=c [1]*p [1];
	//pr(r);
	for (i=2; i <= n; ++i)
	{
		while ((i-dq [st] >= t) && st <= dr) ++st;
		while (st<=dr && (c [i] <= c [dq [dr]]+(i-dq [dr])*s)) --dr;
		dq [++dr]=i;
		r+=(long long)(c [dq [st]]+(i-dq [st])*s)*p [i];
		/*pr(i);
		pr(dq[st]);
		pr(dq[dr]);
		pr(r);*/
	}
	return r;
}

int main ()
{
	freopen ("branza.in", "r", stdin);
	freopen ("branza.out", "w", stdout);
	scan ();
	printf ("%Ld\n", res ());
	return 0;
}