Cod sursa(job #380480)

Utilizator DeadEyeNaiba Mihai Lucian DeadEye Data 6 ianuarie 2010 11:29:15
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<cstdio>
long long n,k,s,st,dr,a[100001],dq[100001],cc[100001];
long long ss; long long nr;
inline void elimst(long long i)
{
	if(i-dq[st]==k)
		++st;
}
void elimdr(long long i)
{
	while(st<=dr && a[dq[dr]]+(i-dq[dr])*s>=a[i])
		--dr;
	dq[++dr]=i;
}
int main()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%lld%lld%lld",&n,&s,&k);
	++k;
	for(long long i=1;i<=n;++i)
		scanf("%lld%lld",&a[i],&cc[i]);
	dq[1]=1;
	nr=a[1]*cc[1];
	st=1; dr=1;
	for(long long i=2;i<=n;++i)
	{
		elimst(i);
		elimdr(i);
		nr=nr+(a[dq[st]]+(i-dq[st])*s)*cc[i];
	}
	printf("%lld\n",nr);
	return 0;
}