Cod sursa(job #442122)

Utilizator alinatomaToma Alina alinatoma Data 13 aprilie 2010 21:41:30
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.1 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define INF 1000


void swap(int *x,int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}

int choose_pivot(int i,int j )
{
   return((i+j) /2);
}

void quicksort(int list[], int list2[],int m,int n)
{
   int key,i,j,k;
   if( m < n)
   {
      k = choose_pivot(m,n);
      swap(&list[m],&list[k]);
      swap(&list2[m],&list2[k]);
      key = list[m];
      i = m+1;
      j = n;
      while(i <= j)
      {
         while((i <= n) && (list[i] >= key))
                i++;
         while((j >= m) && (list[j] < key))
                j--;
         if( i < j)
         	{
                swap(&list[i],&list[j]);
                swap(&list2[i],&list2[j]);
                }
      }
	  // swap two elements
      swap(&list[m],&list[j]);
      swap(&list2[m],&list2[j]);
	  // recursively sort the lesser list
      quicksort(list,list2,m,j-1);
      quicksort(list,list2,j+1,n);
   }
}
void printlist(int list[],int n)
{
   int i;
   for(i=0;i<n;i++)
      printf("%i ",list[i]);
   printf("\n");
}


int main()
{

int N, H, U, i, j, k, max, maxx;
int* inaltime;
int* greutate;
int** best;
FILE* f;
FILE* g;

f= fopen("gutui.in","r");
fscanf(f, "%i %i %i\n", &N, &H, &U);

inaltime = (int*)calloc(N,sizeof(int*));
greutate = (int*)calloc(N,sizeof(int*));
best = (int**)calloc(N,sizeof(int*));

for (i=0; i<N; i++)
	{
	fscanf(f, "%i %i\n", &inaltime[i], &greutate[i]);
	best[i] = (int*)calloc(N,sizeof(int));
	}
	

   
   // sortez descrescator dupa inaltime
   quicksort(inaltime,greutate,0,N-1);

  
   
for (i=0;i<N;i++)
	if (inaltime[i]<=H)
		best[i][0] = greutate[i];
	else
		best[i][0] = -INF;


for (i=0;i<N;i++)
	for(k=1;k<N;k++)
			{
			
			if (inaltime[i]+k*U <= H)
				{
				max=0;
				for(j=0;j<i;j++)
					if (best[j][k-1]>max)
						max=best[j][k-1];
				best[i][k] = greutate[i] + max;	
				}
			else best[i][k] = -INF;
			}


maxx=0;
for (i=1;i<N;i++)
	//{
	//for (j=0;j<N;j++)
		{
		if (best[N-1][j]>maxx)
			maxx=best[i][j];
		//printf("%i ",best[i][j]);
		}
	//printf("\n");
	//}


g= fopen("gutui.out","w");
fprintf(g, "%i", maxx);
fclose(f);
fclose(g);

return 0;
}