Cod sursa(job #442071)

Utilizator alinatomaToma Alina alinatoma Data 13 aprilie 2010 20:52:00
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 3.79 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define INF 1000
#define MAX(a, b)  (((a) > (b)) ? (a) : (b))



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 max(int mat[][], int i, int j)
{
int l, m;
int max=-1;
for (l=0;l<i;l++)	
	for (m=0;m<j;m++)
		if (mat[l][m]>max)
			max = mat[l][m];
return max;
}*/

int main()
{

int N, H, U, i, j, k, maxx;
int* inaltime;
int* greutate;
int* max_col;
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*));
max_col = (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);

   // print the result
   //printf("The list after sorting using quicksort algorithm:\n");
  // printlist(inaltime,N);
   //printlist(greutate,N);
   
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 (j=0;j<N;j++)
		printf("%i ",best[i][j]);
	printf("\n");
	}*/
	
//for (i=0;i<N;i++)
//	max_col[0]=MAX(max_col[0], best[i][0]);

for (i=0;i<N;i++)
	for(k=1;k<N;k++)
			{
			if (inaltime[i]+k*U <= H)
				{
				//max_col[k]=MAX(max_col[k],best[i][k]);
				
				//max=0;
				//for(j=0;j<i;j++)
					//if (best[j][k-1]>max)
						//max=best[j][k-1];
				//printf("max=%i\n",max);
				best[i][k] = greutate[i] + max_col[k];	
				max_col[k]=MAX(max_col[k],best[i][k]);
				}
			else best[i][k] = -INF;
			}

//printf("----------------------------------\n");
maxx=0;
for (i=1;i<N;i++)
	{
	for (j=0;j<N;j++)
		{
		if (best[i][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;
/*
int pas;
int inc_interv, sf_interv;
pas = H;
int nr_intervale;
if ((H-inaltime[N-1]) % U != 0)
	nr_intervale = ((H-inaltime[N-1]) / U )+1;
	else
	nr_intervale = (H-inaltime[N-1]) / U ;
	
a = (int*)malloc(nr_intervale*sizeof(int*));

int j;
for (i=0; i<nr_intervale; i++)
	{
	inc_interv = pas - U +1;
	sf_interv = pas;
	//printf ("inc_interv=%i\n",inc_interv);
	//printf ("sf_interv=%i\n",sf_interv);
	for (j=inc_interv;j<sf_interv;j++)
	
	quicksort(greutate,inaltime,inc_interv,sf_interv);
	printlist(inaltime,N);
	printlist(greutate,N);
	for (j=inc_interv;j<sf_interv;j++)
		if (inaltime[j%10]==j)
		printf("%i ", greutate[j]);
	printf("\n");
	a[i] = greutate[sf_interv%U];
	printf("a[%i]=%i\n",i,a[i]);
	int k=0;
	int s=0;
	while ((sf_interv -1 -k > inc_interv) && (k < i))
		{
		if (a[sf_interv-1-k] - a[k] > 0)
			s+=a[sf_interv-1-k] - a[k];
			else
				break;
		k++;
		}
	a[i]+=s;
	pas = pas - U;
	}
	
printlist(a,nr_intervale);


g= fopen("gutui.out","w");
fclose(f);
fclose(g);
 
return 0;
*/
}