Pagini recente » Cod sursa (job #2019373) | Cod sursa (job #2633345) | Cod sursa (job #2224896) | Cod sursa (job #753343) | Cod sursa (job #2055680)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector <pair<int,int> > f;
int t[100005];
int n,a,b;
bool cmp(pair<int,int> la, pair<int,int> lb)
{
return (la.first<lb.first) || (la.first==lb.first && la.second<lb.second);
}
int caut(int micv)
{
int st=0,dr=n,m;
while(st<dr)
{
m=(st+dr+1)/2;
if(f[m].second<=micv)
st=m;
else
dr=m-1;
}
return dr;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
f.push_back({0,0});
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("\n%d %d", &a,&b);
f.push_back({a,b});
}
sort(f.begin()+1,f.end(),cmp);
t[1]=f[1].second-f[1].first;
for(int i=2;i<=n;i++)
t[i]=max(t[i-1],t[caut(f[i].first)]+f[i].second-f[i].first);
cout<<t[n];
return 0;
}