Cod sursa(job #441296)

Utilizator arpawizovidiu b arpawiz Data 12 aprilie 2010 21:00:13
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.6 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
long max2(long a, long b)
{
	return (a>b)?a:b;
}
 
long max3(long a, long b, long c)
{
	return max2(a, max2(b,c));
}
 
int main()
{
	long n, ho, u, max=0, i, j;
 
	FILE *f=fopen("input.in", "r");
	FILE *g=fopen("output.out", "w");
	fscanf(f, "%ld %ld %ld", &n, &ho, &u);
 
	long *h=(long *) malloc((n+1)*sizeof(long));
	long *w=(long *) malloc((n+1)*sizeof(long));
	long **m=(long **) malloc((n+1)*sizeof(long*));
	for(i=0; i<=n; i++)
	m[i]=(long *) malloc((ho+1)*sizeof(long));
	for(i=1; i<=n; i++)
	fscanf(f,"%ld %ld", &h[i], &w[i]);
    //m[i][j] is the max weight one can obtaing using fruits from 1 to i and admitting a height limit of j
	for(i=0; i<=ho; i++)
	m[0][i]=0;
	for(i=0; i<=n; i++)
	m[i][0]=0;
 
for(i=1; i<=n; i++)
{
   for(j=0; j<=ho; j++)
   {
      //check if iterating height is greater than current items height
      //plus rising height.  You can now add the current item to any
      //previous items and you've increased this ones height by u
      if(j >= h[i]+u)
      {
         m[i][j] = max2(m[i-1][j], w[i]+m[i-1][j-(h[i]+u)]);
      }
      //now check if iterating height is greater than current items height
      //if it is you can take this item but it must be your first pick
      else if(j >= h[i])
      {
         m[i][j] = max2(m[i-1][j], w[i]);
      }
      else
      {
         m[i][j] = m[i-1][j];
      }
   }
}
	max=m[n][ho];
	printf("%ld\n", max);
	fprintf(g, "%ld", max);
 
	for(i=0; i<=n; i++)				
	free(m[i]);
	free(m);	
	fclose(f);
	fclose(g);
	return 0;
}