Cod sursa(job #168976)

Utilizator swift90Ionut Bogdanescu swift90 Data 31 martie 2008 22:12:59
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 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=1;
	for(i=n-1;i>=0;--i){
		if(tmax!=v[i].first){
			tmax=v[i].first;
			sum+=heap[1];
			heap[1]=heap[hn--];
			heap[hn+1]=0;
			downheap(1);
		}
		heap[++hn]=nr[v[i].second].a;
		upheap(hn);
	}
	sum+=heap[1];
	printf("%d\n",sum);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}