Cod sursa(job #423214)

Utilizator vdobrotaDobrota Valentin Eugen vdobrota Data 23 martie 2010 17:00:00
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 1.04 kb
#include<stdio.h>

int q[100000],g[100000];
char o[100000];

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]);
      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(0,j-1);
      quicksort(j+1,n);
   }
}

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