Cod sursa(job #423296)

Utilizator vdobrotaDobrota Valentin Eugen vdobrota Data 23 martie 2010 18:50:04
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.59 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) 
	//printf("%d %d\n",g[i],q[i]);
	for(i=n;i>0;--i) {
		start=1+(h-q[i])/u;
		//printf("q=%d pornim cu %d,",q[i],start);
		k=1;
		stac[k]=start;		
		while(prec[start] && start>0)
		{		
			start=prec[start];		
			stac[++k]=start;
		}		
		//printf("ajungem la %d\n",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("am adaugat greutatea %d pe pozitia %d\n",g[i],start);
		//for(j=1;j<=20;j++)
		//	printf("%d ",prec[j]);
		//printf("\n");
	}		
	printf("%d\n",max);
return 0;
}