Cod sursa(job #549232)

Utilizator cosmyoPaunel Cosmin cosmyo Data 8 martie 2011 11:38:38
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <cstdio>
using namespace std;
const int N = 100005;
long long P[N], C[N], d[N], n, S, T;

int main() {
	freopen("branza.in", "r", stdin);
	freopen("branza.out", "w", stdout);
	long long  i, front = 1, back = 0;
	long long rez = 0, min;
	scanf("%lld %lld %lld", &n, &S, &T);
	for(i = 1; i <= n; ++i)
		scanf("%lld %lld", &C[i], &P[i]);

	for(i = 1; i <= n; ++i) {
		min = P[i] * C[i];
		
		if(front <= back &&  (C[d[front]] - S * d[front] + S * i) * P[i] < min)
			min = (C[d[front]] - S * d[front] + S * i) * P[i];
		
		while(d[back] - d[front] + 1 >= T)
			++front;

		while(front <= back &&  C[i] - S * i <= C[d[back]] - S * d[back])
			--back;
		d[++back] = i;

		rez += min;
	}

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

	return 0;
}