Cod sursa(job #380475)

Utilizator Adela_BaciuAdela Baciu Adela_Baciu Data 6 ianuarie 2010 11:27:36
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include<cstdio>
int s,k,n,st,dr,v[1000010],dq[100010],c[100010];
long long nr;
inline void stanga (int i)
{
	if(i-dq[st]==k)
		++st;
}
void dreapta(int i)
{
	while(st<=dr&&v[dq[dr]]+(i-dq[dr])*s>=v[i])
		--dr;
	dq[++dr]=i;
}

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