Pagini recente » Cod sursa (job #917287) | Cod sursa (job #1464660) | Cod sursa (job #495962) | Cod sursa (job #2386962) | Cod sursa (job #2579099)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#define NMAX 100000
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int n, dp[2*NMAX+10];
struct date
{ int x, y, c;
}v[NMAX+10];
vector <int> a;
vector <pair <int, int> > val[2*NMAX+10];
unordered_map <int, int> umap;
int main()
{
f >> n;
for(int i=1; i<=n; i++)
{ f >> v[i].x >> v[i].y;
v[i].c = v[i].y - v[i].x;
a.push_back(v[i].x);
a.push_back(v[i].y);
}
sort(a.begin(), a.end());
int nr = 1;
umap[a[0]] = 1;
for(int i=1; i<a.size(); i++)
{ if(a[i] != a[i-1]) nr++;
umap[a[i]] = nr;
}
for(int i=1; i<=n; i++)
{ v[i].x = umap[v[i].x];
v[i].y = umap[v[i].y];
val[v[i].y].push_back(make_pair(v[i].c, v[i].x));
}
for(int i=1; i<=nr; i++)
{ dp[i] = dp[i-1];
for(int j=0; j<val[i].size(); j++) dp[i] = max(dp[i], val[i][j].first + dp[val[i][j].second]);
}
g << dp[nr] << '\n';
return 0;
}