Cod sursa(job #436656)

Utilizator johnbBaranga Ionut johnb Data 8 aprilie 2010 18:59:49
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 3.7 kb
#include <fstream>
#include <stdlib.h>
#include <iostream>
//#include <conio.h>

//#define uint unsigned int
#define uint int


using namespace std;

ifstream in ("gutui.in");
ofstream out("gutui.out");

uint n, h, u, r = 0, nr = 0, *del = NULL, b = 0, next_min = 0;

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

gutuie *gutui;

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

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

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

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

void del_next_min() {
		r -= gutui[next_min].g;
		for (int j = gutui[next_min++].n; j < nr; j++)
			del[j]++;
}

bool done() {
	for (int i = b; i < nr; i++)
		if (gutui[i].n < gutui[i].b - del[gutui[i].n]) {
			b = i;
			return false;
		}
	return true;
}

int main() {
    uint  crt_nr = 0, crt_n = 0, i = 0, j = 0;
	in >> n >> h >> u;
	gutui = new gutuie[n];
  
	for (i = 0; i < n; i++) {
		in >> j >> gutui[i].g;
		gutui[i].n = (h - j) / u;
		if (gutui[i].n >= 0 && gutui[i].g > 0) { // se elimina cazurile in care nu se poate ajunge 
			r  += gutui[i].g;
			nr++;
		}
		else {
			gutui[i].g = 0;
		}
    }

    qsort(gutui, n, sizeof(gutuie), cmp_h);	// sortare dupa nivel
	
	/* se pot face maxim k + 1 culegeri de gutui aflate la nivelul k
	 * daca exista mai mult de k + 1 gutui aflate la nivelul k, se pastreaza cele mai grele k + 1 
	 */
    i = 0;

    while (i < n) {
		if (gutui[i].n < 0) {
            gutui[i].g = 0;
			i++;
		}
		else {
            if (gutui[i].n == crt_n) { 
               crt_nr++;  
               if (crt_nr > crt_n + 1) { // incepand cu crt_n + 2, se vor elimina toate gutuile cu nivelul curent
    			   while (gutui[i].n == crt_n && i < n) {
                      //   printf("eliminare %d pt ca gutui[%d].n = %d si crt_n = %d si crt_nr = %d\n", i, i, gutui[i].n, crt_n, crt_nr);
    					r  -= gutui[i].g;
    				    gutui[i].g  =  0;
                        nr--;
    					i++;
    			   }
		
               }
    		   else {
    			   i++;
    		   }
            }
            else {
                 crt_n = gutui[i].n;
                 crt_nr = 1; 
    			 i++;
            }
        }
    }
 //   for (int i = 0; i < n; i++)
   //     printf("[%d %d]\n", gutui[i].g, gutui[i].n);       
             
	// sortare dupa greutate
    qsort(gutui, n, sizeof(gutuie), cmp_g);	
    i = 0;
	while (gutui[i].g == 0)
		i++;
	gutui += i; // raman doar cazurile valide, adica nr gutui, nr <= n
    for (i = 0; i < nr; i++)
        gutui[i].idx = i;		
		
	// sortare dupa nivel
	qsort(gutui, nr, sizeof(gutuie), cmp_h);	
	for (i = 0; i < nr; i++)
		gutui[i].b = i;
 

    int dels = 0, crt_idx = 0;
    while (gutui[nr - 1].n >= gutui[nr - 1].b && nr)
			nr--;

	
	if (nr == 0) {	
		goto end;
	}

	qsort(gutui, nr, sizeof(gutuie), cmp_g);
          
	del = new uint[nr];
	for (i = 0; i < nr; i++)
		del[i] = 0;
	while (!done())
		del_next_min();

end:
    out << r;
	return 0;
}