Cod sursa(job #409560)

Utilizator xtephanFodor Stefan xtephan Data 3 martie 2010 18:46:26
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>
#include<algorithm>
#define INF 0x3f3f3f3f

using namespace std;

long long n,S,T;
long long C[100002], P[100002];
long long L[100002];


void cit();
void rez();
void afis();

int main() {
	
	freopen("branza.in", "r", stdin);
	freopen("branza.out", "w", stdout);
	
	cit();
	rez();
	afis();
	
	return 0;
}


void cit() {
	scanf("%lld%lld%lld", &n,&S,&T);
	
	for(int i=1; i<=n; i++)
		scanf("%lld%lld", &C[i], &P[i]);
}


void rez() {
	
	long i,j;
	
	int Deque[100002];
	int inc=1,sf=1;
	
	L[1]=C[1];
	Deque[1]=1;
	
	for(i=2; i<=n; i++) {
		
		int stric=1;
		
		while( C[i] <= C[Deque[sf]]+stric*S && inc<=sf )
			sf--,stric++;

		Deque[++sf]=i;

		L[i]= C[ Deque[inc] ] + (i-Deque[inc])*S;
		
		if(i-Deque[inc]==T)
			inc++;
		
	}
	
}


void afis() {
	long long tot=0;
	
	for(long i=1; i<=n; i++)
		tot+=P[i]*L[i];
	
	printf("%lld", tot);
}