Pagini recente » Cod sursa (job #684439) | Cod sursa (job #256781) | Cod sursa (job #1647202) | Cod sursa (job #2023910) | Cod sursa (job #2647723)
#define MAX_N 100000
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct DINT64
{
int64_t x, y;
bool operator< (const DINT64& other) const
{
if (x != other.x)
{
return x < other.x;
}
return y < other.y;
}
};
int n;
int64_t Dp[MAX_N + 2];
DINT64 I[MAX_N + 1];
int Bs(int lb);
int main()
{
fin >> n;
for (int i = 1; i <= n; ++i)
{
fin >> I[i].x >> I[i].y;
}
sort(I + 1, I + n + 1);
int64_t res = 0;
for (int i = n; i >= 1; --i)
{
int index = Bs(i);
Dp[i] = max(Dp[i + 1], I[i].y - I[i].x + Dp[index]);
if (res < Dp[i])
{
res = Dp[i];
}
}
fout << res;
fin.close();
fout.close();
return 0;
}
int Bs(int index)
{
int l = 1, r = n, mid, res = 0;
while (l <= r)
{
mid = (l + r) / 2;
if (I[mid].x < I[index].y)
{
l = mid + 1;
}
else
{
res = mid;
r = mid - 1;
}
}
return res;
}