Cod sursa(job #383404)

Utilizator pirvupirvu tudor pirvu Data 16 ianuarie 2010 14:55:29
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<cstdio>

int n,s,t,i,st,dr,numar;

long long sum;

int dq[5000001];

int c[100001],p[100001];

inline void stanga(int i)
{
	if (dq[st]==i-t)
      ++st;
}

void dreapta (int i)
{
	while(st<=dr && p[i]<=p[dq[dr]] + s*(i-dq[dr]) )
		--dr;

	dq[++dr]=i;
}


int main()
{
	
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	
	scanf("%d%d%d", &n , &s , &t);
	
	for (i=1;i<=n;i++)
		scanf("%d%d", &p[i], &c[i]);
	
	st=1;
	
	
	for (i=1;i<=n;i++)
	{
		stanga(i);
		dreapta(i);
		sum+=  (long long)c[i]*(p[dq[st]] + s*(i-dq[st]));
	}
	
	printf("%lld", sum);

	
	
	return 0;

}