Pagini recente » Cod sursa (job #2802169) | Profil IoncioaiaCalin | Cod sursa (job #1560414) | Cod sursa (job #2369912) | Cod sursa (job #138768)
Cod sursa(job #138768)
#include <vector>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
int N;
vector<pair<int, int> > P;
vector<int> Q;
map<int, int> O;
int DP[200001];
int main()
{
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
int i, j;
scanf("%d", &N);
for (i = 0; i < N; ++i)
{
int a, b;
scanf("%d %d", &a, &b);
if (!O[a]) Q.push_back(a), O[a] = 1;
if (!O[b-1]) Q.push_back(b-1), O[b-1] = 1;
P.push_back(make_pair(b-1, a));
};
sort(Q.begin(), Q.end());
for (i = 0; i < Q.size(); ++i) O[Q[i]] = i+1;
for (i = 0; i < P.size(); ++i) P[i].first = O[P[i].first],
P[i].second = O[P[i].second];
sort(P.begin(), P.end());
int best = 0;
int k = 0;
for (i = 1; i <= Q[Q.size()-1]; ++i)
{
DP[i] = DP[i-1];
for (; k < P.size() && P[k].first == i; ++k)
if (DP[P[k].second-1] + Q[P[k].first-1] - Q[P[k].second-1] + 1 > DP[i])
DP[i] = DP[P[k].second-1] + Q[P[k].first-1] - Q[P[k].second-1] + 1;
if (DP[i] > best) best = DP[i];
};
printf("%d", best);
return 0;
};