Pagini recente » Cod sursa (job #1363420) | Cod sursa (job #2534453) | Cod sursa (job #1136286) | Cod sursa (job #115283) | Cod sursa (job #595139)
Cod sursa(job #595139)
# include <fstream>
# include <algorithm>
using namespace std;
struct T {int i, j;} a[100001];
int i, n, best[100001];
template <typename name>
inline name bs (name find, name left)
{
name i, cnt = 1 << 18;
for (i = 1; cnt > 0; cnt >>= 1)
if (i + cnt <= left)
if (a[i + cnt].j <= find) i += cnt;
return i;
}
inline bool cmp (T a, T b)
{
return a.j < b.j;
}
template <class name>
inline name MAX (name a, name b)
{
return a > b ? a : b;
}
int main ()
{
ifstream f ("heavymetal.in");
ofstream g ("heavymetal.out");
f >> n;
for (i = 1; i <= n; ++i)
f >> a[i].i >> a[i].j;
sort (a + 1, a + n + 1, cmp);
best[1] = a[1].j - a[1].i;
for (i = 2; i <= n; ++i)
{
best[i] = MAX (best[i - 1], best[bs (a[i].i, i - 1)] + (a[i].j - a[i].i));
}
g << best[n] << '\n';
g.close ();
return 0;
}