Pagini recente » Cod sursa (job #2961630) | Cod sursa (job #1764102) | Cod sursa (job #967982) | Cod sursa (job #1274182) | Cod sursa (job #1692223)
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
struct COSTIN {
int st,dr;
}v[100001];
int d[100001];
bool cmp( COSTIN a, COSTIN b ) {
if( a.dr == b.dr )
return a.st < b.st;
return a.dr < b.dr;
}
int maxi(int a,int b) {
if( a < b )
a = b;
return a;
}
int bs( int x ) {
int st,dr,mid,last = 1;
st = 1;
dr = x;
while( st <= dr ) {
mid = ( st + dr ) / 2;
if( v[mid].dr <= v[x].st ) {
st = mid + 1;
last = mid;
}
else
dr = mid - 1;
}
return last;
}
int main() {
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int i,j,m = 0;
scanf("%d",&n);
for( i = 1; i <= n; i ++ ) {
scanf("%d%d",&v[i].st,&v[i].dr);
}
sort( v + 1, v + n + 1, cmp );
for( i = 1; i <= n; i ++ ) {
j = bs(i);
d[i] = maxi( d[i-1],d[j]+(v[i].dr-v[i].st) );
if( m < d[i] )
m = d[i];
}
printf("%d",m);
return 0;
}