Cod sursa(job #74665)

Utilizator wefgefAndrei Grigorean wefgef Data 26 iulie 2007 21:18:35
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.52 kb
#include <cstdio>

#define Nmax 100005

int n;
long long s, t;
long long c[Nmax];
int Q[Nmax], qe, qb;
long long ret;

int main()
{
	freopen("branza.in", "r", stdin);
	freopen("branza.out", "w", stdout);

	int i;
	long long need;

	scanf("%d %lld %lld", &n, &s, &t);
	
	qe = 0; qb = 1;
	for (i = 1; i <= n; ++i)
	{
		scanf("%lld %lld", &c[i], &need);
		while (qe >= qb && (i-Q[qe])*s + c[Q[qe]] >= c[i]) --qe;
		Q[++qe] = i;
		if (i-Q[qb] == t) ++qb;
		ret += need*(c[Q[qb]] + (i-Q[qb])*s);
	}

	printf("%lld\n", ret);

	return 0;
}