Cod sursa(job #440050)

Utilizator johnbBaranga Ionut johnb Data 11 aprilie 2010 21:39:27
Problema Gutui Scor 20
Compilator cpp Status done
Runda teme_upb Marime 3.45 kb
#include <fstream>
#include <stdlib.h>

using namespace std;

struct gutuie {
	int g;    // greutatea
    int n;    // nr max de gutui culese anterior pt care gutuia ramane accesibila, numit "nivel"
	int idx;  // indexul 
};

struct nod {
	int val;
	int idx;
	nod* next;

	nod() {
		next = NULL;
	}
};

struct aux {
	int g;
	int idx;
};

#define S (sizeof(gutuie))

ifstream in ("gutui.in");
ofstream out("gutui.out");
int n, h, u, r = 0, nr = 0, *del;
gutuie *gutui;
nod** gn;

// comparara dupa nivel
int cmp_n(const void* fp1, const void* fp2) {
	gutuie* f1 = (gutuie*)fp1;
	gutuie* f2 = (gutuie*)fp2;
	int r = f1->n - f2->n;
	return (r == 0 ? f1->g - f2->g : r);
}

// comparara dupa greutate
int cmp_g(const void* fp1, const void* fp2) {
	gutuie* f1 = (gutuie*)fp1;
	gutuie* f2 = (gutuie*)fp2;
	int r = f1->g - f2->g;
	return (r == 0 ? f1->n - f2->n : r);
}


void print() {
     for (int i = 0; i < n; i++) {
         printf("%9d %d %d\n",  gutui[i].g, gutui[i].n, gutui[i].idx);
     }
     printf("\n");
}



int main() {
	
	in >> n >> h >> u;
	gutui = new gutuie[n];
	int ch, cg, cn, cnr, i, j, k, rem = 0;

	/***********************************************************************************************************
	 * - citire din fisier 
	 * - o prima selectie - selectatrea cazurilor convenabile, adica
	 *						eliminarea gutuilor la care nu se poate ajunge din prima , adica nivelul < 0 si
	 *						a celor cu greutate nula (daca exista)
	 * - nr gutuilor ramase dupa aceasta prima selectie fiind nr <= n
	 *
	 ***********************************************************************************************************/
	
    r = 0;
	for (i = 0; i < n; i++) {
		in >> ch >> cg;       // citire inaltime si greutate
		cn = (h - ch);    // calcul nivel
		if (cn >= 0 && cg > 0) { // se adauga numai cazurile convenabile 
			r += cg;
			gutui[nr].g = cg;
			gutui[nr].n = cn / u;
			nr++;
		}
    }

	n = nr; 
	if (n <= 1) {
		out << r;
		return 0;
	}
	
    i = 0, cn = 0, cnr = 0;    
             

	qsort(gutui, n, S, cmp_g);
	for (i = 0; i < n; i++)
		gutui[i].idx = i;
	qsort(gutui, n, S, cmp_n);
	int maxn = gutui[n - 1].n + 1; // nr de niveluri
	gn = new nod*[maxn];
	for (i = 0; i < maxn; i++)
		gn[i] = NULL;
	j = 0;
	for (i = 0; i < n; i++) {
		while (gutui[i].n != j) 
			j++;
		nod* nn = new nod;
		nn->val = gutui[i].g;
		nn->next = gn[j];
		gn[j] = nn;
	}

	/*
	for (i = maxn - 1; i >= 0; i--) {
		nod* nn = gn[i];
		printf("%d -> ", i);
		while (nn != NULL) {
			printf("%d ", nn->val);
			nn = nn->next;
		}
		printf("\n");
	}
	*/
	
	int m, mi;
	for (i = maxn - 1; i > 0; i--) {
		nod* nn = gn[i];
		if (nn == NULL || nn->next == NULL)
			continue;
		nn = nn->next;
		nr = 1;
again:
		m = INT_MAX;
		for (j = i - 1; j >= 0; j--) {
			if (gn[j] == NULL) {
				m = 0;
				mi = j;
			}
			else
				if (gn[j]->val < m) {
					m = gn[j]->val;
					mi = j;
				}
		}

		if (nn->val > m) {
			if (m == 0)
				gn[mi] = new nod;
			gn[mi]->val = nn->val;
		}
		nr++;
		nn = nn->next;
		if (nr <= j + 1 && nn != NULL)
			goto again;
	}

	r = 0;
	for (i = 0; i < maxn; i++)
		r += gn[i] ? gn[i]->val : 0;

	/*
	for (i = maxn - 1; i >= 0; i--) {
		nod* nn = gn[i];
		printf("%d -> ", i);
		while (nn != NULL) {
			printf("%d ", nn->val);
			nn = nn->next;
		}
		printf("\n");
	}
	*/
	//system("pause");
	out << r;
	return 0;
}