Cod sursa(job #496552)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 29 octombrie 2010 18:05:04
Problema Lupul Urias si Rau Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>
#include <stdlib.h>

struct oaie {
	int t,ln;
};
oaie a[100000];
int h[100000];
int i,n,tmax,m,q,x,l,t,ln,d;
long long s;

int comp(const void *a,const void *b) {
	oaie *x=(oaie*)a;
	oaie *y=(oaie*)b;
	if (x->t<y->t) return 1;
	else if (x->t==y->t) return 0;
	else return -1;
}

void swap(int m,int t) {
	int x;
	x=h[m];
	h[m]=h[t];
	h[t]=x;
}

void HeapUp(int m) {
	int t;
	if (m<=1) return;
	t=m/2;
	if (h[m]>h[t]) {
		swap(m,t);
		HeapUp(t);
	}
}

void HeapDown(int r) {
	int st,dr,i;
	if (2*r<=m) {
		st=h[2*r];
		if (2*r+1<=m) dr=h[2*r+1];
		else dr=st-1;
		if (st>dr) i=2*r;
		else i=2*r+1;
		if (h[r]<h[i]) {
			swap(r,i);
			HeapDown(i);
		}
	}
}

int main () {
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	scanf("%d%d%d",&n,&x,&l);
	for (i=0; i<n; i++) {
		scanf("%d%d",&d,&ln);
		a[i].t=(x-d)/l+1;
		a[i].ln=ln;
		if (a[i].t>tmax) tmax=a[i].t;
	}
	qsort(a,n,sizeof(oaie),comp);
	
	q=0;
	m=0;
	s=0;
	for (i=tmax; i>=1; i--) {
		while (a[q].t==i && q<n) {
			m++;
			h[m]=a[q].ln;
			q++;
			HeapUp(m);
		}
		if (m>=1) {
			s+=h[1];
			m--;
			h[1]=h[m];
			HeapDown(1);
		}
	}
	printf("%lld\n",s);
	return 0;
}