Pagini recente » Cod sursa (job #2197421) | Cod sursa (job #2517937) | Cod sursa (job #729644) | Cod sursa (job #300022) | Cod sursa (job #1851963)
#include <cstdio>
# 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() {
FILE *fin, *fout;
fin=fopen("heavymetal.in", "r");
fout=fopen("heavymetal.out", "w");
int n;
fscanf(fin, "%d", &n);
for ( int i = 1; i <= n; i ++ )
fscanf(fin, "%d%d", &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 ) );
}
fprintf(fout, "%d\n", d[n]);
return 0;
}