Cod sursa(job #436867)

Utilizator dodgerblueBogdan P. dodgerblue Data 9 aprilie 2010 00:23:03
Problema Gutui Scor 30
Compilator cpp Status done
Runda teme_upb Marime 2.4 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) { 
	if(c1.h > c2.h)
		return true;
	if(c1.h == c2.h && c1.g > c2.g)
		return true;
	return false;
}

bool comp2(gutuie c1, gutuie c2){
	if(c1.h < c2.h)
		return true;
	if(c1.h == c2.h && c1.g > c2.g)
		return true;
	return false;
}

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

void afisare(){
		int i;
		for(i=0;i<N;i++)
			printf("Gutuia %d: h = %d g = %d\n",i+1,gutui[i].h,gutui[i].g);
		printf("--------------\n");
}

int main(){
	
	int i,k,hc,j,t,pe_niv;
	int max = 0;
	int M;
	int *heap,dimheap = 0;
	
	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 ;
	heap = (int*)calloc(M,sizeof(int));
	
	//afisare();
	
	sort(gutui,gutui+N,comp2);
	
	//afisare();
	
	
	/*
	k = 0;
	while(k<N){
		if(gutui[k].h>0){
			hc = gutui[k].h;
			max = max + gutui[k].g;
			for(i=k+1;i<N;i++)
				if(gutui[i].h>=hc)
					gutui[i].h--;
		}
		k++;
	}
	
	fprintf(g,"%d\n",max);
	
	*/
	
	//afisare();
	
	i = M-1;
	j= N - 1;
	k = 0;
	pe_niv = 0;
	
	//printf("Uite atatea gutui: %d %d\n",M,j);
	
	while(j>=0){
		//printf("Gutuia %d cu h %d si g %d suntem pe nivelul %d cu %d fructe luate\n",j,gutui[j].h,gutui[j].g,i,pe_niv);
		if(gutui[j].h!=i){
				i--;
				pe_niv = 0;
		}
		if(pe_niv<=gutui[j].h) // se respecta chestia cu triunghiul - nu se pot adauga 2 gutui de pe nivelul 1
			if(k<M){
				heap[k] = gutui[j].g;
				k++;
				push_heap(heap,heap+k,compheap);
				
			}
			else{
				if(heap[0]<gutui[j].g){
					pop_heap(heap,heap+M,compheap);
					heap[M-1] = gutui[j].g;
					push_heap(heap,heap+M,compheap);
				}
			}
		pe_niv++;
		j--;
		
		//for(t=0;t<k;t++)
		//	printf("%d ",heap[t]);
		//printf("\n");
		
	}
	
	for(i=0;i<M;i++)
		max = max + heap[i];
	fprintf(g,"%d\n",max);
	
	fclose(f);
	fclose(g);
	return 0;
	
}