Pagini recente » Istoria paginii blog/oji-oni-2005 | Cod sursa (job #2005640) | Profil TheGamer1023 | Cod sursa (job #232425) | Cod sursa (job #2686976)
#include <fstream>
#include<algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n,d[100005],st,dr,mij,sol;
struct timp
{
int a,b;
}v[100005];
bool cmp(timp x,timp y)
{
return x.b<y.b||(x.b==y.b&&x.a<y.a);
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].a>>v[i].b;
sort(v+1,v+n+1,cmp);
d[1]=v[1].b-v[1].a;
for(int i=2;i<=n;i++)
{
st=1;
dr=n;
while(st<=dr)
{
mij=(st+dr)/2;
if(v[i].a>=v[mij].b)
{
sol=mij;
st=mij+1;
}
else
dr=mij-1;
}
d[i]=max(d[i-1],d[sol]+v[i].b-v[i].a);
}
fout<<d[n];
return 0;
}