Cod sursa(job #422623)

Utilizator RaphyRafailescu Marius Raphy Data 22 martie 2010 22:19:17
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.65 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{
			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){
		j=i-1;best=v[i].g;
		while(v[i].h==v[j].h && j >= 0){
			if (best<v[j].g) best=v[j].g;
			--j;
		}
		//printf("h=%d best=%d ",h,best);
		max+=best;
		h-=u;
	}
}
/*for (i=0;i<n-1;++i)
{
j=i+1;best=v[i].g;
while(v[i].h==v[j].h){
	if (best<v[j].g) best=v[j].g;
	j++;
}
}*/
	
fprintf(out,"%d\n",max);

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