Cod sursa(job #2106325)

Utilizator MatteusTanase Matei Matteus Data 15 ianuarie 2018 16:52:20
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int N=100005;
const int L=30;

struct spectacol
{
    int start, stop;
} v[N];

int n, sfarsit[N], m, dp[N];

bool cmp(spectacol x, spectacol y)
{
    return x.stop < y.stop;
}

int caut(int x)
{
    int r=0,pas=1<<L;
    while(pas!=0)
    {
        if(r+pas<=m && sfarsit[r+pas]<=x)
            r+=pas;
        pas/=2;
    }
    return r;
}

void citire()
{
    cin>>n;

    for(int i=1; i<=n; i++)
        cin>>v[i].start>>v[i].stop;
}

void sortare()
{
    /*
    for(int i=1; i<n; i++)
        for(int j=i+1; j<=n; j++)
            if(v[i].stop>v[j].stop)
                swap(v[i], v[j]);
    */
    sort(v + 1, v + n + 1, cmp);
}

void solve()
{
    int i, j, dr, st;

    sfarsit[1]=v[1].stop;
    for(i=2, j=1; i<=n; i++)
    {
        if(v[i].stop != v[i-1].stop)
            sfarsit[++j] = v[i].stop;
    }
    m=j;

    //for(i=1; i<=m; i++)
        //cout<<sfarsit[i]<<' ';

    for(i=1; i<=n; i++)
    {
        st=caut(v[i].start);
        dr=caut(v[i].stop);
        dp[dr]=max(dp[dr], dp[st]+v[i].stop-v[i].start);
        dp[dr]=max(dp[dr], dp[dr-1]);
        //cout<<dp[i]<<' ';
    }

    cout<<dp[m];
}



int main()
{
    citire();
    sortare();
    solve();
    return 0;
}