Pagini recente » Cod sursa (job #1760624) | Cod sursa (job #2118800)
#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 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 ++ )
{
if ( p[i-1].second != v[i].first )
{
p[i].first = i;
p[i].second = v[i].first;
}
else
{
p[i].first = p[i-1].first;
p[i].second = p[i-1].second;
}
d[i] = max ( (d[p[i].first-1] + lungime (i) ), d[i-1] );
}
fout << d[n];
return 0;
}