Cod sursa(job #435480)

Utilizator johnbBaranga Ionut johnb Data 7 aprilie 2010 15:11:00
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 3.48 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
	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;
	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) {
                      //   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;
	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;
    
    qsort(gutui, nr, sizeof(gutuie), cmp_g);
 //  print();
 //   system("pause");
    int dels = 0, crt_idx;
    for (i = 0; i < nr; i++)
        if (gutui[i].idx == 0)
           crt_idx = i;
    for (i = nr - 1; i >= 0; i--) {
        while (gutui[i].g != 0 && gutui[i].n < gutui[i].b - dels) { 
              r -= gutui[crt_idx].g;
              gutui[crt_idx].g = 0;
              dels++;
              for (j = i; j >= 0; j--)
                  if (gutui[j].idx == gutui[crt_idx].idx + 1)
                     crt_idx = j;
        }
    }

    out << r;
	return 0;
}