Cod sursa(job #3185098)

Utilizator xXoctavianXxStanescu Matei Octavian xXoctavianXx Data 17 decembrie 2023 22:42:36
Problema Heavy metal Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>
#define int long long

using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

const int nmax = 2e5+5;
int dp[2*nmax];

struct Event{
    int l,r,val;
    bool operator < (const Event &other)
    {
        return r < other.r;
    }
};

signed main()
{
    int n; fin>>n;
    vector<Event> v(n,{0,0,0});
    map<int,int> norm;
    for(int i=0; i<n; i++)
    {
        fin>>v[i].l>>v[i].r;
        v[i].val = v[i].r - v[i].l;
        v[i].r --;
        norm[v[i].l] = 1;
        norm[v[i].r] = 1;
    }
    int cnt = 1;
    for(auto p: norm)
    {
        norm[p.first] = cnt++;
    }
    for(int i=0; i<n; i++)
        v[i] = {norm[v[i].l],norm[v[i].r],v[i].val};
    sort(v.begin(),v.end());

    int i=0;
    for(int timp = 1; timp <= 2*n; timp++)
    {
        dp[timp] = dp[timp-1];
        while(v[i].r < timp)
        {
            i++;
        }
        while(v[i].r == timp)
        {
            dp[timp] = max(dp[timp],dp[v[i].l-1] + v[i].val);
            i++;
        }
    }
    fout<<dp[2*n];
    return 0;
}