Cod sursa(job #141944)

Utilizator alexeiIacob Radu alexei Data 23 februarie 2008 21:48:25
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<stdio.h>
#define nmax 100002
#define max(a,b) ( (a)>(b)? (a):(b) )

unsigned long long frig1[nmax],frig2[nmax],sol[nmax];

int schimb(int st,int dr)
{
long long x=frig2[st];
long long y=frig1[st];
 
 while( st < dr ){ 
   while( st < dr && frig2[dr] >= x )--dr;
   
    frig2[st]=frig2[dr];
    frig1[st]=frig1[dr];
    
   while( st < dr && frig2[st] <= x )++st;
      
    frig2[dr]=frig2[st];
    frig1[dr]=frig1[st];
            
    }
frig2[st]=x;        
frig1[st]=y;        
        
        return st;}
        
 void slowsort(int st,int dr)
 {               
 if(st<dr)
  {
 int m=schimb(st,dr);
  slowsort(st,m);
  slowsort(m+1,dr);        
  }     
        }

int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	
	int n;
    unsigned long long i,j,tmax=0,tmin=0;
	
	scanf("%d",&n);
	
	for(i=1; i<=n; ++i){
		scanf("%u%u",&frig1[i],&frig2[i]);
			if(frig2[i]>tmax)
				tmax=frig2[i];
			if(	!tmin || frig1[i] < tmin )
			    tmin=frig1[i];
			
	}
	 
	slowsort(1,n);

	
	for(i=tmin,j=1; i<=tmax; ++i){
		
		sol[i]=sol[i-1];
		
		for(j; frig2[j] == i; ++j){	
			sol[i] = max ( sol[i] , sol[ frig1[j] ] + (frig2[j]-frig1[j]) );
	    }
        
    }
	
	printf("%u\n",sol[tmax]);
	
	
	
	return 0;
}