Cod sursa(job #43035)

Utilizator ZuziFilip Sanziana Zuzi Data 29 martie 2007 19:09:53
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <stdio.h>
#define NMAX 100001
int n, a[NMAX], p, l, tmax;
int dm,sol;

typedef struct
{
	int t, x;
}VEC;
VEC t[NMAX];

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


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;
	}

}

int partitie(int st, int dr)
{
	int i, j, pivot;
	VEC aux;
	i=st-1;
	j=dr+1;
	pivot=t[(st+dr)/2].t;
	while (1)
	{
		do {++i;} while (t[i].t>pivot);
		do {--j;} while (t[j].t<pivot);
			if (i<j)
				{ aux=t[i]; t[i]=t[j]; t[j]=aux;}
			else
				return j;
	}
}


void sort(int st, int dr)
{
	int m;
	if (st < dr)
	{
		m = partitie(st, dr);
		sort(st, m);
		sort(m+1, dr);
	}
}

void rezolv()
{
	int j, i;
	sort(1,n);

	for (i =1; i <= n; i=j+1)
	 { 	for (j = i; t[j].t == t[j+1].t && j <= n; j++)
		  insert_heap(t[j].x);
		  insert_heap(t[j].x);

		sol += extragere_maxim();

	 }


}

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