Cod sursa(job #437640)

Utilizator Cristina_89Cristina Savin Cristina_89 Data 9 aprilie 2010 23:34:30
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 3.1 kb
//==Savin Cristina 322CA==
#include <stdio.h>
#include <stdlib.h>

#define MAXINT 2000000000

int *hh,*gg,*cap_inter;
int n,h,u,crt;
int minPoz,maxPoz;
int *sol;
int pozSol=0;

/*Quicksort */
void quicksort(int *prim,int *sec,int st, int dr)
{
	int i,j;
	int v,t;
	if ( dr>st )
	{
		v=prim[dr]; i=st-1; j=dr; /*indice=ultimul element */
		for ( ; ; )
		{
			while ( prim[++i]>v );
			while ( prim[--j]<v );
			if (i>=j) break;
			t=prim[i];prim[i]=prim[j];prim[j]=t;
			if (sec) {t=sec[i];sec[i]=sec[j];sec[j]=t;} 
		}
		t=prim[i];prim[i]=prim[dr];prim[dr]=t;
		if (sec) {t=sec[i];sec[i]=sec[dr];sec[dr]=t;}
		quicksort(prim,sec,st,i-1);
		quicksort(prim,sec,i+1,dr);
	}
}

/*Functie care afla intervalele*/
void afla_intervale()
{
	int i;
	minPoz=(h-hh[0])/u+1;
	for (i=0;i<n;i++)
	{ 
		if (cap_inter[2*((h-hh[i])/u+1)]==-1) cap_inter[2*((h-hh[i])/u+1)]=i; //pozitia din stanga a intervalului
		cap_inter[2*((h-hh[i])/u+1)+1]=i;  //pozitia din dreapta a intervalului	
	}
	maxPoz =(h-hh[n-1])/u+1;
}  

/*Functie care sorteaza fiecare interval dupa greutate*/
void sorteaza_intervale()
{
	int i;
	for (i=minPoz;i<= maxPoz;i++)
	{
		//daca nu e nici un element in interval
		if (cap_inter[2*i]==-1) continue;	
		quicksort(gg,hh,cap_inter[2*i],cap_inter[2*i+1]);
	}
}

/*Afla minimul intre i si lungimea intervalului i*/
int minim_lung(int i)
{
	if (i<(cap_inter[2*i+1]-cap_inter[2*i]+1)) return i;
	else return (cap_inter[2*i+1]-cap_inter[2*i]+1);
}
 
/*Afla minimul din vectorul solutie*/   
int afla_minim(int nr)
{
	int i,poz=0,min=MAXINT;

	for (i=0;i<nr;i++)
		if (sol[i]<min) {min=sol[i];poz=i;}
	return poz;		
}    
    
void construieste_solutia()
{
	int i,j,pozitieMinim;
	//din intervalul i tb sa alex maxim i numere
	for (i=minPoz;i<= maxPoz;i++)
	{		
		//daca nu e nimic in acel interval sari peste el
		if (cap_inter[2*i]==-1) continue;
		
		//completez vectorul de solutii pana ajung la i
		for (j=cap_inter[2*i];j<cap_inter[2*i]+minim_lung(i);j++)
		{
			sol[pozSol++]=gg[j];
			if (pozSol==i) break;
		}
				
		pozitieMinim=afla_minim(pozSol);
		//inlocuiesc minimul cu maximul din intervalul i
		for (j=j+1;j<cap_inter[2*i]+minim_lung(i);j++)
		{
			if (sol[pozitieMinim]<gg[j]) 
				{
				sol[pozitieMinim]=gg[j];
				pozitieMinim=afla_minim(pozSol);
				}
		}				
	}
	
}	
	
int main()
{
    int i,sum=0;
    FILE *fis=fopen("gutui.in","r");
    fscanf(fis,"%d%d%d",&n,&h,&u);

    hh=(int*)malloc(n*sizeof(int));
    gg=(int*)malloc(n*sizeof(int));
	sol=(int*)malloc(n*sizeof(int));
    cap_inter=(int*)malloc(2*(h/u+2)*sizeof(int));
    
    for(i=0;i<n;i++)
       {fscanf(fis,"%d%d",&hh[i],&gg[i]);}
    fclose(fis);
	
	for(i=0;i<2*(h/u+2);i++)
		cap_inter[i]=-1;
    //sortez dupa inaltime
    quicksort(hh,gg,0,n-1);
    //calculez intervale
	afla_intervale();
	//sortez fiecare interval dupa greutate
	sorteaza_intervale();	
	//construiesc solutia
	construieste_solutia();

	for(i=0;i<pozSol;i++)
		sum+=sol[i];
	
	FILE *fis1=fopen("gutui.out","w");
    fprintf(fis1,"%d\n",sum);
    fclose(fis1);
  
    return 0;   
}