Pagini recente » Cod sursa (job #783983) | Cod sursa (job #2901285) | Cod sursa (job #1289754) | Cod sursa (job #1104288) | Cod sursa (job #1295667)
#include <iostream>
#include<fstream>
#include<algorithm>
#define Nmax 1000001
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n,DP[Nmax];
pair <int,int> interval[Nmax];
int k;
void read()
{
fin>>n;
int i;
for(i=1;i<=n;i++)
{
int x,y;
fin>>x>>y;
interval[++k]=make_pair(x,y);
}
}
int Search(int poz)
{
int s=1,d,m,sol=0;
d=poz-1;
while(s<=d)
{
m=(s+d)/2;
if(interval[m].second<=interval[poz].first)
{
s=m+1;sol=m;}
else d=m-1;
}
return sol;
}
int main()
{
read();
sort(interval+1,interval+n+1);
int i;
for(i=1;i<=n;i++)
DP[i]=max(DP[i-1], DP[Search(i)]+interval[i].second-interval[i].first);
fout<<DP[n];
return 0;
}