Pagini recente » Borderou de evaluare (job #586429) | Borderou de evaluare (job #757907) | Cod sursa (job #1320081) | Borderou de evaluare (job #655519) | Cod sursa (job #2504901)
#include <fstream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMAX = 100000;
const int INF = 1e9;
struct sp
{
int l, r, len;
bool operator < (const sp other) const
{
if(r != other.r)
return r < other.r;
return l < other.l;
}
};
int N;
sp v[4 * NMAX + 5];
vector <int> p;
unordered_map <int, int> mp;
int dp[4 * NMAX + 5];
int main()
{
fin >> N;
for(int i = 1; i <= N; i++)
{
fin >> v[i].l >> v[i].r;
v[i].len = v[i].r - v[i].l;
p.push_back(v[i].l);
p.push_back(v[i].r);
}
int k = 0;
sort(p.begin(), p.end());
for(auto it : p)
if(mp[it] == 0)
mp[it] = ++k;
int maxT = 0;
for(int i = 1; i <= N; i++)
{
v[i].l = mp[v[i].l];
v[i].r = mp[v[i].r];
maxT = max(maxT, v[i].r);
}
for(int i = 1; i <= maxT; i++)
{
v[++N].l = i;
v[N].r = i;
v[N].len = 0;
}
sort(v + 1, v + N + 1);
for(int i = 1; i <= maxT; i++)
dp[i] = -INF;
dp[0] = 0;
for(int i = 1; i <= N; i++)
dp[v[i].r] = max(dp[v[i].r], max(dp[v[i - 1].r], dp[v[i].l] + v[i].len));
fout << dp[maxT] << '\n';
return 0;
}