Cod sursa(job #2506180)

Utilizator trifangrobertRobert Trifan trifangrobert Data 7 decembrie 2019 17:37:29
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5 + 5;
int n, dp[NMAX];
pair <int, int> a[NMAX];

int BinarySearch(int val)
{
    int left = 1, right = n, mid, pos = 0;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (a[mid].second <= val)
        {
            pos = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
    return pos;
}

int main()
{
    ifstream fin("heavymetal.in");
    ofstream fout("heavymetal.out");
    fin >> n;
    for (int i = 1;i <= n;++i)
        fin >> a[i].first >> a[i].second;
    sort(a + 1, a + n + 1, [&](pair <int, int> x, pair <int, int> y)
    {
        return x.second < y.second;
    });
    for (int i = 1;i <= n;++i)
    {
        int p = BinarySearch(a[i].first);
        dp[i] = max(dp[i - 1], dp[p] + a[i].second - a[i].first);
    }
    fout << dp[n] << "\n";
    fin.close();
    fout.close();
    return 0;
}