Pagini recente » Cod sursa (job #2785122) | Cod sursa (job #1318614) | Cod sursa (job #1960846) | Cod sursa (job #2093624) | Cod sursa (job #2358943)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int N=100005;
pair<int,int>v[N];
int n,best[N];
bool cmp(pair<int,int>a, pair<int,int>b)
{
if(a.second==b.second)
return(a.first<b.first);
return(a.second<b.second);
}
int binsc(int x)
{
int p=0;
for(int bit=16;bit>=0;bit--)
if(p+(1<<bit)<x && v[p+(1<<bit)].second<=v[x].first)
p=p+(1<<bit);
return p;
}
int main()
{
in>>n;
for(int i=1;i<=n;i++)
in>>v[i].first>>v[i].second;
sort(v+1,v+n+1,cmp);
int pred;
for(int i=1;i<=n;i++)
{
pred=binsc(i);
best[i]=max(best[i-1],v[i].second-v[i].first+best[pred]);
}
out<<best[n];
return 0;
}