Cod sursa(job #549212)

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

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

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

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

		rez += min;
	}

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

	return 0;
}