Cod sursa(job #433954)

Utilizator tigora_andreitigora andrei tigora_andrei Data 4 aprilie 2010 19:45:15
Problema Gutui Scor 90
Compilator c Status done
Runda teme_upb Marime 3.67 kb
//Tigora Andrei 322CA
#include<stdio.h>
#include<stdlib.h>

typedef struct	{
		int w;
		int h;
		} gutuie;
typedef struct	{
		int max;
		int crt;
		int* w;
		} heap;

int compare(gutuie a,gutuie b){
	if(a.h<b.h)
		return -1;
	if(a.h>b.h)
		return 1;
	if(a.w>b.w)
		return -1;
	if(a.w<b.w)
		return 1;
	return 0;
}


void merge_sort(gutuie *vect,int size){
	
	gutuie aux;
	
	if(size==1)		
		return;
	if(size==2){
		if(compare(vect[0],vect[1])>0){
			aux = vect[0];
			vect[0] = vect[1];
			vect[1] = aux;
		}
		return;
	}
	int middle = size/2,i,j,crt;
	gutuie *vect1 = malloc((middle)*sizeof(gutuie));
	gutuie *vect2 = malloc((size-middle)*sizeof(gutuie));
	for(i=0;i<middle;i++)
		vect1[i] = vect[i];
	for(i=middle;i<size;i++)
		vect2[i-middle] = vect[i];
	
	merge_sort(vect1,middle);
	merge_sort(vect2,size-middle);
	
	i = 0, j = 0, crt = 0;
	while(i<middle && j<size-middle)
		if(compare(vect1[i],vect2[j])<=0)
			vect[crt++] = vect1[i++];
		else
			vect[crt++] = vect2[j++];
	while(i<middle)
		vect[crt++] = vect1[i++];
	while(j<size-middle)
		vect[crt++] = vect2[j++];
	free(vect1);free(vect2);
}

void remove_first(heap *choice){
	choice->crt--;
	choice->w[0] = choice->w[choice->crt];
	int poz = 0;
	int aux;
	while(1){
		if(poz*2+2<choice->crt){	//are ambii fii
			if(choice->w[poz*2+1]<choice->w[poz]){
				if(choice->w[poz*2+2]<choice->w[poz*2+1]){
					aux = choice->w[poz];
					choice->w[poz] = choice->w[poz*2+2];
					choice->w[poz*2+2] = aux;
					poz = poz*2+2;
				}
				else{
					aux = choice->w[poz];
					choice->w[poz] = choice->w[poz*2+1];
					choice->w[poz*2+1] = aux;
					poz = poz*2+1;
				}
			}
			else{
				if(choice->w[poz*2+2]<choice->w[poz]){
					aux = choice->w[poz];
					choice->w[poz] = choice->w[poz*2+2];
					choice->w[poz*2+2] = aux;
					poz = poz*2+2;
				}
				else
					break;
			}
		}
		else
			if(poz*2+2<choice->crt){
				if(choice->w[poz*2+1]<choice->w[poz]){
					aux = choice->w[poz];
					choice->w[poz] = choice->w[poz*2+1];
					choice->w[poz*2+1] = aux;
					poz = poz*2+1;
				}
				else
					break;
			}
			else
				break;
	}
}

void add(heap *choice,int val){
	int poz = choice->crt;
	int aux;
	choice->crt++;
	choice->w[poz] = val;
	while(poz)
		if(choice->w[poz]<choice->w[(poz-1)/2]){
			aux = choice->w[poz];
			choice->w[poz] = choice->w[(poz-1)/2];
			choice->w[(poz-1)/2] = aux;
			poz = (poz-1)/2;
		}
		else
			break;	
}

int main(){
	int i,crt,n;
	gutuie *vect;
	int high_max,low;
	long long suma = 0;
	heap choice;
	FILE *in,*out;
	//File *test;
	
	
	in = fopen("gutui.in","r");
	out = fopen("gutui.out","w");
	//test = fopen("test.out","w");
	
	fscanf(in,"%d%d%d",&n,&high_max,&low);
	vect = malloc(n*sizeof(gutuie));
		
	crt = 0;
	for(i=0;i<n;i++){
		fscanf(in,"%d%d",&vect[i].h,&vect[i].w);
		if(vect[crt].h<=high_max){	//	gutuie accesibila
			crt++;
		}
	}
	
	if(crt==0){
		fprintf(out,"%lld",suma);
		return 0;
	}
	
	n = crt;
	//	Inaltimea este inlocuita cu nivelul corespunzator
	for(i=0;i<n;i++)
		vect[i].h = ((high_max - vect[i].h) / low) + 1;
	//	Sorteaza corespunzator
	merge_sort(vect,n);
	//	Initializeaza minheapul
	if(vect[n-1].h > n){
		choice.w = malloc(n*sizeof(int));
		choice.max = n;
	}
	else{
		choice.w = malloc(vect[n-1].h*sizeof(int));
		choice.max = vect[n-1].h;
	}
	choice.crt=0;
	
	//	Adauga in minheap
	for(i=0;i<n;i++){
		if(vect[i].h>choice.crt)//mai sunt gutui accesibile pe nivelul curent
			add(&choice,vect[i].w);
		else if(vect[i].w > choice.w[0]){//gutuia curenta reprezinta o alegerea mai buna decat cea mai slaba alegere anterioara
			remove_first(&choice);
			add(&choice,vect[i].w);
		}
	}
	
	while(choice.crt){
		suma+=choice.w[0];
		remove_first(&choice);
	}
	
	fprintf(out,"%lld",suma);
	fclose(in);fclose(out);//fclose(test);
	//	End
	return 0;
}