Cod sursa(job #271658)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 5 martie 2009 19:15:18
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>

const int N_MAX = 100010;

int C[N_MAX], P[N_MAX], din[N_MAX];

struct deque {
	int el, val;
} dq[N_MAX];

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

	int N, S, T;
	scanf("%d %d %d\n", &N, &S, &T);
	for (int i = 1; i <= N; i ++) {
		scanf("%d %d\n", &C[i], &P[i]);
	}
	din[1] = C[1];
	int in = 1, sf = 1;
	dq[1].val = C[1] + (N - 1) * S;
	dq[1].el = 1;

	for (int i = 2; i <= N; i ++) {
		while (i - dq[in].el > T) in ++;
		while (sf >= in && (C[i] + (N - i) * S < dq[sf].val)) sf --;

		dq[++ sf].val = C[i] + (N - i) * S;
		dq[sf].el = i;

		din[i] = dq[in].val - (N - i) * S;
	}

	long long rez = 0;
	for (int i = 1; i <= N; i ++) {
		rez += (long long) P[i] * din[i];
	}
	printf("%lld\n", rez);

	return 0;
}