Pagini recente » Cod sursa (job #1568334) | Cod sursa (job #86513) | Cod sursa (job #803014) | Cod sursa (job #1297681) | Cod sursa (job #1723319)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int nmax = 100005;
int n,dp[nmax];
struct manelica
{
int st,dr;
};
manelica F[nmax];
inline bool CMP(const manelica A, const manelica B)
{
if(A.dr == B.dr) return A.st < B.st;
return A.dr < B.dr;
}
inline int Bsearch(int p)
{
int st, dr, m , x, sol = 0;
st = 1, dr = p-1, x = F[p].st;
while(st <= dr)
{
m = (st + dr) >> 1;
if(F[m].dr <= x)
{
sol = m;
st = m+1;
}
else dr = m-1;
}
return sol;
}
int main()
{
int i,p;
fin >> n;
for(i = 1; i <= n; i++)
fin >> F[i].st >> F[i].dr;
sort(F+1,F+n+1,CMP);
for(i = 1;i <= n; i++)
{
dp[i] = dp[i-1];
p = Bsearch(i);
dp[i] = max(dp[i],dp[p] + (F[i].dr - F[i].st));
}
fout << dp[n] << "\n";
fout.close();
return 0;
}