Cod sursa(job #170769)

Utilizator razvi9Jurca Razvan razvi9 Data 3 aprilie 2008 10:31:30
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<cstdio>
#include<vector>
#include<algorithm>
int n,x,l,i,j,d,c,m,h[100001];
std::pair<int,int> a[100001];
long long nr;
inline void swap(int i,int j)
{
	int aux=h[i];h[i]=h[j];h[j]=aux;
}
void up(int k)
{
	if(k<2) return;
	int t=k>>1;
	if(h[t]<h[k]){
		swap(t,k);
		up(t);}
}
void down(int k)
{
	int st=k<<1;
	if(st>m) return;
	if(st+1<=m)
		if(h[st+1]>h[st])
			st++;
	if(h[st]>h[k]){
		swap(st,k);
		down(st);}		
}
inline void add(int i)
{
	h[++m]=a[i].second;
	up(m);
}
int get()
{
	if(!m) return 0;
	swap(1,m);
	m--;
	if(m>1) down(1);
	return h[m+1];
}
int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	scanf("%d %d %d",&n,&x,&l);
	for(i=1;i<=n;i++){
		scanf("%d %d",&d,&c);
		if(d<=x)
			a[++m]=std::make_pair<int,int>((x-d)/l,c);}
	std::sort(&a[1],&a[m+1]);
	n=m;
	m=0;
	j=n;
	nr=0;
	for(i=a[n].first;i>=0;i--){
		while(j>0 && a[j].first==i){
			add(j);j--;}
		nr+=get();}
	printf("%lld\n",nr);
	fclose(stdout);
	return 0;
}