Pagini recente » Cod sursa (job #2701814) | Cod sursa (job #1109966) | Cod sursa (job #2193196) | Cod sursa (job #1570348) | Cod sursa (job #770740)
Cod sursa(job #770740)
#include <iostream>
#include <fstream>
#include <algorithm>
#define st(x) (V[x].first)
#define dr(x) (V[x].second)
using namespace std;
ifstream in ("heavymetal.in");
ofstream out ("heavymetal.out");
const int MAXN = 100010;
pair < int, int > V[MAXN];
int Best[MAXN];
bool comp (pair < int, int > a, pair < int, int > b)
{
return a.second < b.second;
}
int main ()
{
int N, i, j, now = 1, end;
in >> N;
for (i = 1; i <= N; ++i)
in >> st(i) >> dr(i);
sort (V + 1, V + N + 1, comp);
end = dr(N);
for (i = 1; i <= end; ++i){
Best[i] = Best[i - 1];
for ( ; V[now].second == i; ++now)
if (Best[i] < Best[ st(now) ] + i - st(now))
Best[i] = Best[ st(now) ] + i - st(now);
}
out << Best[end];
return 0;
}