Cod sursa(job #2970466)

Utilizator AswVwsACamburu Luca AswVwsA Data 25 ianuarie 2023 10:58:29
Problema Heavy metal Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#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[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;
}