Cod sursa(job #436106)

Utilizator baktakNicoleta Iordachi baktak Data 8 aprilie 2010 02:26:49
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.73 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;

/******************************************************************************
 *									      *
 *	sortW() - functie auxiliara pentru compararea elementelor             *
 *	de pe pozitia a doua din pereche				      *
 *									      *
 ******************************************************************************/

bool sortW(pair<unsigned int,unsigned int>x,pair<unsigned int,unsigned int>y) {
    return(x.second > y.second);
}


/******************************************************************************
 *									      *
 *	sortH() - functie auxiliara pentru compararea elementelor             *
 *	de pe pozitia a doua din pereche				      *
 *									      *
 ******************************************************************************/

bool sortH(pair<unsigned int,unsigned int>x, pair<unsigned int, unsigned int>y) {
    return(x.first > y.first);
}

int main(){

	
	unsigned int n;			// nr de gutui
	unsigned int h;			// inaltimea maxima 
	unsigned int prag;		// inaltimea cu care se inalta ramurile
	unsigned int pr = 0;		// inaltimea curenta cu care se inalta ramurile
	unsigned int x,y;		// variabile pentru a crea perechile
	
	vector< pair<unsigned int,unsigned int> > gutui;// vectori de perechi pentru inaltimi si greutati
	vector< pair<unsigned int,unsigned int> > cules;// greutatea fiecarei gutui culese	
	pair<unsigned int,unsigned int> k ;		// lungimea vectorului cules[]
		
	unsigned int i;		// variabile auxiliare
	

	FILE *f, *g;
	f = fopen("gutui.in","r");
	g = fopen ("gutui.out","w");
	

	/* citire date de unsigned intrare */
	fscanf(f,"%d %d %d", &n, &h, &prag);
	gutui.resize(n);
	for(i = 0; i<n; i++){
		fscanf(f, "%d %d",&x,&y);
		gutui[i] = make_pair(x,y);
	}
		
	sort(gutui.begin(), gutui.end(), sortH);
	
	make_heap(cules.begin(),cules.end());
	unsigned int len = gutui.size();

	pr = 0;
	for(i = 0; i<len; i ++){
		/* verificare daca Gigel poate ajunge la ramuri */
		if((gutui[i].first + pr) <= h && pr <= h){
			cules.push_back(gutui[i]);
			push_heap(cules.begin(),cules.end(),sortW);
			
			/* cresterea inaltimii cu care se ridica ramurile */
			pr +=prag;
		}
	else{
			/* verificare daca nu a fost aleasa o greutate mai
			 * usoara decat cea curenta 			 */
			if(cules.front().second < gutui[i].second){
				pop_heap(cules.begin(), cules.end(),sortW);
				cules.pop_back();
				cules.push_back(gutui[i]);
				push_heap(cules.begin(),cules.end(),sortW);
	
			}
		}
	}
	
	len = cules.size();	// retin lungimea heap-ului
	unsigned int s = 0;	// variabila in care se retine suma
	
	// calculez suma greutatilor
	for(i=0; i<len; i++)
		s += cules[i].second;
	
	fprintf(g,"%d\n",s);
	
	fclose(f);
	fclose(g);
	return 0;
}