Cod sursa(job #2537508)

Utilizator WladDalwMvladutu cristian vlad WladDalwM Data 3 februarie 2020 18:51:00
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

struct spectacol
{
    int a , b;
}v[100005];

int d[100005];

bool xort(spectacol x , spectacol y)
{
    if(x.b < y.b)
        return true;
    if(x.b == y.b && x.a <= y.a)
        return true;
    return false;
}

int main()
{
    int n , maxim = 0 , i , t , l , pas;
    cin >> n;
    for(i = 1; i <= n; i++)
    {
        cin >> v[i].a >> v[i].b;
    }
    sort(v + 1, v + n + 1, xort);
    for(t = 1; t <= n; t++)
    {
        l = 0;
        pas = 131072;
        while(pas)
        {
            if(l + pas <= n)
            if(v[l + pas].b <= v[t].a)
                l += pas;

            pas /= 2;
        }
        d[t] = max( d[l] + v[t].b - v[t].a , maxim);
        maxim = max(d[t] , maxim);
    }
    cout << d[n];

    return 0;
}