Pagini recente » Cod sursa (job #2030211) | Cod sursa (job #761470) | Cod sursa (job #1239064) | Cod sursa (job #1997196) | Cod sursa (job #1722891)
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct coord
{
int st,dr;
};
inline bool cmp(const coord A,const coord B)
{
if(A.dr==B.dr) return A.st<B.st;
return A.dr<B.dr;
}
coord v[Nmax];
int n,dp[Nmax];
void Citire()
{
int i;
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i].st>>v[i].dr;
fin.close();
sort(v+1,v+n+1,cmp);
}
inline int Cautbin(int p1,int p2,int val)
{
int st=p1,dr=p2,mij,sol;
sol=0;
while(st<=dr)
{
mij=(st+dr)/2;
if(v[mij].dr<=val) sol=mij,st=mij+1;
else dr=mij-1;
}
return sol;
}
void Rezolvare()
{
int i,poz;
for(i=1;i<=n;i++)
{
poz=Cautbin(1,i-1,v[i].st);
dp[i]=max(dp[i-1],v[i].dr-v[i].st+dp[poz]);
}
fout<<dp[n]<<"\n";
fout.close();
}
int main()
{
Citire();
Rezolvare();
return 0;
}