Cod sursa(job #2455604)

Utilizator Ionut28Porumb Palincas Ionut Ionut28 Data 12 septembrie 2019 07:12:39
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

const int nmax = 100000;
struct interval
{
    int st,  dr;
};
interval v[nmax + 5];
bool cmp(const interval a, const interval b)
{
    if(a.dr == b.dr)
        return a.st < b.st;
    return a.dr < b.dr;
}
int cautarebinara(int i)
{
    int x = 1, y = i - 1, sol = 0;
    while(x <= y)
    {
        int mid = (x + y) >> 1;
        if(v[mid].dr <= v[i].st)
        {
            x = mid + 1;
            sol = mid;
        }
        else
            y = mid - 1;

    }
    return sol;
}
int n, dp[nmax + 5], best[nmax + 5];
int main()
{
    fin >> n;
    for(int i = 1; i <= n; ++i)
    {
        fin >> v[i].st >> v[i].dr;
    }
    sort(v + 1, v + n + 1, cmp);
    for(int i = 1; i <= n; ++i)
    {
        dp[i] = dp[i - 1];
        int x = cautarebinara(i);
        dp[i] = max(dp[i], dp[x] + (v[i].dr - v[i].st));
    }
    fout << dp[n] << "\n";
    fout.close();
    return 0;
}