Cod sursa(job #2135960)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 19 februarie 2018 15:36:25
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
const int nmax=100000;
struct data
{
    int st,dr;
};
bool cmp(data a,data b)
{
    if(a.dr!=b.dr)
        return a.dr<b.dr;
    return a.st<b.st;
}
int n;
data v[nmax+5];
int best[nmax+5];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].st>>v[i].dr;
        v[i].dr--;
    }
    sort(v+1,v+n+1,cmp);
    best[1]=v[1].dr-v[1].st+1;
    for(int i=2;i<=n;i++)
    {
        int r=0,pas=(1<<16);
        while(pas)
        {
            if(r+pas<i && v[r+pas].dr<v[i].st)
                r+=pas;
            pas/=2;
        }
        best[i]=max(best[i-1],best[r]+v[i].dr-v[i].st+1);
    }
    cout<<best[n];
    return 0;
}
/**

**/