Cod sursa(job #425667)

Utilizator johnbBaranga Ionut johnb Data 25 martie 2010 22:24:19
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.6 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;

struct gutuie {
	int h;  // inaltimea la care se  afla initial
	int g;  // greutatea
    int nc; // nr max de gutui culese dupa care devine inaccesibila
};


/*
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 fcmp2(const void* fp1, const void* fp2) {
	gutuie* f1 = (gutuie*)fp1;
	gutuie* f2 = (gutuie*)fp2;
	return f2->h - f1->h;
}



int main() {
    gutuie *gutui, *sel;
	in >> n >> h >> u;
	gutui = new gutuie[n];
	sel   = 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 + 1;
    }
	qsort(gutui, n, sizeof(gutuie), fcmp2); // sortare dupa inaltimea la care se afla
	int crtMax = 0, crtNc = 0, si = 0;
	bool foundPrev = false;
	for (int i = 0; i < n; i++) {
        test:
        if (gutui[i].nc == crtNc){
           foundPrev = true;
           if (gutui[i].g > crtMax) {
              crtMax = gutui[i].nc;
              sel[si] = gutui[i];
           }
        }
        else {
             crtMax = 0;
             if (foundPrev)
                si++;
             crtNc++;
             foundPrev = false;
             goto test;
        }
    }
    for (int i = 0; i < si; i++)
        r += sel[i].g;

    	
	out << r;
	return 0;
}