Pagini recente » Cod sursa (job #1446575) | Cod sursa (job #2201368) | Cod sursa (job #1031801) | Cod sursa (job #721071) | Cod sursa (job #551461)
Cod sursa(job #551461)
#include<stdio.h>
#include<algorithm>
#define Nmax 100010
using namespace std;
struct interval { int x,y ; } v[Nmax] ;
int i,n,best[Nmax],j;
int cmp ( interval a, interval b )
{
return a.y < b.y ;
}
int bsearch( int x )
{
int s = 0 , d = i , m , r = 0 ;
for( m = (s+d)>>1 ; s <= d ; m = (s+d)>>1 )
if( v[m].y <= x ) { r = m ; s = m + 1 ; }
else d = m - 1 ;
return r ;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for( i = 1 ; i <= n ; i++ )
scanf("%d %d",&v[i].x,&v[i].y);
sort( v+1 , v+n+1, cmp ) ;
for( i = 1 ; i <= n ; i++ )
{
best[i] = best[i-1];
j = bsearch(v[i].x);
if( best[i] < best[j] + v[i].y - v[i].x )
best[i] = best[j] + v[i].y - v[i].x ;
}
printf("%d",best[n]);
return 0;
}