Pagini recente » Cod sursa (job #2229606) | just4fun | Cod sursa (job #2661081) | Cod sursa (job #41923) | Cod sursa (job #2383240)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int N=100000+2;
struct spectacol
{
int start;
int fin;
};
spectacol v[N];
int d[N];
int n;
void read()
{
in>>n;
for(int i=1;i<=n;++i)
{
in>>v[i].start>>v[i].fin;
}
}
bool cmp(spectacol a, spectacol b)
{
if(a.fin != b.fin)
{
return (a.fin<b.fin);
}
return (a.start<b.start);
}
int bSearch(int x)
{
int p=0;
for(int bit=16;bit>=0;bit--)
if(p+(1<<bit)<x && v[p+(1<<bit)].fin<=x)
p=p+(1<<bit);
return p;
}
int main()
{
read();
sort(v+1,v+n+1,cmp);
d[1]=v[1].fin-v[1].start;
for(int i=2;i<=n;++i)
{
d[i]=max(d[i-1],d[bSearch(v[i].start)]+v[i].fin-v[i].start);
}
out<<d[n];
return 0;
}