Cod sursa(job #439585)

Utilizator dodgerblueBogdan P. dodgerblue Data 11 aprilie 2010 17:16:33
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.43 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>

using namespace std;

int N,H,U;

typedef struct {
		int h,g;
} gutuie;

gutuie *gutui;

FILE *f,*g;

bool comp(gutuie c1, gutuie c2) { 
	return c1.h > c2.h;
		return true;
}

bool compheap(int c1, int c2){
	return c1 > c2;
}

int main(){
	
	int i,k,hc,j;
	int max = 0;
	int M;
	int *heap;
	
	f = fopen("gutui.in","r");
	g = fopen("gutui.out","w");
	
	fscanf(f,"%d %d %d\n",&N,&H,&U);
	gutui = (gutuie*)calloc(N,sizeof(gutuie));
	
	for(i=0;i<N;i++)
		fscanf(f,"%d %d\n",&gutui[i].h,&gutui[i].g);
		
	//afisare();
	sort(gutui,gutui+N,comp);
	//afisare();
	
	//se elimina gutuile care sunt la inaltimi mai mari de H
	k=0;
	while(gutui[k].h>H)
		k++;
	for(i=0;i<N-k;i++)
		gutui[i]=gutui[i+k];
	N=N-k;
	//afisare();
	
	k = 0;
	hc = H;
	i = 0;
	
	while(i<N){
			while(gutui[i].h<=hc && gutui[i].h>(hc-U) && i<N){
				gutui[i].h = k;
				i++;
			}
			hc = hc - U;
			k++;
	}
	
	M = k ;
	if(N<M) M = N;
	heap = (int*)calloc(N,sizeof(int));
	
	i = 0;
	j= 0;
	k = 0;
	
	while(j<N){
		if(gutui[j].h!=i){
				i = gutui[j].h;
		}
			if(k<=i){
				heap[k] = gutui[j].g;
				k++;
				push_heap(heap,heap+k,compheap);
				
			}
			else{
				if(heap[0]<gutui[j].g){
					pop_heap(heap,heap+k,compheap);
					heap[k-1] = gutui[j].g;
					push_heap(heap,heap+k,compheap);
				}
			}
		j++;
		
	}
	
	for(i=0;i<k;i++)
		max = max + heap[i];
	fprintf(g,"%d\n",max);
	
	fclose(f);
	fclose(g);
	return 0;
	
}