Cod sursa(job #2383195)

Utilizator CosaMateiMatei Cosa Gabriel CosaMatei Data 19 martie 2019 10:19:44
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

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

const int N=100000+2;

vector <pair<int,int>> v;

int d[N];

int n;

void read()
{
    in>>n;
    int x,y;
    for(int i=1;i<=n;++i)
    {
        in>>x>>y;
        v.push_back(make_pair(x,y));
    }
}

bool cmp(pair <int,int> a, pair<int,int> b)
{
    if(a.second != b.second)
    {
        return (a.second<b.second);
    }
    return (a.first<b.first);
}

int bSearch(int x)
{
    int pas=1<<17;
    int ans=0;
    while(pas)
    {
        if(ans+pas<n && v[ans+pas].second<=x)
        {
            ans+=pas;
        }
        pas/=2;
    }
    return ans;
}

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