Cod sursa(job #425582)

Utilizator johnbBaranga Ionut johnb Data 25 martie 2010 21:24:13
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.05 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 fruct {
	int h;
	int g;
};

fruct* fructe;

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) {
	fruct* f1 = (fruct*)fp1;
	fruct* f2 = (fruct*)fp2;
	return f2->h - f1->h;
}



int main() {
	in >> n >> h >> u;
	fructe = new fruct[n];
	for (int i = 0; i < n; i++)
		in >> fructe[i].h >> fructe[i].g;
	qsort(fructe, n, sizeof(fruct), fcmp2);
	int idx = 0, // indexul curent in lista de fructe
	    nr  = 0, // nr de gutui culese
	    r   = 0;
	for (int i = 0; i < n; i++) {
        if ((fructe[i].h + nr*u) <= h) {
           nr++;
           r += fructe[i].g;
        }
    }
    	
	out << r;
	return 0;
}