Cod sursa(job #423297)

Utilizator vdobrotaDobrota Valentin Eugen vdobrota Data 23 martie 2010 18:52:21
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.33 kb
#include<stdio.h>

int q[100001],g[100001],prec[100001];
char o[100001];

void swap(int *x,int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}

void quicksort(int m,int n)
{
   int key,i,j,k;
   if( m < n)
   {
      k = (m+n)/2;
      swap(&g[m],&g[k]);
      swap(&q[m],&q[k]);
      key = g[m];
      i = m+1;
      j = n;
      while(i <= j)
      {
         while((i <= n) && (g[i] <= key))
                i++;
         while((j >= m) && (g[j] > key))
                j--;
         if( i < j)
		 {   
		 	swap(&g[i],&g[j]);	         
	        swap(&q[i],&q[j]);
	     }
      }      
      swap(&g[m],&g[j]);
      swap(&q[m],&q[j]);                        
      quicksort(m,j-1);
      quicksort(j+1,n);
   }
}

int main()
{
	int n,h,u,i,start,max=0,val,stac[100001],j,k;
	freopen("gutui.in","r",stdin);
	freopen("gutui.out","w",stdout);
	scanf("%d %d %d",&n,&h,&u);
	for(i=1;i<=n;i++)
		scanf("%d %d",&(q[i]),&(g[i]));
	quicksort(1,n);
	for(i=n;i>0;--i) {
		start=1+(h-q[i])/u;
		k=1;
		stac[k]=start;		
		while(prec[start] && start>0)
		{		
			start=prec[start];		
			stac[++k]=start;
		}		
		if(start>0)		
		{
			if(start!=1)
				if(prec[start-1])
					val=prec[start-1];
				else
					val=start-1;
			else
				val=-1;
			for(j=1;j<=k;j++)
				prec[stac[j]]=val;
			max+=g[i];
			o[start]=1;
		}
	}		
	printf("%d\n",max);
return 0;
}