Pagini recente » Cod sursa (job #2562075) | Cod sursa (job #2521435) | Cod sursa (job #3143435) | Cod sursa (job #1236230) | Cod sursa (job #2383199)
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int N=100000+2;
vector <pair<int,int>> v;
int d[N];
int n;
void read()
{
in>>n;
int x,y;
for(int i=1;i<=n;++i)
{
in>>x>>y;
v.push_back(make_pair(x,y));
}
}
bool cmp(pair <int,int> a, pair<int,int> b)
{
if(a.second != b.second)
{
return (a.second<b.second);
}
return (a.first<b.first);
}
int bSearch(int x)
{
int pas=1<<17;
int ans=0;
while(pas)
{
if(ans+pas<n && v[ans+pas].second<=x)
{
ans+=pas;
}
pas>>=2;
}
return ans;
}
int main()
{
read();
sort(v.begin(),v.end(),cmp);
d[1]=v[0].second-v[0].first;
for(int i=2;i<=n;++i)
{
d[i]=max(d[i-1],d[bSearch(v[i-1].first)+1]+v[i-1].second-v[i-1].first);
}
out<<d[n];
return 0;
}