Pagini recente » Cod sursa (job #1995060) | Cod sursa (job #369933) | Cod sursa (job #710028) | Cod sursa (job #2733961) | Cod sursa (job #2833727)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMAX = 100000;
struct Inter
{
int b, e;
};
Inter v[NMAX + 5];
int dp[NMAX + 5], w[NMAX + 5];
bool cmp(const Inter& a, const Inter& b)
{
if (a.e == b.e)
{
return a.b < b.b;
}
return a.e < b.e;
}
int bs(int n, int x)
{
int r = 0, pas = 1 << 16;
while (pas)
{
if (r + pas <= n && w[r + pas] <= x)
{
r += pas;
}
pas >>= 1;
}
return r;
}
int main()
{
int n;
fin >> n;
for (int i = 1; i <= n; ++i)
{
fin >> v[i].b >> v[i].e;
}
sort(v + 1, v + n + 1, cmp);
int i, j;
for (i = 1, j = 1; j <= n; ++i)
{
w[i] = v[j].e;
dp[i] = dp[i - 1];
while (j <= n && w[i] == v[j].e)
{
int b = bs(i, v[j].b);
dp[i] = max(dp[i], dp[b] + v[j].e - v[j].b);
++j;
}
}
fout << dp[i - 1];
return 0;
}