Pagini recente » Cod sursa (job #1671788) | Cod sursa (job #3004681) | Cod sursa (job #630388) | Cod sursa (job #2755086) | Cod sursa (job #2639346)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <cstring>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int DIM = 100005;
long long DP[DIM],n,sol,Max[DIM];
struct Point
{
int x,y;
}P[DIM];
void Read()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>P[i].x>>P[i].y;
}
bool Compare(Point a, Point b)
{
return a.y<b.y;
}
int Search(int value)
{
int st=1,dr=n,ans=0;
while(st<=dr)
{
int mij=(st+dr)/2;
if(P[mij].y<=value)
{
ans=max(ans,mij);
st=mij+1;
}
else
dr=mij-1;
}
return ans;
}
void Solve()
{
for(int i=1;i<=n;i++)
{
DP[i]=P[i].y-P[i].x;
Max[i]=max(Max[i-1],DP[i]);
}
for(int i=2;i<=n;i++)
{
int Find=P[i].x;
sol=Search(Find);
DP[i]+=Max[sol];
Max[i]=max(Max[i-1],DP[i]);
}
}
void Print()
{
fout<<Max[n]<<'\n';
}
int main()
{
Read();
sort(P+1,P+1+n,Compare);
Solve();
Print();
}