Cod sursa(job #2553477)

Utilizator Andrei012Trache Andrei Andrei012 Data 22 februarie 2020 00:35:14
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
struct ura{
    int a,b;
};
bool cmp(ura a,ura b){
    if(a.b<=b.b)
        return true;
    return false;
}
ura v[100001];
long long d[100001];
int main()
{
    int n,i,st,dr,mij,elem;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i].a>>v[i].b;
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++){
        st=0;
        dr=i-1;
        while(st<=dr){
            mij=(st+dr)/2;
            if(v[mij].b>v[i].a)
                dr=mij-1;
            else{
                st=mij+1;
                elem=mij;
            }
            d[i]=max(d[i-1],d[elem]+v[i].b-v[i].a);
        }
    }
    cout<<d[n];
    return 0;
}