Cod sursa(job #385624)

Utilizator nightwish0031Vlad Radu Cristian nightwish0031 Data 23 ianuarie 2010 10:37:40
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include<cstdio>
const int N=1<<20;

int k;
int dq[N];
int s;
int st,dr;
int x[N],y[N];

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

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

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