Pagini recente » Istoria paginii runda/oji12_simulare/clasament | Istoria paginii runda/oni_10_1 | Istoria paginii runda/no_feed/clasament | Cod sursa (job #1985087) | Cod sursa (job #2970469)
#include <fstream>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#define ll long long
using namespace std;
const int NMAX = 100000;
int v[NMAX + 1][2];
int cnt;
map <int, int> mp;
//d[i] = timpul maxim ocupat pana la momentul de timp i pe care il pot
//canta formatiile
//esti la formatia j: d[v[j].b] = max(d[v[j].a] + v[j].b - v[j].a)
//d[v[j].b] = max(d[v[j].b], d[v[j].b-1])
long long d[2 * NMAX + 1];
pair <int, int> vec[NMAX + 1];
bool cmp(pair <int, int> a, pair <int, int> b)
{
return v[a.first][a.second] < v[b.first][b.second];
}
int main()
{
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
int n, i;
cin >> n;
for (i = 1; i <= n; i++)
{
cin >> v[i][0] >> v[i][1];
vec[2 * i - 1] = {i, 0};
vec[2 * i] = {i, 1};
mp[v[i][0]] = 0;
mp[v[i][1]] = 0;
}
sort(vec + 1, vec + 2 * n + 1, cmp);
for (auto it = mp.begin(); it != mp.end(); it++)
it->second = ++cnt;
long long ans = 0;
for (i = 1; i <= 2 * n; i++)
{
int v1 = mp[v[vec[i].first][vec[i].second]];
int v2 = mp[v[vec[i].first][!vec[i].second]];
d[v1] = max(d[v1], d[v1 - 1]);
ans = max(ans, d[v1]);
if (vec[i].second == 1)
{
d[v1] = max(d[v1], d[v2] + v[vec[i].first][1] - v[vec[i].first][0]);
ans = max(ans, d[v1]);
}
}
cout << ans;
}