Cod sursa(job #114436)

Utilizator andrei.12Andrei Parvu andrei.12 Data 14 decembrie 2007 10:17:41
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<stdio.h>
long long n, cs, t, i, first, last, cost, nr;
long long rezultat;
struct deque{
	long long v, i;
};
deque q[100005];
int main()
{
	freopen("branza.in", "rt", stdin);
	freopen("branza.out", "wt", stdout);
	scanf("%lld%lld%lld", &n, &cs, &t);
	rezultat = 0;
	first = 1, last = 0;
	for (i=1; i<=n; i++){
		scanf("%lld%lld", &cost, &nr);
		while (first <= last && q[first].i + t < i)
			first ++;
		while (first <= last && nr*(q[last].v + (i-q[last].i)*cs) > nr*cost)
			last --;
		q[++last].v = cost;
		q[last].i = i;
		rezultat += nr*(q[first].v + (i-q[first].i)*cs);
	}
	printf("%lld\n", rezultat);
	fclose(stdin);
	fclose(stdout);
	return 0;
}