Pagini recente » Cod sursa (job #2316022) | Cod sursa (job #733178) | Cod sursa (job #822298) | Cod sursa (job #2159952) | Cod sursa (job #1851950)
# include <iostream>
# include <fstream>
# include <algorithm>
using namespace std;
const int MAX_N = 100000;
struct interval{
int b, e;
bool operator<( const interval t ) const { return e < t.e; }
} v[1 + MAX_N + 1];
int d[1 + MAX_N];
int cbin( int t, int n ) {
int i = 0;
for ( int pas = ( 1 << 20 ); pas > 0; pas >>= 1 )
if ( i + pas <= n && v[i + pas].e <= t )
i += pas;
return i;
}
int main() {
ifstream fin( "heavymetal.in" );
ofstream fout( "heavymetal.out" );
int n;
fin >> n;
for ( int i = 1; i <= n; i ++ )
fin >> v[i].b >> v[i].e;
sort( v + 1, v + n + 1 );
for ( int i = 1; i <= n; i ++ ) {
int p = cbin( v[i].b, n );
d[i] = max( d[i - 1], d[p] + ( v[i].e - v[i].b ) );
}
fout << d[n];
fin.close();
fout.close();
return 0;
}