Cod sursa(job #169047)

Utilizator swift90Ionut Bogdanescu swift90 Data 31 martie 2008 23:41:14
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct oi{
	int d,a;
}nr[100010];
int sum;
int hn,heap[100010];
pair <int,int> v[100010];
void schimb(int i,int poz){
	int aux=heap[poz];
	heap[poz]=heap[i];
	heap[i]=aux;
}
void upheap(int i){
	int poz=i>>1;
	if(heap[i]>heap[poz] && poz>0){
		schimb(i,poz);
		upheap(poz);
	}
}
void downheap(int i){
	int st=i<<1,max;
	max=i;
	if(st<=hn && heap[max]<heap[st])
		max=st;
	++st;
	if(st<=hn && heap[max]<heap[st])
		max=st;
	if(max!=i){
		schimb(i,max);
		downheap(max);
	}
}
int main(){
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	int n,x,l,i,tmax;
	scanf("%d%d%d",&n,&x,&l);
	for(i=0;i<n;++i){
		scanf("%d%d",&nr[i].d,&nr[i].a);
		v[i].second=i;
		v[i].first=(x-nr[i].d)/l;
	}
	
	sort(v,v+n);
	tmax=v[n-1].first;
	hn=0;
	i=n-1;
	while(i>=0 && tmax>=0){
		while(tmax==v[i].first && i>=0){
			heap[++hn]=nr[v[i].second].a;
			upheap(hn);
			--i;
		}
		if(hn>0){
			sum+=heap[1];
			heap[1]=heap[hn--];
			heap[hn+1]=0;
			downheap(1);
		}
		--tmax;
	}
	printf("%d\n",sum);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}