Cod sursa(job #2685800)

Utilizator Botzki17Botocan Cristian-Alexandru Botzki17 Data 17 decembrie 2020 18:57:05
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMAX = 100000;
struct interval{
    long long start, finish, val;
    bool operator < (const interval &a) const{
        if(finish == a.finish)
            return start < a.start;
        else return finish < a.finish;
    }
};
vector<interval> v;
long long dp[NMAX+5];
int cautare_binara(int st, int dr, interval x)
{
    int sol = -1;
    while(st <= dr)
    {
       int mid = (st + dr) >>1;
       if(v[mid].finish <= x.start)
       {
          sol = mid;
          st = mid + 1;
       }
       else dr = mid -1;

    }
    return sol + 1;
}

int main()
{
    int n, i;
    long long a, b;
    fin>>n;
    for(i = 1; i <=n ;i++)
    {
       fin>>a>>b;
       interval aux;
       aux.start = a;
       aux.finish = b;
       aux.val = b - a;
       v.push_back(aux);
    }
    sort(v.begin(), v.end());
    for(int i =0; i < v.size(); i++)
    {
        int index = cautare_binara(0, i -1, v[i]);
        dp[i + 1] = max(dp[i], dp[index] + v[i].val);

    }
    fout<<dp[n]<<"\n";
    return 0;
}