Pagini recente » Cod sursa (job #2103889) | Cod sursa (job #1287730) | Cod sursa (job #1514140) | Cod sursa (job #2602471) | Cod sursa (job #2046124)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
#define lim 100010
int n,dp[lim],rez;
struct pct{int st,dr;} ini[lim];
bool cmp (pct A, pct B)
{
if (A.dr < B.dr) return 1;
if (A.dr == B.dr) return A.st<B.st;
return 0;
}
int caut_bin(int x)
{
int l=1,r=n,mid=(l+r)/2;
while (l<=r)
{
mid = (l+r)/2;
if (ini[mid].dr <= x) l = mid+1;
else r = mid-1;
}
return r;
}
int main()
{
fin>>n;
for (int i=1; i<=n; i++) fin>>ini[i].st>>ini[i].dr;
sort (ini+1, ini+n+1, cmp);
for (int i=1; i<=n; i++)
{
int aux = caut_bin(ini[i].st);
dp[i] = max (dp[i-1], dp[aux]+ini[i].dr-ini[i].st);
rez = max(rez, dp[i]);
}
fout<<rez;
fin.close();
fout.close();
return 0;
}