Cod sursa(job #439460)

Utilizator daniela.eneEne Daniela daniela.ene Data 11 aprilie 2010 16:21:38
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.04 kb
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h> 
#include <math.h>
#include<vector>
#include <functional>
//#include<sys/types.h>
using namespace std;
#define MAXX 1000000

typedef struct DATE {
	unsigned long int a;
	unsigned long int b;
} date;
vector<date> in;//memorez inaltimea si greutatea gutuilor din copac


bool comp(pair<unsigned long int,unsigned long int>i,pair<unsigned long int,unsigned long int>j) {
	return(i.second>j.second);
}

bool comp2 (date aa, date bb) {
	return(aa.a > bb.a);
}

int main () {
	FILE *f,*g;
	f=fopen("gutui.in","r");
	g=fopen("gutui.out","w");
	unsigned long int n,h,u; // n:numar de gutui h: inamtimea max u:cu cat se ridica crengile
	unsigned long int gmax=0; // greutatea maxima
	int i;
	//int k = 0; //contor pt a numara cate gutui voi culege
	vector<pair<unsigned long int,unsigned long int> > out; //heap in care memorez inaltimea si greutatea gutuilor culese
	fscanf (f, "%lu %lu %lu",&n,&h,&u);
	date aux;
	for (i = 0; i < (int)n; i ++) {
		fscanf (f, "%lu %lu",&aux.a,&aux.b);	
		in.push_back(aux);
		}
	sort(in.begin(),in.end(),comp2);
	/*if (in[0].a <= h) {	
		out.push_back(make_pair(in[0].a, in[0].b));
		push_heap(out.begin(),out.end(),comp) ;
		if (h < u) 
				h = 0;
			else
				h -= u ; 
		}*/
	for (i = 0; i < (int) n;i ++ )
		if (in[i].a <= h) {
			out.push_back(make_pair(in[i].a, in[i].b));
			push_heap(out.begin(),out.end(),comp) ;
		//	printf ("**** \n");
			//for (i=0; i<(int)out.size(); i++)
			//	printf (" %lu %lu \n", out[i].first,out[i].second);
		//	printf ("**** \n");
			if (h < u) 
				h = 0;
			else
				h -= u ; 
		//	k ++;
		}
		else {
			if ( out.front().second < in[i].b) {
				printf ("la la la \n");
				pop_heap( out.begin( ), out.end( ), comp );
				out.pop_back();
				out.push_back(make_pair(in[i].a,in[i].b));
				push_heap(out.begin(),out.end(),comp) ;	
			}
		}
	gmax=0;
	for (i=0; i<(int)out.size(); i++)
		gmax += out[i].second;
	for (i=0; i<(int)out.size(); i++)
		printf (" %lu %lu \n", out[i].first,out[i].second);
	fprintf(g, "%lu\n",gmax);
	return 0;
}