Pagini recente » Cod sursa (job #51028) | Cod sursa (job #2849233) | Cod sursa (job #1348819) | Cod sursa (job #904969) | Cod sursa (job #1729663)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int MAX = 100005;
struct Interval{
int x, y;
};
Interval a[MAX];
int D[MAX];
int N;
void Read();
void Solve();
int CautareBinara( int x );
bool Comp( const Interval& a, const Interval& b )
{
if ( a.y < b.y || ( a.y == b.y && a.x < b.x ) )
return true;
return false;
}
int main()
{
Read();
Solve();
fout << D[N] << '\n';
fin.close();
fout.close();
return 0;
}
void Read()
{
int i;
fin >> N;
for ( i = 1; i <= N; i++ )
{
fin >> a[i].x >> a[i].y;
}
sort( a + 1, a + 1 + N, Comp );
}
void Solve()
{
int i, j;
D[1] = a[1].y - a[1].x;
for ( i = 2; i <= N; i++ )
D[i] = max( D[CautareBinara(i)] + ( a[i].y - a[i].x ), D[i - 1] );
}
int CautareBinara( int x )
{
int st = 1, dr = x - 1, mid;
int p = 0;
while ( st <= dr )
{
mid = ( st + dr ) / 2;
if ( a[mid].y <= a[x].x )
{
p = mid;
st = mid + 1;
}
else
dr = mid - 1;
}
return p;
}