Pagini recente » Cod sursa (job #776595) | Cod sursa (job #266805) | Cod sursa (job #1997819) | Cod sursa (job #1992910) | Cod sursa (job #2537508)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
struct spectacol
{
int a , b;
}v[100005];
int d[100005];
bool xort(spectacol x , spectacol y)
{
if(x.b < y.b)
return true;
if(x.b == y.b && x.a <= y.a)
return true;
return false;
}
int main()
{
int n , maxim = 0 , i , t , l , pas;
cin >> n;
for(i = 1; i <= n; i++)
{
cin >> v[i].a >> v[i].b;
}
sort(v + 1, v + n + 1, xort);
for(t = 1; t <= n; t++)
{
l = 0;
pas = 131072;
while(pas)
{
if(l + pas <= n)
if(v[l + pas].b <= v[t].a)
l += pas;
pas /= 2;
}
d[t] = max( d[l] + v[t].b - v[t].a , maxim);
maxim = max(d[t] , maxim);
}
cout << d[n];
return 0;
}