Cod sursa(job #2378779)

Utilizator vladstanciuVlad Stanciu vladstanciu Data 12 martie 2019 16:58:05
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>

#include <fstream>

#include <algorithm>



using namespace std;



ifstream in("heavymetal.in");

ofstream out("heavymetal.out");



const int N=100002;

const int L=29;



int n,a,b,d[N];





struct obiect

{

    int ora_inc;

    int ora_sf;

} v[N];





int caut1(int x)

{

    int pas=1<<L;

    int r=0;

    while(pas!=0)

    {

        if(r+pas<=n && v[r+pas].ora_sf<=x)

            r+=pas;

        pas/=2;

    }

    return r;

}



bool cmp(obiect x, obiect y)

{

    return x.ora_sf < y.ora_sf;

}



void citire()

{

    in>>n;

    for(int i=1; i<=n; ++i) in>>v[i].ora_inc>>v[i].ora_sf;

    sort(v+1,v+n+1,cmp);

}





int main()

{

    citire();

    for(int i=1; i<=n; ++i)

        {

            int a=v[i].ora_sf-v[i].ora_inc+d[caut1(v[i].ora_inc)];

            d[i]=max(d[i-1],a);

        }

        out<<d[n];

    return 0;

}