Cod sursa(job #214939)

Utilizator Andrei200Andrei200 Andrei200 Data 16 octombrie 2008 22:41:02
Problema Heavy metal Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <stdio.h>
#include <stdlib.h>

int n,i,j,Best[100000],b[100000],a[100000],maxim,x,y,f[100000];
char ch[10];

int max(int a,int b)
{
    if (a>b)
    return a;
    else
    return b;
}

void q_sort(int numbers[], int left, int right)
{
   int pivot, l_hold, r_hold;
   l_hold = left;
   r_hold = right;
   if(left != right)
   {
   	int aux = numbers[left], randompoz = left + rand() % (left - right);
   	numbers[left] = numbers[randompoz];
   	numbers[randompoz] = aux;
   }
   pivot = numbers[left];
   while (left < right)
   {
      while ((numbers[right] >= pivot) && (left < right))
      right--;
      if (left != right)
      {
	numbers[left] = numbers[right];
	left++;
      }
      while ((numbers[left] <= pivot) && (left < right))
	left++;
      if (left != right)
      {
	  numbers[right] = numbers[left];
	  right--;
      }
   }
   numbers[left] = pivot;
   pivot = left;
   left = l_hold;
   right = r_hold;
   if (left < pivot)
      q_sort(numbers, left, pivot-1);
   if (right > pivot)
      q_sort(numbers, pivot+1, right);
}

int main()
{
    freopen("heavymetal.in","rt",stdin);
    //freopen("heavymetal.out","wt",stdout);
    scanf("%d", &n);
    for (i=1;i<=n+1;++i)
          {
               // scanf("%d %d", &a[i],&b[i]);
           gets(ch);
           x=y=j=0;
           while (ch[j]!=' ')
                  {
                        x=x*10+ch[j]-'0';
                        j++;
                        }
                        j++;
           while (ch[j])
           {
                y=y*10+ch[j]-'0';
                j++;
                }
            a[i]=x;
            b[i]=y;  
            //printf("%d %d\n", x,y);
            //f[a[i]]++;  
            //f[b[i]]++;
            //a[i]=x;
            //b[i]=y;
           maxim=max(maxim,b[i]);
        }
    //q_sort(a,1,n);
    //q_sort(b,1,n);        
    for (i=1;i<=maxim;++i)
          {    
             //   if (f[i]>=1)
           Best[i]=Best[i-1];   
           for (j=1;j<=maxim;++j)
           if (b[j]==i)   
        Best[i]=max(Best[i],Best[a[j]]+(b[j]-a[j]));  
}

freopen("heavymetal.out","wt",stdout);
printf("%d", Best[maxim]);
return 0;
}