Pagini recente » Cod sursa (job #719113) | Cod sursa (job #1893215) | Cod sursa (job #2535000) | Cod sursa (job #230762) | Cod sursa (job #2118804)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <fstream>
using namespace std;
const int N = 100001;
pair <int, int> v[N], p[N];
long long d[N] ;
bool comp ( pair <int,int> a, pair <int, int> b)
{
if ( a.second < b.second)
return 1;
else
{
if ( a.second == b.second && a.first < b.first )
return 1;
else
return 0;
}
}
inline int lungime ( int a )
{
return v[a].second - v[a].first;
}
int caut_bin ( int a , int n)
{
int pas = 1 << 17, r = 1;
while ( pas != 0 )
{
if ( r + pas <= n && v[r + pas].second <= a )
r += pas;
pas = pas >> 1;
}
return r;
}
int main()
{
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
int n, j, m = 0;
fin >> n;
for ( int i = 1 ; i <= n ; i ++ )
fin >> v[i].first >> v[i].second;
sort ( v + 1 , v + 1 + n, comp );
for ( int i = 1 ; i <= n ; i ++ )
{
d[i] = max ( (d[caut_bin( v[i].first, n )] + lungime (i) ), d[i-1] );
}
fout << d[n];
return 0;
}