Pagini recente » Cod sursa (job #2297512) | Cod sursa (job #615311) | Cod sursa (job #3225166) | Cod sursa (job #1067648) | Cod sursa (job #1294996)
#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;
d=poz;
while(s<=d)
{
m=(s+d)/2;
if(interval[m].second<=interval[poz].first)
s=m+1;
else d=m-1;
}
m=(s+d)/2;
if(m && interval[m].second>interval[poz].first) m--;
return m;
}
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;
}