Pagini recente » Cod sursa (job #704823) | Cod sursa (job #56597) | Cod sursa (job #1239758) | Cod sursa (job #1922902) | Cod sursa (job #2046858)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#define NMAX 100005
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct sp
{
int x,y;
}v[NMAX];
int x[NMAX],nr,n,rez;
inline int comp(sp a, sp b)
{
if(a.y<b.y) return 1;
if(a.y==b.y) return a.x<b.x;
return 0;
}
inline void citire()
{
fin>>n;
for (int i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
}
inline int caut(int x)
{
int l=1,r=n,mid=(l+r)/2;
while(l<=r)
{
mid=(l+r)/2;
if(v[mid].y<=x) l=mid+1;
else r=mid-1;
}
return r;
}
inline void solve()
{
int i,j;
for (i=1;i<=n;i++)
{
int aux=caut(v[i].x);
x[i]=max(x[i-1],x[aux]+v[i].y-v[i].x);
rez=max(rez,x[i]);
}
}
int main()
{
citire();
sort(v+1,v+n+1,comp);
solve();
fout<<rez;
fin.close();
fout.close();
return 0;
}