Cod sursa(job #148004)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 3 martie 2008 20:09:35
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <stdio.h>
#include <math.h>

long long aux, i, n, cost, t, first, last, k, nr1, nr2, suma, dq[100010], dqa[100010];

void add() {
	aux -= cost;
	k = nr1 + aux;
}

int main() {
	freopen("branza.in", "r", stdin);
	freopen("branza.out", "w", stdout);
	
	scanf("%lld %lld %lld\n", &n, &cost, &t);
	dq[1] = 2000000000;
	dq[1] = dq[1] * dq[1];
	aux = n * cost;	
	first = 1;
	last = 1;
	for (i = 1; i <= n; ++i) {
		scanf("%lld %lld\n", &nr1, &nr2);
		add();
		while (dq[last] > k) {
			--last;
		}
		++last;
		dq[last] = k;
		dqa[last] = i + t + 1;
		if (dqa[first] <= i) {
			++first;
		}
		suma += (dq[first] - aux) * nr2;
	}
	printf("%lld\n", suma);
	return 0;
}