Cod sursa(job #463082)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 14 iunie 2010 15:14:18
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.55 kb
//Ene Daniela 324CA
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h> 
#include <math.h>
#include<vector>
#include <functional>

#define MAXX 1000000
using namespace std;

typedef struct DATE {
	unsigned long int a;
	unsigned long int b;
} date;
date in[MAXX];//memorez inaltimea si greutatea gutuilor din copac

void merge(int low, int high, int mid) {
	int i, j, k;
	unsigned long int c[MAXX],d[MAXX];
	i = low;
	j = mid+1;
	k = low;
	while((i <= mid)&&(j <= high)) { // sortez dupa in.a
		if (in[i].a > in[j].a) {
			c[k] = in[i].a;
			d[k] = in[i].b;
			k ++;
			i ++;
		}
		else {
			c[k] = in[j].a;
			d[k] = in[j].b;
			k ++;
			j ++;
		}
	}
	while(i <= mid) {
		c[k] = in[i].a;
		d[k] = in[i].b;
		k ++;
		i ++;
	}
	while(j <= high){
		c[k] = in[j].a;
		d[k] = in[j].b;
		k ++;
		j ++;
	}
	for(i = low;i < k;i ++) {
		in[i].a = c[i];
		in[i].b = d[i];
	}
} 

void mergesort( int low, int high) {
	int mid;
	if(low < high) {
		mid = (low+high)/2;
		mergesort(low,mid);
		mergesort(mid+1,high);
		merge(low,high,mid);
	}
}


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;
	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
	vector<pair<unsigned long int,unsigned long int> > out; //heap in care memorez inaltimea si greutatea gutuilor culese
	date aux;
	int i;
	
	f=fopen("gutui.in","r");
	g=fopen("gutui.out","w");
	fscanf (f, "%lu %lu %lu",&n,&h,&u);
	for (i = 0;i < n;i ++)
		fscanf (f, "%lu %lu",&in[i].a,&in[i].b);	
	//am fol merge sort pt ca mi s-a parut cel mai optim pt sortare si am optinut cel mai bun timp cu el	
	mergesort(0,n-1); //ordonez vectorul de structuri de tip date descrescator dupa inaltime
	
	for (i = 0; i < (int) n;i ++ )
		//daca mai pot culege gutui culeg in continuare
		if (in[i].a <= h) {
			out.push_back(make_pair(in[i].a, in[i].b));
			push_heap(out.begin(),out.end(),comp) ;
			if (h < u) 
				h = 0;
			else
				h -= u ; 
		}
		else {
			//verific daca una din gutuile culese deja pot fi poate fi inlocuita de gutuia curenta
			if ( out.front().second < in[i].b) {
				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) ;	
			}
		}
	//calculez greutatea max a tuturor gutuilor culese
	for (i=0; i<(int)out.size(); i++)
		gmax += out[i].second;
	fprintf(g, "%lu\n",gmax);
	return 0;
}