Cod sursa(job #2383240)

Utilizator CosaMateiMatei Cosa Gabriel CosaMatei Data 19 martie 2019 11:16:29
Problema Heavy metal Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int N=100000+2;

struct spectacol
{
    int start;
    int fin;
};

spectacol v[N];

int d[N];

int n;

void read()
{
    in>>n;
    for(int i=1;i<=n;++i)
    {
       in>>v[i].start>>v[i].fin;
    }
}

bool cmp(spectacol a, spectacol b)
{
    if(a.fin != b.fin)
    {
        return (a.fin<b.fin);
    }
    return (a.start<b.start);
}

int bSearch(int x)
{
    int p=0;
    for(int bit=16;bit>=0;bit--)
        if(p+(1<<bit)<x && v[p+(1<<bit)].fin<=x)
            p=p+(1<<bit);
    return p;
}

int main()
{
    read();
    sort(v+1,v+n+1,cmp);
    d[1]=v[1].fin-v[1].start;
    for(int i=2;i<=n;++i)
    {
        d[i]=max(d[i-1],d[bSearch(v[i].start)]+v[i].fin-v[i].start);
    }
    out<<d[n];
    return 0;
}