Cod sursa(job #426927)

Utilizator stefansStefan-Gabriel Sicleru stefans Data 27 martie 2010 13:30:08
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 2.96 kb
/*
N - numar de gutui din copac
H - inaltimea maxima la care ajunge Gigel
U - cu cat se ridica crengile dupa ridicarea unei gutui
*/

#include<stdio.h>
#include<stdlib.h>
#define MAX 100000


struct pair 
{
	int inaltime;
	int greutate;
};


void merge(struct pair *vector, int start, int middle, int end)
{
	int i,j;
	int n = middle - start + 1;
	int m = end - middle;
	struct pair *left = (struct pair *)calloc(n, sizeof(struct pair)); //parcurs cu i
	struct pair *right  = (struct pair *)calloc(m, sizeof(struct pair)); //parcurs cu j
	//copiez elementele
	for (i=0;i<n;i++)
		left[i] = vector[start+i];
	for (i=0;i<m;i++)
		right[i] = vector[middle +1 +i];
	
	
	i = 0; 
	j = 0;
	int k = start;
	while (i<n && j<m)
	{
		if (left[i].inaltime < right[j].inaltime)
			vector[k++] = left[i++];
		else 
			vector[k++] = right[j++];	
	}
	while (i<n)
		vector[k++] = left[i++];
	while (j<m)
		vector[k++] = right[j++];
	free(left);
	free(right);
}

void mergeSort(struct pair *vector, int start, int end)
{
	int middle;
	if (start < end)
	{
		middle = (start+end)/2;
		mergeSort(vector, start, middle);
		mergeSort(vector, middle+1, end);
		merge(vector, start, middle, end);
	}
}

int enabled[MAX];
int main()
{
	FILE *in = fopen("gutui.in", "r");
	FILE *out = fopen("gutui.out", "w");
	struct pair p[MAX];
	int n, h, u, i, k=0; 
	int temp_h, temp_g;
	fscanf(in, "%d%d%d", &n, &h, &u);
	for (i=0; i<n; i++){
		fscanf(in, "%d%d", &temp_h, &temp_g);
		if (temp_h<=h)
		{
			p[k].inaltime=temp_h;
			p[k].greutate=temp_g;
			k++;
		}
	}
	n = k; //!! aici raman doar la gutuile la care pot ajunge
	/*
	printf("\n-------------\n");
	for (i=0;i<n;i++)
		printf("[%d %d] ",p[i].inaltime, p[i].greutate);
	*/
	mergeSort(p, 0, n-1);
	/*
	printf("\n");
	for (i=0;i <n; i++)
		printf("[%d %d] ",p[i].inaltime, p[i].greutate);
	printf("\n-------------\n\n");
	*/
	
	
	//rezolvare
		
	int greutateMaxima=0, min,j;
	int addedHeight=0, minhelper;
	min=p[n-1].greutate;
	for (i=n-1;i>=0;i--)
	{
		if (p[i].inaltime+addedHeight<=h)
		{
				enabled[i]=1;
				greutateMaxima += p[i].greutate;
				addedHeight+=u; //actualizez addedHeight
				//actualizez min daca este nevoie
				if (p[i].greutate < min)
					min = p[i].greutate;
		}
		else
		{
			//nu modific addedHeight
			//vad daca e mai mare decat minimul solutiei anterioare
			if (p[i].greutate > min)
			{
				//atunci inseamna ca trebuie adaugat
				greutateMaxima -= min;
				greutateMaxima += p[i].greutate;
				enabled[i] = 1;
				//actualizez minim
				for (j=i+1;j<n;j++)
					if (enabled[j]==1&&p[j].greutate==min)
						{enabled[j] = 0;break;}
				minhelper=p[i].greutate;
				for (j=i+1;j<n;j++)
					if (enabled[j] && p[j].greutate<minhelper 
						&& p[j].greutate >=min)
							minhelper = p[j].greutate;
				min=minhelper;
				
				
			}
			
		}	
	}
	
	//afisez la ecran
	//printf("\ngreutate: %d\n", greutateMaxima);
	//printf("\n");
	//for (i=n-1;i>=0;i--)
		//printf("%d ",enabled[i]);
	fprintf(out,"%d",greutateMaxima);
	
	
	
	
	
	//EXIT
	fclose(in);
	fclose(out);
	return 0;
}