Pagini recente » Cod sursa (job #188863) | Cod sursa (job #2417740) | Cod sursa (job #161709) | Cod sursa (job #2870949) | Cod sursa (job #669006)
Cod sursa(job #669006)
#include <fstream>
#include <algorithm>
#define NMAX 100001
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
long long n,i,p=0;
struct inter {long long s,f;};
bool comp(inter a,inter b) {return a.f<b.f;}
inter a[NMAX];
long long ANS[NMAX];
long long caut(long long v) {
long long p=1,u=n,m,s=0;
while (p<=u) {
m=p+(u-p)/2;
if (a[m].f<=v) p=m+1,s=ANS[m];
else u=m-1;
}
return s;
}
int main () {
f >> n;
for (i=1;i<=n;i++) f >> a[i].s >> a[i].f;
sort(a+1,a+n+1,comp);
ANS[1]=a[1].f-a[1].s;
for (i=2;i<=n;i++)
ANS[i]=max(ANS[i-1],caut(a[i].s)+a[i].f-a[i].s);
g << ANS[n] << '\n';
f.close();g.close();
return 0;
}