Pagini recente » Cod sursa (job #100704) | Cod sursa (job #1117241) | Cod sursa (job #2653959) | Cod sursa (job #67932) | Cod sursa (job #2505594)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int Nmax = 1e5+2;
int n, k;
struct Interval
{
int a, b;
bool operator < (const Interval &e) const
{
return b < e.b;
}
}t[Nmax], dp[Nmax];
int Caut_bin(int x)
{
int st, dr, mij, pos;
st = 1; dr = k; pos = k;
while (st <= dr)
{
mij = (st + dr) / 2;
if (dp[mij].a <= x)
{
pos = mij;
st = mij + 1;
}
else dr = mij - 1;
}
return pos;
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> t[i].a >> t[i].b;
sort(t + 1, t + n + 1);
int x, y, p;
for (int i = 1; i <= n; i++)
{
x = t[i].a;
y = t[i].b;
p = Caut_bin(x);
if (dp[k].a == y)
dp[k].b = max(dp[k].b, dp[p].b + y - x);
else
{
k ++;
dp[k].a = y;
dp[k].b = max(dp[k - 1].b, dp[p].b + y - x);
}
}
fout << dp[k].b << "\n";
fin.close();
fout.close();
return 0;
}