Cod sursa(job #2358943)

Utilizator DovlecelBostan Andrei Dovlecel Data 28 februarie 2019 14:47:16
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int N=100005;
pair<int,int>v[N];
int n,best[N];

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 binsc(int x)
{
    int p=0;
    for(int bit=16;bit>=0;bit--)
        if(p+(1<<bit)<x && v[p+(1<<bit)].second<=v[x].first)
            p=p+(1<<bit);
    return p;
}

int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i].first>>v[i].second;
    sort(v+1,v+n+1,cmp);
    int pred;
    for(int i=1;i<=n;i++)
    {
        pred=binsc(i);
        best[i]=max(best[i-1],v[i].second-v[i].first+best[pred]);
    }
    out<<best[n];
    return 0;
}