Cod sursa(job #435422)

Utilizator johnbBaranga Ionut johnb Data 7 aprilie 2010 14:23:55
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 3.04 kb
#include <fstream>
#include <stdlib.h>
#include <iostream>
//#include <conio.h>

using namespace std;

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

int n, h, u, r = 0, nr = 0, *del = NULL;

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

gutuie *gutui;

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

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

int main() {
     int  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) {
    					r  -= gutui[i].g;
    				    gutui[i].g  =  0;
                        nr--;
    					i++;
    			   }
    			   crt_n++;
               }
    		   else {
    			   i++;
    		   }
            }
            else {
                 crt_n = gutui[i].n;
                 crt_nr = 1; 
    			 i++;
            }
        }
    }
       
             
	// 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
   // printf("%d %d %d\n", i, nr, r);
	/* del[i] = nr de cazuri eliminate in care nivelul este <= i */
	del = new int[nr];
	for (i = 0; i < nr; i++)
		del[i] = 0;			

	// sortare dupa nivel
	qsort(gutui, nr, sizeof(gutuie), cmp_h);	
	for (i = 0; i < nr; i++)
		gutui[i].b = i;

	// sortare dupa greutate
    qsort(gutui, nr, sizeof(gutuie), cmp_g);
   // print();
  //  system("pause");
	for (i = 0; i < nr; i++) {		
		if (gutui[i].n < gutui[i].b - del[i]) { // daca nu se poate culege
			r -= gutui[i].g;
			for (j = i; j < nr; j++) {
				del[j]++;
			}
		}
	}

    out << r;
	return 0;
}