Cod sursa(job #430591)

Utilizator Cristina_89Cristina Savin Cristina_89 Data 31 martie 2010 10:31:58
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.68 kb
#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;

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);
	}
}


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;
}  

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]);
	}
}

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);
}
    
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
		if (cap_inter[2*i]==-1) continue;
		
		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);
		
		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;
    
    quicksort(hh,gg,0,n-1);
    
	afla_intervale();
	sorteaza_intervale();	
	
	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;   
}