Cod sursa(job #2973687)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 1 februarie 2023 16:32:35
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;

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

/**
dp[t] =  timpul maxim pe care il ascultam pana la secunda t

pentru concertul (l, r):
dp[l] = max(dp[l], dp[l-1])
dp[r] = max(dp[r], dp[l-1] + (r - l + 1)
**/

#define l a[i].first
#define r a[i].second

pair<int, int>a[100001];

int dp[200001];
vector<pair<int, int>>R[200001]; /// R[i] = care au capat in dreapta, {L, C} -> capatul din stanga de la segment, costul

int main()
{
    int n;
    in >> n;

    vector<int>norm;

    for (int i=1; i<=n; i++)
    {
        in >> l >> r;

        norm.push_back(l);
        norm.push_back(r);
    }

    sort(norm.begin(), norm.end());

    for (int i=1; i<=n; i++)
    {
        int c = r - l;

        l = lower_bound(norm.begin(), norm.end(), l) - norm.begin() + 1;
        r = lower_bound(norm.begin(), norm.end(), r) - norm.begin() + 1;

        R[r].push_back({l, c});
    }

    int m = (n << 1);

    for (int rt=1; rt<=m; rt++)
    {
        dp[rt] = max(dp[rt], dp[rt-1]);

        for (pair<int, int> pr : R[rt])
            {
                int lt = pr.first;
                int C = pr.second;

                dp[rt] = max(dp[rt], dp[lt] + C);
            }
    }

    out << dp[m];

    return 0;
}