Pagini recente » Cod sursa (job #2441020) | Cod sursa (job #2590881) | Cod sursa (job #130209) | Cod sursa (job #119146) | Cod sursa (job #2505613)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5 + 5;
int n;
pair <int, int> a[NMAX];
vector <int> v[2 * NMAX];
map <int, int> nrm;
int invnrm[2 * NMAX];
int dp[2 * NMAX];
int main()
{
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
fin >> n;
int x, y;
for (int i = 1;i <= n;++i)
{
fin >> a[i].first >> a[i].second;
nrm[a[i].first] = 1;
nrm[a[i].second] = 1;
}
int nrmval = 0;
for (auto &i : nrm)
{
i.second = ++nrmval;
invnrm[nrmval] = i.first;
}
for (int i = 1;i <= n;++i)
{
a[i].first = nrm[a[i].first];
a[i].second = nrm[a[i].second];
v[a[i].second].push_back(a[i].first);
}
n = nrmval;
for (int i = 1;i <= n;++i)
{
dp[i] = dp[i - 1];
for (auto &j : v[i])
dp[i] = max(dp[i], dp[j] + (invnrm[i] - invnrm[j]));
}
fout << dp[n] << "\n";
fin.close();
fout.close();
return 0;
}