Cod sursa(job #462016)

Utilizator HoriaClementHoriaC HoriaClement Data 9 iunie 2010 15:39:17
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <cstdio>

int n,s,t,p[1<<17],c[1<<17],dq[1<<17],st=1,dr=0;
long long sum;

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