Cod sursa(job #435049)

Utilizator veraconstVeronica Constantinoaia veraconst Data 6 aprilie 2010 20:36:39
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.52 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct gut
{
	long int inaltime;
	long int greutate;
} gutui;

int compare (const void * a, const void * b)
{
    return ( *(int*)b - *(int*)a );
}
void inalta (gutui *a, long int pozi,long int pozf,long int c)
{
	long int i;
	for (i=pozi;i<pozf;i++)
		a[i].inaltime=a[i].inaltime+c;
	
}
void swap(gutui *x,gutui *y)
{
   gutui aux;
   aux = *x;
   *x = *y;
   *y = aux;
}

void sterge (gutui *a,long int *n,long int h)
{
	long int i=0,j;
	while (i<*n)
	{
		if ((a[i].greutate==0)||(a[i].inaltime>h))
		{
			for(j=i; j<*n-1; j++)
				a[j]=a[j+1];    
			
			*n=*n-1;
		}
		else i++;
			
	}
		
}
long int suma (gutui *a,long int pf,long int h)
{
	long int i;
	long int s=0;
	for (i=0;i<pf;i++)
		if (a[i].inaltime<=h)
			s=s+a[i].greutate;
return s;
}

/*long int greutate_maxima (gutuie *a,long int pi, long int pf,long int h,long int u)
{
	long int g=0;
	long int i=pi+1;
	while (i<pf)
		if ((a[i].inaltime<=h)&&(suma(a,pi+1,i)<a[i].greutate)&& (a[i].inaltime+u*(i-pf)>h))
			pozu=i;
	return g;
}*/
/*int neculese (gutui *a,long int n,long int h)
{
	long int i,nr=0;
	for (i=0;i<n;i++)
		if ((a[i].greutate!=0)&&(a[i].inaltime<=h))
			nr++;
	if (nr!=0) return 1;
	return 0;
}*/
int conditie(gutui *a,long int i,long int u,long int h)
{
	if ((a[i].inaltime<=h)&&(suma(a,i,h)<=a[i].greutate) && (a[i].inaltime+u*i>h))
		return 1;
return 0;	
}
int main()
{
	FILE *f=fopen ("gutui.in","r");
	FILE *g=fopen ("gutui.out","w");
	
	gutui *a;
	long int n,h,u,i,poz;
	int gasit;
	fscanf(f,"%ld %ld %ld",&n,&h,&u);
	a=(gutui*)malloc(n*sizeof(gutui));
	for (i=0;i<n;i++)
		fscanf(f,"%ld %ld",&a[i].inaltime,&a[i].greutate);
	qsort(a,n,sizeof(gutui),compare);
	int sortat=1;
	while (sortat)
	{
		sortat=0;
		for (i=0;i<n-1;i++)
			if ((a[i].inaltime==a[i+1].inaltime)&&(a[i].greutate<a[i+1].greutate))
			{	
				swap(&a[i],&a[i+1]);
				sortat=1;
			}
	}
	//for (i=0;i<n;i++)
	//	printf("%ld %ld\n",a[i].inaltime,a[i].greutate);
	//gasit=0;
	//pozi=0;
	sterge (a,&n,h);
	long int gmax=0;
	//long int pas=0;
	while (n!=0)
	{ 	
		i=0;	
		gasit=0;
		poz=0;
		while ((!gasit)&&(i<n-1))
		{
			if ((conditie (a,i,h,u))&&(!(conditie(a,i+1,h,u))))
			{
				poz=i;	
				gasit=1;	
			}
			
			i++;
		}
		if (conditie (a,n-1,h,u))
			poz=n-1;
		//printf("%ld\n",poz);
		gmax=gmax+a[poz].greutate;
		a[poz].greutate=0;
		inalta(a,0,n,u);
		sterge (a,&n,h);
		//printf("%ld\n",inaltimi(a,n,h));
		//for (i=0;i<n;i++)
		//printf("%ld %ld\n",a[i].inaltime,a[i].greutate);
			
	}
	fprintf (g,"%ld\n",gmax);
	free(a);
	fclose(f);
	fclose(g);

	return 0;
}