Cod sursa(job #431949)

Utilizator PacoGeorgescu Claudiu Paco Data 1 aprilie 2010 17:53:44
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2 kb
#include <stdio.h>
#include <stdlib.h>

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

typedef struct node {
	gutui fr;
	struct node* next;
} node;

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;
	gutui *fr;
	node** 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);
	quicksort(fr,0,n-1);
	zona=(node**)malloc(n*sizeof(node*));
	node *p,*q;
	int k=-1;	
	int r=-1;
	for (i=0;i<n;i++){
		p=(node*)malloc(sizeof(node));
		p->fr=fr[i]; 
		if ((h-fr[i].h)/u==r){
			//p->next=zona[k];
			//zona[k]=p;
			if (zona[k]->fr.g<p->fr.g){
				p->next=zona[k];
				zona[k]=p;
			}
			else{	
				q=zona[k];
				while(q->next!=NULL&&q->next->fr.g>p->fr.g)
					q=q->next;
				p->next=q->next;
				q->next=p;
			}		
			//printf("%d %d|",fr[i].h,fr[i].g);
			}
			else {
				k++;
				p->next=NULL;
				zona[k]=p;
				//printf("\n");
				//printf("%d %d|",fr[i].h,fr[i].g);
				r=(h-fr[i].h)/u;
				}
		}		
	k++;
		
	/*for (i=0;i<k;i++){
		p=zona[i];
		while(p!=NULL){
			printf("%d %d : ",p->fr.h,p->fr.g);
			p=p->next;
		}
		printf("\n");
	}
	 */	
	int j=1,max,poz,s=0,ok=0,hi=0;		
	while (1){
		max=-1;
		ok=0;
		for (i=0;i<j;i++)
			if(zona[i]!=NULL&&zona[i]->fr.g>max&&zona[i]->fr.h<=h){
				max=zona[i]->fr.g;
				poz=i;
				ok=1;
			}
		if(ok==1){	
		//printf("Am ales %d %d\n",zona[poz]->fr.h,zona[poz]->fr.g);
		s+=zona[poz]->fr.g;
		zona[poz]=zona[poz]->next;
		h=h-u;	
		}
		else
		    j++;
		if(h<0) break;    
		if (j==k+1) break;
	}		
	fprintf(g,"%d\n",s); 
	
	//for (i=0;i<n;i++)
	//		printf("%d %d\n",fr[i].h,fr[i].g);
	fclose(f);
	fclose(g);
	return 0;
}