Cod sursa(job #423266)

Utilizator vdobrotaDobrota Valentin Eugen vdobrota Data 23 martie 2010 18:15:50
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 1.42 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,t;
   if( m < n)
   {
      k = (m+n)/2;
      swap(&g[m],&g[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)
         {
                t=g[i];
                g[i]=g[j];
                g[j]=t;
                t=q[i];
                q[i]=q[j];
                q[j]=t;
         }
      }      
      t=g[m];
      g[m]=g[j];
      g[j]=t;
      t=q[m];
      q[m]=q[j];
      q[j]=t;              
      quicksort(m,j-1);
      quicksort(j+1,n);
   }
}

int main()
{
	int n,h,u,i,start,max=0,val,stac[100000],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;
}