Cod sursa(job #2990430)

Utilizator dnprxDan Pracsiu dnprx Data 7 martie 2023 21:21:03
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
int n;
pair <int, int> a[100005];
long long dp[100005];

bool cmp (pair <int, int> a, pair <int, int> b)
{
    if (a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
}

int CB (int val)
{
    int st = 1, dr = n, mid, p = 0;
    while (st <= dr)
    {
        mid = (st + dr) / 2;
        if (a[mid].second <= val)
        {
            p = mid;
            st = mid + 1;
        }
        else dr = mid - 1;
    }
    return p;
}

int main()
{
    int i, j;
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i].first >> a[i].second;
    sort(a + 1, a + n + 1, cmp);
    dp[0] = 0;
    for (i = 1; i <= n; i++)
    {
        dp[i] = dp[i - 1];
        j = CB(a[i].first);
        dp[i] = max(dp[i], dp[j] + a[i].second - a[i].first);
    }
    fout << dp[n] << "\n";
    fout.close();
    return 0;
}