Cod sursa(job #435205)

Utilizator baktakNicoleta Iordachi baktak Data 7 aprilie 2010 01:10:40
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 2.87 kb
#include<iostream>
//#include<fstream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include<vector>
using namespace std;



/******************************************************************************
 *									      *
 *	minim() - determina elementul minim dintr-un vector		      *
 *									      *
 ******************************************************************************/

int minim(vector<int> v, int n){

	int i;
	int min = v[0];
	
	for(i = 1; i<n; i++)
		if(min > v[i])
			min = v[i];
		
	return min;
}


/******************************************************************************
 *									      *
 *	index() - determinarea pozitiei unui element intr-un vector	      *
 *									      *
 ******************************************************************************/

int index(int x, vector<int> v, int n){

	int i;
	
	for(i = 0; i<n; i++)
		if(x == v[i])
			return i;
		
	return -1;
}


/******************************************************************************
 *									      *
 *		suma() - determinarea sumei elementelor dintr-un vector	      *
 *									      *
 ******************************************************************************/

int suma(vector<int> v, int n){

	int i, s = 0;
	
	for(i = 0; i<n; i++)
		s += v[i];
	
	return s;
}

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

int main(){

	
	
	
	
	int n;			// nr de gut
	int h;			// inaltimea maxima 
	int prag;		// inaltimea cu care se inalta ramurile
	int pr = 0;		// inaltimea curenta cu care se inalta ramurile
	
	vector< pair<int,int> > gutui;
	vector< pair<int,int> > cules;		// greutatea fiecarei gut culese	
	pair<int,int> k ;		// lungimea vectorului cules[]
		
	int i;		// variabile auxiliare
	

	FILE *f, *g;
	f = fopen("gutui.in","r");
	g = fopen ("gutui.out","w");
	
	int x,y;
	/* citire date de 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());
//	printf("%d\n",gutui.front().first);
	for(i = 0; i<n; 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());
			/* 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){
				replace(cules.begin(),cules.end(),cules.front(),gutui[i]);
	
			}
		}
	
	//for(i=0; i<n; i++)
	//	printf("%d %d\n",cules[i].first,cules[i].second);	
	i = 0;
	int s = 0;
	int len = cules.size();
	for(i=0; i<len; i++)
		s += cules[i].second;
	
		
	fprintf(g,"%d\n",s);
	
	fclose(f);
	fclose(g);
	return 0;
}