Cod sursa(job #208822)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 19 septembrie 2008 09:55:49
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <stdio.h>
#define N 100001
int n,s,h[N],poz;
long long t;
struct ab{
	long long a,b;
};
ab v[N];
void  swap(int &x,int &y){
	int z=x;x=y;y=z;
}
void sift(int h[],int k,int n){
	int son=0;
	do{
		if(2*k<=n) son=2*k;
		if(2*k+1<=n && v[h[son]].a+(poz-h[son])*t>v[h[2*k+1]].a+(poz-h[2*k+1])*t)
			son=2*k+1;
		if(v[h[son]].a>=v[k].a)
			son=0;
		else {
			swap(h[son],h[k]);
			k=son;
		}
	}
	while(son);
}
void percolate(int h[],int k,int n){
	while(k>1 && v[h[k/2]].a+(poz-h[k/2])*t>v[h[k]].a+(poz-h[k])*t){
		swap(h[k/2],h[k]);
		k/=2;
	}
}
void add(int h[],int key,int &n){
	h[++n]=key;
	percolate(h,n,n);
}
void cut(int h[],int k,int &n){
	h[k]=h[n]; n--;
	if(k>1 && v[h[k/2]].a+(poz-h[k/2])*t > v[h[k]].a +(poz-h[k])*t)
		percolate(h,k,n);
	else
		sift(h,k,n);
}
int main(){
	int i,nr=1;
	long long sol;
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%d%lld%d",&n,&t,&s);
	for(i=1;i<=n;i++)
		scanf("%lld%lld",&v[i].a,&v[i].b);
	h[1]=1;sol=v[1].a*v[1].b;
	for(poz=2;poz<=n;poz++){
		add(h,poz,nr);
		if(poz-h[1]>=s) 
			cut(h,1,nr);
		sol+=( v[h[1]].a+(poz-h[1])*t ) * v[poz].b;
	}
	printf("%lld\n",sol);
	return 0;
}