Cod sursa(job #498697)

Utilizator GulyanAlexandru Gulyan Data 5 noiembrie 2010 19:02:31
Problema Lupul Urias si Rau Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int g, r;
}Fr;

typedef struct {
	int *v, n;
}Vector;

/*	sorteaza dupa rang (2 fructe au acelasi rang daca se pot la pasul k)
	practic, rangul = inaltimea_scarii - inaltime_fruct/cat_urca_fructele
	daca au acelasi rang le sortam descrescator dupa greutate
*/
int cmp(const void *a, const void *b) {
	if( ((Fr*)a)->r != ((Fr*)b)->r )
		return ((Fr*)b)->r - ((Fr*)a)->r;
	return ((Fr*)b)->g - ((Fr*)a)->g;
}

/*	coboara un element (n) intr-un arbore
	pana cand devine heap
*/
void coboara(Vector ** heap, int dimHeap, int n) {
	int st = 2 * n + 1;
	int dr = st + 1;
	int max = n;
	if(st < dimHeap && heap[st]->v[0] > heap[n]->v[0])
		max = st;
	if(dr < dimHeap && heap[dr]->v[0] > heap[max]->v[0])
		max = dr;
	if(max != n) {
		Vector *v = heap[n];
		heap[n] = heap[max];
		heap[max] = v;
		coboara(heap, dimHeap, max);
	}
}

/*	urca un element (n) intr-un arbore
	pana cand devine heap
*/
void urca(Vector ** heap, int dimHeap, int i) {
	if(i <= 0)
		return;
	int p = (i - 1)/ 2;
	if(heap[i]->v[0] > heap[p]->v[0]) {
		Vector *v = heap[p];
		heap[p] = heap[i];
		heap[i] = v;
		urca(heap, dimHeap, p);
	}
}

int main() {
	freopen("lupu.in", "r", stdin);
	freopen("lupu.out", "w", stdout);
	int n, s, k, i, j;
	scanf("%d%d%d", &n, &s, &k);
	Fr *a = (Fr*)(malloc(n * sizeof(Fr)));
	Vector *v;
	/* citim date, ignorand fructele inaccesibile din start */
	for(i = 0; n--;) {
		scanf("%d%d", &(a[i].r), &(a[i].g));
		if(a[i].r > s)
			continue;
		//calculam randul, nu inaltimea pentru ca este mai util
		a[i].r = (s - a[i].r) / k;
		i++;
	}
	//sortam vectorul de fructe dupa rang, apoi dupa greutate
	qsort(a, n = i, sizeof(Fr), cmp);
	int *buff, *origBuff = buff = (int*)malloc(n * sizeof(int));

	Vector ** heap = (Vector**)malloc(n * sizeof(Vector*));
	int dimHeap = 0;

	int vf = 0, max = 0;
	for(i = 0, j = s / k; j >= 0; j--) {
		buff += vf;
		vf = 0;
		/*	toate fructele cu acelasi rang sunt grupate in vectorul buff
			ele sunt deja sortate descrescator dupa greutate */
		while(i < n && a[i].r >= j)
			buff[vf++] = a[i++].g;
		/*	daca exista macar un element in vectorul buff (exista fructe pe acest rang)
			adaugam vectorul intr-un max-heap */
		if(vf > 0) {
			v = (Vector*)malloc(vf * sizeof(Vector));
			v->n = vf;
			v->v = buff;
			heap[dimHeap++] = v;
			urca(heap, dimHeap, dimHeap - 1);
		}
		/*	daca putem sa scoatem, scoatem primul element din heap
			adaugam la maximul nostru,
			si daca mai sunt elemente in vector il punem la loc */
		if(dimHeap > 0) {
			max += heap[0]->v[0];
			heap[0]->v++;
			heap[0]->n--;
			if(heap[0]->n <= 0) {
				free(heap[0]);
				heap[0] = heap[--dimHeap];
			}
			coboara(heap, dimHeap, 0);
		}
	}

	printf("%d\n", max);
	free(a);
	free(origBuff);
	free(heap);
	fclose(stdout);
	return 0;
}