Cod sursa(job #441059)

Utilizator vitalie23vitalie vitalie23 Data 12 aprilie 2010 18:56:28
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.4 kb
#include <stdio.h>
#include <stdlib.h>


void swap (long *vec, long n, long poz)
{
	long aux;
	
	aux = vec[n - 1];
	vec[n - 1] = vec[poz];
	vec[poz] = aux;
}


void quicksort (long *high, long *wheight, long left, long right)
{ 
    long i = left;
	long j = right;
	long aux;
    long x = wheight[left];
    do
    {    
        while (wheight[i] > x) i++;
        while (wheight[j] < x) j--;
        if (i<=j)
        {
            aux = wheight[i]; wheight[i] = wheight[j]; wheight[j] = aux;
            aux = high[i]; high[i] = high[j]; high[j] = aux;
            i++; j--;
        }
    } while (i <= j);
    if (left < j) quicksort(high, wheight, left, j);
    if (i < right) quicksort(high, wheight, i, right);
}


long getLevel (long x, long h, long u, long nr)
{
	h -= u;
	while (x <= h)
	{
		nr--;
		h -= u;
	}
	return nr;
}

int main ()
{
	long n, h, u;
	long *high, *wheight;
	FILE *fin, *fout;
	long i, nrLevel = 0, temp;
	long gmax = 0;
	long *aux;
	long level, tempNrLevel, nrGutui = 0;
	int zero = 0;
	
	fin = fopen ("gutui.in", "r");
	if (fin == NULL)
	{
		printf("reading error!\n");
		exit(0);
	}
	fout = fopen ("gutui.out", "w");
	
	fscanf(fin, "%ld %ld %ld", &n, &h, &u);
	
	high = (long*)malloc (n * sizeof (long));
	wheight = (long*)malloc (n * sizeof (long));
	
	for (i = 0; i < n; i++)
	{
		fscanf(fin, "%ld %ld", &high[i], &wheight[i]);
	}
	quicksort (high, wheight, 0, n-1);
	
	temp = h;
// cate gutuie maxim pot culege
	while (temp > 0)
	{
		temp -= u;
		nrLevel++;
	}
	temp = nrLevel;
	aux = (long*)malloc (nrLevel * sizeof (long));
	for (i = 0; i < nrLevel; i++)
	{
		aux[i] = temp;
		temp--;
	}

	tempNrLevel = nrLevel;
	i = 0;
	do
	{
		if (high[i] > h)
		{
			i++;
			continue;
		}
		if (high[i] == 0)
		{
			if (zero == 0)
			{
				zero++;
				tempNrLevel++;
			}
//			printf("Culeg gutuia\n");
			nrGutui++;
			gmax += wheight[i];
			i++;
			continue;
		}
		level = getLevel (high[i], h, u, nrLevel - 1);
// culeg gutuia
		if (aux[level] > 0)
		{
			while (level >= 0)
			{
				aux[level]--;
				if (aux[level] == 0)
				{
					temp = level;
					while (temp < nrLevel)
					{
						aux[temp] = 0;
						temp++;
					}
				}
				level--;
			}
			gmax += wheight[i];
			nrGutui++;
		}
		i++;
	}while (i < n && nrGutui < tempNrLevel);
	
	fprintf(fout, "%ld\n", gmax);


	return 0;
}