Cod sursa(job #2801051)

Utilizator federicisFedericis Alexandru federicis Data 14 noiembrie 2021 19:00:44
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

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

long long n, dp[100001], limit;
pair<long long, long long> intervale[100001];

int binarySearch( int l, int r)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (intervale[mid].second <= limit)
        {
            if(mid + 1 > r)
            {
                return mid;
            }
            if(intervale[mid + 1].second > limit)
            {
                return mid;
            }
            else
            {
                return binarySearch(mid + 1, r);
            }
        }
        else
        {
            return binarySearch(l, mid - 1);
        }
    }
    return 0;
}

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 main()
{
    intervale[0].first = intervale[0].second = 0;
    dp[0] = 0;
    in >> n;
    for(int i = 1; i <= n; i++)
    {
        long long a,b;
        in >> a >> b;
        intervale[i] = {a,b};
    }
    sort(intervale + 1, intervale + n + 1, cmp);
    dp[1] = intervale[1].second - intervale[1].first;
    for(int i = 2; i <= n; i++)
    {
        limit = intervale[i].first;
        dp[i] = max(dp[i],dp[i - 1]);
        int poz = binarySearch(1, i - 1);
        dp[i] = max(dp[i], dp[poz] + intervale[i].second - intervale[i].first);
    }
    out << dp[n];

    return 0;
}