Cod sursa(job #120155)

Utilizator alexeiIacob Radu alexei Data 4 ianuarie 2008 13:42:09
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<stdio.h>
#define NMAX 100000
#define INF 20000000
typedef struct 
{
	long long c,p;
}heap; 
heap h[NMAX+1];
long long s;
inline long long compar(heap x,heap y){
	if(s*(x.p-y.p)+y.c>x.c)
		return -1;
	if(s*(x.p-y.p)+y.c<x.c)
		return 1;
	return 0;
}
void adaugare(long long m)
{
	heap aux=h[m];
	while(compar(aux,h[m/2])<=0&&m>=2)
	{
		h[m]=h[m/2];
		m/=2;
	}
	h[m]=aux;
}
/*
void scrie(long long i)
{
	for(long long j=1; j<=i; j++)
		printf("(%d,%d) ",h[j].c,h[j].p);
	printf("\n");
}
*/
inline long long minim(long long x,long long y)
{
	if(compar(h[x],h[y])<=0)
		return x;
	return y;
}
void elimin(long long &m)
{
	heap aux=h[m];
	long long min,k=1,k1=minim(2*k,2*k+1);
	/*
	while(k*2+1<=NMAX&&compar(aux,h[min=minim(k*2,k*2+1)])>0){
		h[k]=h[min];
		k=min;
	}
	
	while((k*2<m&&compar(aux,h[k*2])>0)||(k*2+1<m&&compar(aux,h[k*2+1])>0)){
		if(k*2+1>=m) 
			min=k*2;
		else
			min=minim(k*2,k*2+1);
		h[k]=h[min];
		k=min;
	}
	*/
	while(k1<=m&&compar(aux,h[k1])>0){
		h[k]=h[k1];
		k=k1;
		k1=minim(2*k,2*k+1);
	}
	h[k]=aux;
	--m;
}
void init(){
	for(long long i=0;i<=NMAX;++i)
		h[i].c=INF;
}
int main()
{
	
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	init();
	long long n,t,cost=0,nr,m=1;
	scanf("%lld%lld%lld",&n,&s,&t);
	scanf("%lld%lld",&h[1].c,&nr);
	cost+=h[1].c*nr;
	h[1].p=1;
	for(long long i=2; i<=n; i++){
		scanf("%lld%lld",&h[i].c,&nr);
		h[i].p=i;
		adaugare(++m);
		
		while(i-h[1].p>=t)
			elimin(m);
		
		//scrie(m);
		cost+=nr*(h[1].c+s*(i-h[1].p));
	}
	printf("%lld",cost);
	return 0;
}