Pagini recente » Cod sursa (job #216862) | Cod sursa (job #2538794) | Cod sursa (job #2384481) | Cod sursa (job #967789) | Cod sursa (job #2559146)
#include <bits/stdc++.h>
#define DAU ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
#define PLEC fin.close(); fout.close(); return 0;
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
unordered_map<int, int> M, nr;
vector<pair<int, int>> v;
vector<int> sorted, dp;
vector<vector<int>> before;
int n, cnt;
int main()
{
DAU
fin >> n;
v = vector<pair<int, int>>(n + 1);
for (int i = 1; i <= n; ++i)
{
fin >> v[i].first >> v[i].second;
sorted.emplace_back(v[i].first);
sorted.emplace_back(v[i].second);
}
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
for (const int& x : sorted)
M[x] = ++cnt, nr[cnt] = x;
before = vector<vector<int>>(cnt + 1);
for (int i = 1; i <= n; ++i)
before[M[v[i].second]].emplace_back(M[v[i].first]);
dp = vector<int>(cnt + 1);
for (int i = 1; i <= cnt; ++i)
{
dp[i] = dp[i-1];
for (const int& j : before[i])
dp[i] = max(dp[i], dp[j] + nr[i] - nr[j]);
}
fout << dp[cnt];
PLEC
}