Pagini recente » Cod sursa (job #2208533) | Cod sursa (job #1494936) | Cod sursa (job #1030774) | Cod sursa (job #1527216) | Cod sursa (job #2135960)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
const int nmax=100000;
struct data
{
int st,dr;
};
bool cmp(data a,data b)
{
if(a.dr!=b.dr)
return a.dr<b.dr;
return a.st<b.st;
}
int n;
data v[nmax+5];
int best[nmax+5];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i].st>>v[i].dr;
v[i].dr--;
}
sort(v+1,v+n+1,cmp);
best[1]=v[1].dr-v[1].st+1;
for(int i=2;i<=n;i++)
{
int r=0,pas=(1<<16);
while(pas)
{
if(r+pas<i && v[r+pas].dr<v[i].st)
r+=pas;
pas/=2;
}
best[i]=max(best[i-1],best[r]+v[i].dr-v[i].st+1);
}
cout<<best[n];
return 0;
}
/**
**/