Cod sursa(job #434191)

Utilizator RaphyRafailescu Marius Raphy Data 5 aprilie 2010 12:04:32
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.12 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,total=0,ch,k;  
FILE *in,*out;  
in=fopen("gutui.in","r");  
out=fopen("gutui.out","w");  
fscanf(in,"%d%d%d",&n,&h,&u);
gutuie *v=(gutuie*)calloc(n,sizeof(gutuie));
best=(int*)calloc(n,sizeof(int));  
for (i=0;i<n;++i){
    fscanf(in,"%d%d",&v[i].h,&v[i].g);
	total+=v[i].g;
}
MergeSort(n,v); 
/*printf("Gutui sortate\n");
for (i=0;i<n;i++){
	printf("%d %d\n",v[i].h,v[i].g);
	}*/
for (j=0;j<n;j++){
	ch=h; 
	max=0;
	//printf("Incep cu gutuia de pe poz %d\n",n-1-j);
	for (i=n-1-j;i>=0;--i){
		if (v[i].h<=ch){
			//printf("O aleg pe cea de la %d\n",i);
			max+=v[i].g;
			//ch=v[i].h-u;
			for (k=j;k<i;k++)
			v[k].h+=u;
		}
	}
	
	best[j]=max;
	//printf("Pot lua maxim %d\n",max);
	if (max == total) break;
}
max=best[0];
//printf("%d\t",best[0]);
for (i=1;i<n;i++){
	//printf("%d\t",best[i]);
	if (best[i]>max) max=best[i];}
fprintf(out,"%d",max);

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