Cod sursa(job #434462)

Utilizator johnbBaranga Ionut johnb Data 5 aprilie 2010 22:56:36
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 2.88 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;

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

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 < n; i++) {
         printf("%d %d\n",  gutui[i].g, gutui[i].n);
     }
     printf("\n");
}


int main() {
    
	in >> n >> h >> u;
	gutui = new gutuie[n];
	gutuie* gutui2 = new gutuie[n];
	int j = 0;

	for (int i = 0; i < n; i++) {
		in >> j >> gutui[i].g;
		gutui[i].n = (h - j) / u;
		gutui2[i].n = (h - j) / u;
		if (gutui[i].n >= 0) { // se elimina cazurile in care nu se poare ajunge 
			r  += gutui[i].g;
			nr += gutui[i].n;
		}
    }

       
    int ne = n;
    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 

    int  crt_nr = 0, crt_n = 0, i = 0;

    while (i < n) {
		if (gutui[i].n < 0) {
			i++;
			continue;
		}
        if (gutui[i].n == crt_n) {   
           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;
					nr -= gutui[i].n;
				    gutui[i].g  =  0;
                    ne--;
					i++;
			   }
			   continue;
           }
		   else {
			   crt_nr++;
			   i++;
		   }
        }
        else {
             crt_n = gutui[i].n;
             crt_nr = 1; 
			 i++;
        }
    }
       
             
	// sortare dupa greutate
    qsort(gutui2, n, sizeof(gutuie), cmp_g);	

	/*
    i = 0;
	int limit = ne * (ne - 1) / 2;
	while (gutui[i].g == 0)
		i++;
    while (nr < limit) {
		  if (gutui[i].n )
          r  -= gutui[i].g;
          gutui[i].g = 0;
          nr -= gutui[i++].n;
          --ne;
          limit = ne * (ne - 1) / 2;
    }
  //  print();
  //  printf("r total = %d\n", r);
  //  getchar();  
  */
	int deleted = 0;
	for (int i = 0; i < n; i++) {
		if (gutui[i].n < i - deleted) {
			int del = i - gutui[i].n;
			for (int j = 0; j < n && del > 0; j++)
				if (gutui2[i].n <= gutui[i].n) {
					r -= gutui2[i].g;
					del--;
					deleted++;
				}
		}
	}

					
    out << r;
	return 0;
}