Cod sursa(job #422638)

Utilizator RaphyRafailescu Marius Raphy Data 22 martie 2010 22:39:14
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.6 kb
#include <stdio.h>  
#include <stdlib.h>  

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

void merge(int starts,int startd,int stopd,gutuie *a){  
	int n=stopd-starts+1;  
	int is=starts,id=startd,stops=startd-1,it=0,i;  
	gutuie *temp=(gutuie*)malloc(n*sizeof(gutuie));  
   
	while(is<=stops && id<=stopd) { 
		if (a[is].h<a[id].h){
			temp[it].h=a[is].h;
			temp[it++].g=a[is++].g;
		}
		else if (a[is].h > a[id].h){
			temp[it].h=a[id].h;
			temp[it++].g=a[id++].g;
		}  else{ //egale
			if (a[is].g < a[id].g){
				temp[it].h=a[is].h;
				temp[it++].g=a[is++].g;
			}
			else {
				temp[it].h=a[id].h;
				temp[it++].g=a[id++].g;
			}
		}
	}
	while (is<=stops){
		temp[it].h=a[is].h;
		temp[it++].g=a[is++].g;
	}
	while (id<=stopd){
		temp[it].h=a[id].h;
		temp[it++].g=a[id++].g;
	}   
	  
	for (i=0;i<n;i++){
		a[starts+i].h=temp[i].h;
		a[starts+i].g=temp[i].g;
	}
	free(temp);  
}  
   
void MS(int s,int d,gutuie *a){  
if (s<d)  
    {  
    int m=(s+d)/2;  
    MS(s,m,a);  
    MS(m+1,d,a);  
    merge(s,m+1,d,a);  
    }  
}  
  
void MergeSort(int n,gutuie *a){  
    MS(0,n-1,a);  
}  
   
int main(){  
int n,h,u,i,max=0,j,best;  
FILE *in,*out;  
in=fopen("gutui.in","rt");  
out=fopen("gutui.out","wt");  
fscanf(in,"%d%d%d",&n,&h,&u);
gutuie *v=(gutuie*)calloc(n,sizeof(gutuie));  
for (i=0;i<n;++i)  
    fscanf(in,"%d%d",&v[i].h,&v[i].g);  
MergeSort(n,v); 
j=n-1; 
for (i=j;i>=0;--i){
	//printf("i=%d ",i);
	if (v[i].h<=h){
		max+=v[i].g;
		h-=u;
	}
}
fprintf(out,"%d\n",max);

free(v);
fclose(in);  
fclose(out);  
return 0;  
}