Cod sursa(job #440764)

Utilizator alex.mireaAlex Mirea alex.mirea Data 12 aprilie 2010 15:02:56
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.28 kb

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
struct Gutuie{
	long int h,g,ls;
};

int comparaGutui(Gutuie g1,Gutuie g2){
	return g1.h > g2.h;
}

int main(){
	FILE *fin,*fout;
	long int n,h,u,i,nivel,gMax=0;
	vector<long int> gutuiDisp;
	
	fin = fopen("gutui.in","rw");
	fscanf(fin,"%ld %ld %ld",&n,&h,&u);
	vector<Gutuie> gutui(n);
	
	for (i=0;i<n;i++){
		fscanf(fin,"%ld %ld",&(gutui[i].h),&(gutui[i].g));
		gutui[i].ls = (h-gutui[i].h)/u; //stabilire life-span
	}

	sort(gutui.begin(),gutui.end(),comparaGutui);
		
	nivel = gutui[n-1].ls;

	while ((gutui.size() or gutuiDisp.size()) and nivel != -1){
		//actualizare vector (heap) de gutui disponibile
		while (gutui.size() and gutui.back().ls == nivel) {
		   	gutuiDisp.push_back(gutui.back().g);
        	push_heap(gutuiDisp.begin(), gutuiDisp.end()); // refac ordinea de heap
        	gutui.pop_back();   //scot elementul din lista
    	}
		nivel --;
		if (gutuiDisp.size()){
			gMax += gutuiDisp.front();
			pop_heap(gutuiDisp.begin(),gutuiDisp.end()); // rearanjeaza heapul - cea mai mare greutate este ultima
			gutuiDisp.pop_back(); // scot greutatea
		}
	
	}
	fout = fopen("gutui.out","wt");
	
	fprintf(fout,"%ld",gMax);
	fclose(fin);
	fclose(fout);
	return 0;
}