Cod sursa(job #383242)

Utilizator Teodor94Teodor Plop Teodor94 Data 16 ianuarie 2010 09:55:20
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.56 kb
#include<cstdio>

const int N=1<<17;

int c[N],p[N],dq[N],t,s,st=1,dr=1;

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

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

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