Cod sursa(job #204891)

Utilizator AndreyPAndrei Poenaru AndreyP Data 27 august 2008 22:39:23
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<stdio.h>
int n,t,cate;
long long s,rez;
struct help
{
	long long c;
	int z;
};
help h[100005];
inline int father(int x)
{
	return x>>1;
}
inline int left_son(int x)
{
	return x<<1;
}
inline int right_son(int x)
{
	return (x<<1)+1;
}
void upheap(int k)
{
	help key=h[k];
	while((k>1)&&(key.c<h[father(k)].c))
	{
		h[k]=h[father(k)];
		k=father(k);
	}
	h[k]=key;
}
void swap(help &x,help &y)
{
	help aux;
	aux=x;
	x=y;
	y=aux;
}
void downheap(int k)
{
	int son;
	do
	{
		son=0;
		if(left_son(k)<=cate)
		{
			son=left_son(k);
			if(right_son(k)<=cate)
			{
				if(h[right_son(k)].c<h[son].c)
					son=right_son(k);
			}
			if(h[son].c>=h[k].c)
				son=0;
		}
		if(son)
		{
			swap(h[son],h[k]);
			k=son;
		}
	}while(son);
}
void update()
{
	int i;
	for(i=1; i<cate; i++)
	{
		h[i].c+=s;
		h[i].z++;
		if(h[i].z==t)
		{
			h[i]=h[cate];
			cate--;
			downheap(i);
		}
	}
}
int main()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%d%lld%d",&n,&s,&t);
	long long c,p;
	for(cate=1; n; n--,cate++)
	{
		scanf("%lld%lld",&c,&p);
		update();
		h[cate].c=c;
		upheap(cate);
		rez+=h[1].c*p;
	}
	printf("%lld\n",rez);
	return 0;
}