Pagini recente » Cod sursa (job #2085484) | Cod sursa (job #175528) | Cod sursa (job #2004385) | Cod sursa (job #1523760) | Cod sursa (job #1874005)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
#define nmax 100010
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct element{int st,dr;} v[nmax];
int n,i,j;
int best[nmax];
bool cmp(element a,element b)
{
if(a.dr!=b.dr) return a.dr<b.dr;
return a.st<b.st;
}
int search(int x)
{
int left=0,right=n,mid;
while (left<=right)
{
mid=(left+right)/2;
if(v[mid].dr<=x) left=mid+1;
else right=mid-1;
}
return right;
}
int main()
{
fin>>n;
for(i=1;i<=n;++i)
{
fin>>v[i].st>>v[i].dr;
}
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;++i)
{
j=search(v[i].st);
best[i]=max(best[i-1],v[i].dr-v[i].st+best[j]);
}
fout<<best[n];
return 0;
}