Cod sursa(job #435485)

Utilizator baktakNicoleta Iordachi baktak Data 7 aprilie 2010 15:16:51
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.1 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;

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

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 gut
	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
	
	vector< pair<unsigned int,unsigned int> > gutui;
	vector< pair<unsigned int,unsigned int> > cules;		// greutatea fiecarei gut 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");
	
	unsigned int x,y;
	/* 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);
	pr = 0;
	make_heap(cules.begin(),cules.end());
	unsigned int len = gutui.size();
	
	for(i = 0; i<len; i ++){//prunsigned intf("bag %d\n",gutui[i].second);
		/* 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);
//			printf("bag %d\n",gutui[i].second);
			/* 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();
	///for(i=0; i<len; i++)
	//	prunsigned intf("%d %d\n",cules[i].first,cules[i].second);	

	unsigned int s = 0;
	
	for(i=0; i<len; i++)
		s += cules[i].second;
	
		
	fprintf(g,"%d\n",s);
	
	fclose(f);
	fclose(g);
	return 0;
}