Cod sursa(job #439895)

Utilizator alex.mireaAlex Mirea alex.mirea Data 11 aprilie 2010 20:15:22
Problema Gutui Scor 20
Compilator cpp Status done
Runda teme_upb Marime 1.34 kb

#include <iostream>

#include <vector>
#include <list>
using namespace std;
struct Gutuie{
	long int h,g;
};

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

int main(){
	FILE *fin,*fout;

	long int n,h,u,i,aux,max,s=0,k;
	vector<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));
	}


	sort(gutui.begin(),gutui.end(),comparaGutui);
		
	/*
	for (i=0;i<n;i++)
		printf("%ld %ld\n",gutui[i].h,gutui[i].g);
	*/
	aux = (gutui[n-1].h / u)*u;
	
	while ((gutui.size() or gutuiDisp.size()) and aux <= h){
			while (gutui.size() and gutui.back().h <= aux) {
      		gutuiDisp.push_back(gutui.back().g);
        	push_heap(gutuiDisp.begin(), gutuiDisp.end()); // refac ordinea de heap
        	gutui.pop_back();   //scot elementul din lista
    	}
		
       
	    if (gutuiDisp.size()){
			s+=gutuiDisp.front();
			pop_heap(gutuiDisp.begin(),gutuiDisp.end()); // rearanjeaza heapul - cea mai mare greutate este ultima
			gutuiDisp.pop_back(); // scot greutatea
			aux += u;
		}
		else{
			k = (gutui.back().h - aux)/u;
			if (k>1)
				aux += u*k;
			else
				aux += u;
		}
	}
	fout = fopen("gutui.out","wt");
	fprintf(fout,"%ld",s);
	fclose(fin);
	fclose(fout);
	return 0;
}