Cod sursa(job #42087)

Utilizator ZuziFilip Sanziana Zuzi Data 28 martie 2007 20:36:48
Problema Lupul Urias si Rau Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>
int n, x[100001], a[100001], p, l, tmax, t[100001];
int dm,sol;

void read()
{
	int i,d;
	scanf("%d%d%d", &n, &p, &l);
	for (i = 1; i <= n; i++)
	{
		scanf("%d%d", &d, &x[i]);
		t[i] = (p-d) / l+1;
		if (t[i] > tmax)
			tmax = t[i];
	}
}


void rec_heap(int i)
{
	int st, dr, maxim, aux;
	while (i<=dm)
	{
		st = 2*i; dr = 2*i+1;
		if (st <= dm && a[st] > a[i])
			maxim = st;
		else
			maxim = i;
		if (dr <= dm && a[dr] > a[maxim])
			maxim = dr;
		if (i != maxim)
		 {
			aux = a[i];
			a[i] = a[maxim];
			a[maxim] = aux;
			i = maxim;
		 }
		else
			i=dm+1;
	}
}

int extragere_maxim()
{
	int v =a [1];
	a[1] = a[dm--];
	rec_heap(1);
	return v;
}


void insert_heap(int v)
{
	int i,t,aux;
	a[++dm] = v;
	for (i = dm; i > 1; i = i/2)
	{
		t=i/2;
		if (a[t]<a[i])
		 aux = a[t], a[t] = a[i], a[i] = aux;
		else
		 i = 1;
	}

}


void rezolv()
{
	int j, i;

	for (i = tmax; i >= 1; i--)
	 { 	for (j = 1; j <= n; j++)
		  if (t[j] == i)
			insert_heap(x[j]);
		sol+=extragere_maxim();

	 }


}

int main()
{
	freopen("lupu.in", "r", stdin);
	freopen("lupu.out", "w", stdout);
	read();
	rezolv();
	printf("%d\n", sol);
	return 0;
}