Cod sursa(job #426266)

Utilizator johnbBaranga Ionut johnb Data 26 martie 2010 17:51:01
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 2.33 kb
#include <fstream>
#include <stdlib.h>
#include <iostream>
using namespace std;

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

int n, h, u, r = 0, nr = 0;

struct gutuie {
	int h;  // inaltimea la care se  afla initial
	int g;  // greutatea
    int nc; // nr max de gutui culese anterior pt care gutuia ramane accesibila
            // numit "nivel"
};

gutuie *gutui;
/*
int fcmp(const void* fp1, const void* fp2) {
	fruct* f1 = (fruct*)fp1;
	fruct* f2 = (fruct*)fp2;
	float r1 = f1->g / f1->h,
	      r2 = f2->g / f2->h;
	return r1 - r2 < 0 ? -1 : 1;
}

int fcmp1(const void* fp1, const void* fp2) {
	fruct* f1 = (fruct*)fp1;
	fruct* f2 = (fruct*)fp2;
	return f2->g - f1->g;
}
*/

int cmp_h(const void* fp1, const void* fp2) {
	gutuie* f1 = (gutuie*)fp1;
	gutuie* f2 = (gutuie*)fp2;
	int r = f1->nc - f2->nc;
	return r == 0 ? f2->g - f1->g : r;
}

int cmp_g(const void* fp1, const void* fp2) {
	gutuie* f1 = (gutuie*)fp1;
	gutuie* f2 = (gutuie*)fp2;
	return f1->g - f2->g;
}

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


int main() {
    
	in >> n >> h >> u;
	gutui = new gutuie[n];
	for (int i = 0; i < n; i++) {
		in >> gutui[i].h >> gutui[i].g;
		gutui[i].nc = (h - gutui[i].h) / u;
		r  += gutui[i].g;
		nr += gutui[i].nc;
    }
    int ne = n;
    qsort(gutui, n, sizeof(gutuie), cmp_h);	
 
    int crt_g = 0, crt_n = 0, crt_nc = 0, max = 1;
    for (int i = 0; i < n; i++) {
       // print();
        if (gutui[i].nc == crt_nc) {
           crt_n++;
           if (crt_n > max) {
              r -= gutui[i].g;
              gutui[i].g  = 0;
              gutui[i].nc = 0;
              ne--;
              //printf("*");
           }
        }
        else {
             crt_nc = gutui[i].nc;
             crt_n = 1;
             max = crt_nc + 1;
            
        }
    }
             
             
    qsort(gutui, n, sizeof(gutuie), cmp_g);	
    int i = 0, limit = ne * (ne - 1) / 2;
    while (nr < limit) {
          /*
          print();
          printf("%d %d %d\n", nr, limit, ne);
          getchar();
          */
          r  -= gutui[i].g;
          nr -= gutui[i++].nc;
          --ne;
          limit = ne * (ne - 1) / 2;
    }
    /*
    print();
    printf("%d %d %d\n", nr, limit, ne);
    getchar();*/
    out << r;
	return 0;
}