Cod sursa(job #3305176)

Utilizator Cyb3rBoltSbora Ioan-David Cyb3rBolt Data 30 iulie 2025 15:21:41
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n, dp[200010];
vector<int> aux;

struct Iris {
    int st, dr, durata;
}v[100010];

inline int cmp(Iris a, Iris b) { return a.dr < b.dr; }

int main()
{
    fin >> n;
    for(int i=1; i<=n; i++) {
        fin >> v[i].st >> v[i].dr, v[i].dr--;
        v[i].durata = v[i].dr - v[i].st + 1;
        aux.push_back(v[i].st);
        aux.push_back(v[i].dr);
    }
    sort(aux.begin(), aux.end());
    vector<int>::iterator it = unique(aux.begin(), aux.end());
    aux.resize(distance(aux.begin(), it));
    for(int i=1; i<=n; i++) {
        v[i].st = lower_bound(aux.begin(), aux.end(), v[i].st) - aux.begin() + 1;
        v[i].dr = lower_bound(aux.begin(), aux.end(), v[i].dr) - aux.begin() + 1;
    }
    sort(v+1, v+n+1, cmp);
    int index = 1;
    for(int i=1; i<=200000; i++) {
        dp[i] = dp[i - 1];
        while(v[index].dr == i) dp[i] = max(dp[i], dp[v[index].st - 1] + v[index].durata), index++;
    }
    fout << dp[200000];

    return 0;
}