Cod sursa(job #825600)

Utilizator crushackPopescu Silviu crushack Data 29 noiembrie 2012 11:43:09
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
#include <deque>
#define NMax 100010
using namespace std;

typedef long long ll;
const char IN[]="branza.in",OUT[]="branza.out";

int N,S,T;
ll P[NMax],C[NMax];
ll D[NMax];
deque<int> d;

void add(int x)
{
	while (!d.empty() && (x-d.back()>T || C[x]-S*x<C[d.back()]-S*d.back()))
		d.pop_back();
	d.push_back(x);
	while (!d.empty() && (x-d.front()>T))
		d.pop_front();
}

void solve()
{
	int i;
	D[1]=P[1]*C[1];
	add(1);
	for (i=2;i<=N;++i)
	{
		add(i);
		D[i]=D[i-1]+P[i]*S*i+P[i]*(C[d.front()]-S*d.front());
	}
}

int main()
{
	int i,p,c;
	freopen(IN,"r",stdin);
	scanf("%d%d%d",&N,&S,&T);
	for (i=1;i<=N;++i) scanf("%d%d",&c,&p),P[i]=p,C[i]=c;
	fclose(stdin);

	solve();

	freopen(OUT,"w",stdout);
	printf("%lld\n",D[N]);
	fclose(stdout);
	return 0;
}