Cod sursa(job #459991)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 31 mai 2010 21:39:06
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <cstdio>

#define nmax 100010
#define ll long long
using namespace std;

ll dp[nmax], sol;
ll cant[nmax], cost[nmax], i, j;
ll N, S, T, front, back;
ll D[nmax];
int main () {
	freopen ("branza.in", "r", stdin);
	freopen ("branza.out", "w", stdout);
	scanf ("%lld%lld%lld\n", &N, &S, &T);
	for (i = 1; i <= N; i++) scanf ("%lld%lld\n", &cost[i], &cant[i]);
	dp[1] = cost[1];
	front = 1; back = 0;
	for (i = 1; i <= N; i++) {
		dp[i] = cost[i];
		while (front <= back && dp[i] <= dp[ D[back] ] + (i - D[back]) * S) --back;
		D[++back] = i;
		dp[i] = dp[ D[front] ] + (i - D[front]) * S * 1LL;
		if (D[front] == i - T) ++front;
	}
	for (i = 1; i <= N; i++) {
		sol += 1LL * cant[i] * dp[i];
	}
	printf ("%lld\n", sol);
	return 0;
}