Cod sursa(job #537002)

Utilizator ConsstantinTabacu Raul Consstantin Data 19 februarie 2011 21:07:28
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<stdio.h>
#include<deque>
#define Nmax  100010
using namespace std;

deque<long long int>  d;

long long int p[ Nmax ] , C[ Nmax ],i,j,k,l,m,n,t,s,sol;

void citire(){
freopen("branza.in","r",stdin);
scanf("%lld %lld %lld",&n,&s,&t);
for(i = 1 ; i <= n ;  i++)
	scanf("%lld %lld",&C[i],&p[ i ]);

}
void solve(){
long long int i,x;
sol = C[1]*p[1];
d.push_front(1);

for(i = 2 ; i <= n; i++)
	{x =  d.front();
	while((s * ( i - x)+ C[x]) > C[i]) 
		{d.pop_front();
		if(d.size())
			x = d.front();
		else
			break;
		}
	d.push_front(i);
	
	x = d.back();
	if((i-x) > t)
		d.pop_back();
	
	x = d.back();
	
	sol += C[x]*p[i] + s * (i-x)*p[i];
	
	}
	
}

void afisare(){
freopen("branza.out","w",stdout);
printf("%lld",sol);

}


int main(){

citire();
solve();
afisare();

return 0;}