Cod sursa(job #440762)

Utilizator DetudaArthur Koestler Detuda Data 12 aprilie 2010 15:01:26
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.14 kb
//UNGUREANU CRISTIAN 324CA
//TEMA 1 PA - GUTUI

#include <stdio.h>

	// nr gutui, inaltimea maxima, inaltarea, rezultatul final
	long n, hi, u, smax;
	// inantimea fiecarei gutui si greutatea
	long h[100001], w[100001], i, j, k, l, pozmin;
	long h1[100001], w1[100001], imin; // vectori auxiliari si alte variabile

//functii pentru quicksort
void swap(long *x, long *y)
{
   long auxi;
   auxi = *x;
   *x = *y;
   *y = auxi;
}

long pivot(long i, long j)
{
   return((i+j)/2);
}

void quicksort(long m, long n)
{
   long i, j, k, l;
   if( m < n)
   {
      k = pivot(m, n);
      swap(&h[m], &h[k]);
      swap(&w[m], &w[k]);
      l = h[m];
      i = m+1;
      j = n;
      while(i <= j)
      {
         while((i <= n) && (h[i] >= l))
                i++;
         while((j >= m) && (h[j] < l))
                j--;
         if( i < j)
         {
		swap(&h[i], &h[j]);
		swap(&w[i], &w[j]);
	 }
      }
      swap(&h[m], &h[j]);
      swap(&w[m], &w[j]);
      quicksort( m, j-1);
      quicksort( j+1, n);
   }
}

int main()
{
	FILE *f=fopen("gutui.in", "r");
	FILE *g=fopen("gutui.out", "w");
	fscanf(f, "%ld %ld %ld", &n, &hi, &u);
	for(i=0; i<n; i++)
	fscanf(f, "%ld %ld", &h[i], &w[i]);

	//sortam descrescator fructele, in functie de inaltime
	quicksort(0, n-1);
	/*
	printf("Dupa quicksort, ordonate in functie de greutate: \n");
	for(i=0; i<n; i++)
	{
		printf("fructul %ld are inaltimea %ld si greutatea %ld\n", i, h[i], w[i]);
	} 
	*/
	smax=0;

	k=0;
	for(i=0; i<n; i++)
		if(h[i]<=hi)
		{
			w1[k]=w[i];
			h1[k]=h[i];//
			k++;
			smax+=w[i];
			if(hi>=u) // in loc sa crestem fiecare inaltime la fiecare pas, scadem u din hi la fiecare pas
				hi-=u;
			else
				hi=0;
		}
		else
		{
			pozmin=0;
			for(j=1; j<k; j++)
				if(w1[j]<w1[pozmin])
					pozmin=j;
			if(w[i]>w1[pozmin])
			{
			/*	smax+=w[i];
				smax-=w1[pozmin];
				w1[pozmin]=w[i];
				w1[pozmin]=h[i];//
				*/
				smax = smax + w[i] - w1[pozmin];
				w1[pozmin]=w[i];
				h1[pozmin]=h[i];//
			}
		}

	//printf("%ld\n", smax);
	fprintf(g, "%ld", smax);	
	fclose(f);
	fclose(g);
	return 0;
}