Cod sursa(job #463721)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 17 iunie 2010 12:28:29
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.61 kb
#include <stdio.h>
#include <malloc.h>
#include <algorithm>
#include <vector>
using namespace std;
#define u_int unsigned int

//functia comparator pentru sortarea gutuilor in ordinea descrescatoare a inaltimilor
bool desc(u_int *a, u_int *b){
	return a[0]>b[0];
}

u_int max(u_int a, u_int b){
	if(a > b)
		return a;
	return b;
}

int main(){
	FILE *f, *g;
	f = fopen ("gutui.in", "r");
	g = fopen ("gutui.out", "w");
	u_int H, U, **a, cules = 0, h_mom;
	int N, i, n;
	vector<u_int> momentan;
	vector<u_int>::iterator it;
//citire date	
	fscanf(f, "%d %u %u", &N, &H, &U);
	n = N;
	a = (u_int**)malloc(N*sizeof(u_int*));
	for(i = 0; i < N; i ++){
		a[i] = (u_int*)malloc(2*sizeof(u_int));
		fscanf(f, "%u %u", &a[i][0], &a[i][1]);
	}
//sortarea gutuilor	
	sort(a, a+N, desc);
//pornesc de la ultimul nivel, cel mai jos	
	if(H%U == 0)
		h_mom = U;
	else
		h_mom = H - ((H / U) * U);
		
	//h_mom -= U;
//incep sa "culeg" gutui, pornind de la ultimul nivel
	while((h_mom <= H) && (N > 0 || momentan.size() > 0)){
		
//parcurge un nivel
		while(N > 0){
//s-a terminat nivelul -> iese din while
			if(a[N-1][0] > h_mom)
				break;
//pune gutuile de pe nivel in momentan			
			momentan.push_back(a[N-1][1]);
			N --;
			push_heap(momentan.begin(), momentan.end());
		}
//culege maximul din heap si il elimina
		if(momentan.size() > 0){
			cules = cules + momentan.front();
			pop_heap(momentan.begin(), momentan.end());
			momentan.pop_back();
			h_mom = h_mom + U;
		}
		else
			h_mom = h_mom + U*max((a[N-1][0]-h_mom)/U, 1);
	}
//eliberare memorie
	for(i = 0; i < n; i ++)
		free(a[i]);
	free(a);
//afisare rezultat	
	fprintf(g, "%u", cules);
	return 0;
}