Cod sursa(job #435278)

Utilizator PacoGeorgescu Claudiu Paco Data 7 aprilie 2010 10:42:58
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 4.03 kb
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
/*	Structura heap_vector_struct retine heap-ul avand drept camp un vector de intregi , si alte doua campuri
 *	reprezentand capacitatea , repsectiv dimensiunea heap-ului . 
*/	
typedef struct heap_vector_struct 
{
    int *values;
    int dimVect;
    int capVect;
    int niv;
} HeapVector;

typedef struct gutui{
	int h;
	int g;
} gutui;

int DescS(HeapVector *h, int poz)
{
	if ((2*poz+1)>=h->dimVect) 
			return -1;
		else
			return (2*poz+1);	
}

int DescD(HeapVector *h, int poz) 
{
	if ((2*poz+2)>=h->dimVect) 
			return -1;
		else
			return (2*poz+2);	
}

int Parinte(HeapVector *h, int poz)
{
	if (poz==0) 
			return -1;
		else
			return (poz-1)/2; 
		
}

HeapVector* CV(int capVect)
{
	HeapVector *h;
	h=(HeapVector*)malloc(sizeof(HeapVector));
	h->values=(int*)calloc(capVect,sizeof(int));
	h->dimVect=0;
	h->capVect=capVect;
	h->niv=-1;	
	return h;
}
	
void ElibereazaVector(HeapVector *h)
{
	free(h->values);
	free(h);
}

void CoboaraValoare(HeapVector *h, int poz)
{
	int pozdesc=0;
	int valmax,aux;	
	for (;;) 
		{ 
			valmax=h->values[poz];	
			if (DescS(h,poz)!=-1)
				if (h->values[DescS(h,poz)]>valmax)
					valmax=h->values[DescS(h,poz)];
			if (DescD(h,poz)!=-1)
				if (h->values[DescD(h,poz)]>valmax)
					valmax=h->values[DescD(h,poz)];			
    		if (valmax==h->values[poz])
				return; 
            if (DescS(h,poz)!=-1&&valmax==h->values[DescS(h,poz)])
        		    pozdesc=DescS(h,poz);
        		else
        		if (DescD(h,poz)!=-1)
            		pozdesc=DescD(h,poz); 
   			aux=h->values[pozdesc];
   			h->values[pozdesc]=h->values[poz];
    		h->values[poz]=aux;
    		poz=pozdesc;
   		 }
}
void UrcaValoare(HeapVector *h,int poz) {
	int aux;	
    while (poz>0&&h->values[poz]>h->values[Parinte(h,poz)]) 
    	{
 			aux=h->values[Parinte(h,poz)];
 			h->values[Parinte(h,poz)]=h->values[poz];
 			h->values[poz]=aux;    
       		poz=Parinte(h,poz);
    	}
 } 

int Maxim(HeapVector *h){
	assert(h->dimVect>0) ;
	return h->values[0];
}

int ExtrageMaxim(HeapVector *h){
	assert(h->dimVect>0);	
	int min,aux;
	min=h->values[0];
	aux=h->values[0];
	h->values[0]=h->values[h->dimVect-1];
	h->values[h->dimVect-1]=aux;
	h->dimVect--;
	CoboaraValoare(h,0);
	return min;
 }   

void AdaugaValoare(HeapVector *h,int val){
	if (h->dimVect==h->capVect){
		h->capVect=2*h->capVect;
		h->values=(int*)realloc(h->values,h->capVect*sizeof(int));
	}
	h->dimVect++;
	h->values[h->dimVect-1] = val;
	UrcaValoare(h,h->dimVect-1);
}    

int size(HeapVector *h){
	return h->dimVect;
}

int partitie(gutui x[],int s,int d){
	int piv=x[s].h;
	int j=d+1,i=s-1;
	gutui aux;		
	while(1){
		do{j--;} while(x[j].h>piv);
		do{i++;} while(x[i].h<piv);
		if (i<j){
			aux=x[i];
			x[i]=x[j];
			x[j]=aux;
		}
	else return j;
		}
	}
	
void quicksort(gutui x[],int s,int d){
		if(s<d){
			int p=partitie(x,s,d);
			quicksort(x,s,p);
			quicksort(x,p+1,d);
		}
	}



int main(){
	FILE *f=fopen("gutui.in","r");
	FILE *g=fopen("gutui.out","w");
	int u,h,n,i,j=1,max,poz,s=0;
	gutui *fr;
	HeapVector** zona;

	fscanf(f,"%d%d%d",&n,&h,&u);
	fr=(gutui*)malloc(n*sizeof(gutui));
	for (i=0;i<n;i++)
		fscanf(f,"%d%d",&fr[i].h,&fr[i].g);
	int k=h/u+1,niv;
	zona=(HeapVector**)calloc(k,sizeof(HeapVector*));
	int nr=-1,r=-1;
	quicksort(fr,0,n-1);
	//for (i=0;i<n;i++)
	//		printf("%d %d\n",fr[i].h,fr[i].g);
	for (i=0;i<n;i++){
		niv=k-1-(h-fr[i].h)/u;
		if(r==niv)
			AdaugaValoare(zona[nr],fr[i].g);
		else{
			nr++;
			zona[nr]=CV(1);
			AdaugaValoare(zona[nr],fr[i].g);
			zona[nr]->niv=niv;
			r=niv;
		}
	}	
	nr++;
	/*for (i=0;i<nr;i++){
		printf("%d : ",zona[i]->niv);
		for (j=0;j<size(zona[i]);j++)
				printf("%d ",zona[i]->values[j]);
		printf("\n");
	}*/		
	j=1;  			
	while (1){
		max=-1;
		poz=-1;
		for (i=0;i<nr;i++)
			if(zona[i]->niv>=j) 
				break;
			else	
				if (size(zona[i])!=0&&Maxim(zona[i])>max){
				max=Maxim(zona[i]);
				poz=i;
				}					
		if (poz!=-1){
			s+=max;
			ExtrageMaxim(zona[poz]);
		}
		j++;
		if (j==k+1) break;

	}
	for (i=0;i<nr;i++)
		ElibereazaVector(zona[i]);
	fprintf(g,"%d\n",s); 
	fclose(f);
	fclose(g);
	return 0;
}