Cod sursa(job #497243)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 1 noiembrie 2010 21:43:44
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include <cstdio>
#define nmax 100010

int c[nmax], p[nmax], v[nmax], q[nmax], n, s, t;
long long sol;

int main()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%d %d %d",&n,&s,&t);
	int i, st, dr, j;
	for (i=1; i<=n; i++) scanf("%d %d",&c[i],&p[i]);
	st=1;
	dr=0;
	for (i=1; i<=n; i++) 
	{
		while (st<=dr && c[i]+(n-i)*s<c[q[dr]]+(n-q[dr])*s) 
			dr--;
		while (q[st]+t<i && st<=dr) st++;
		q[++dr]=i;
		v[i]=c[q[st]]+(i-q[st])*s;
	}
	for (i=1; i<=n; i++) sol+=(long long) p[i]*v[i];
	printf("%lld\n",sol);
}