Cod sursa(job #2603804)

Utilizator eugen5092eugen barbulescu eugen5092 Data 20 aprilie 2020 21:47:37
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;
ifstream ci("heavymetal.in");
ofstream cou("heavymetal.out");
struct date{
    int a,b;
};
int n,dp[100005];
date v[100005];
bool cmp(date a,date b){
    if(a.b!=b.b){
        return a.b<b.b;
    }else{
        return a.a<b.a;
    }
}
void citire(){
    ci>>n;
    for(int i=1;i<=n;i++){
        ci>>v[i].a>>v[i].b;
    }
    sort(v+1,v+n+1,cmp);
}

int cautare(int st,int dr,int x){
    int sol=st,mij;
    while(st<=dr){
        mij=(st+dr)/2;
        if(v[mij].b>x){
            dr=mij-1;
        }else{
            sol=mij;
            st=mij+1;
        }
    }
    return sol;
}

void rez(){
    int p;
    /*
    for(int i=1;i<=n;i++){
        cout<<v[i].a<<" "<<v[i].b<<"\n";
    }
    cout<<"\n";
    */
    dp[1]=v[1].b-v[1].a;
    for(int i=2;i<=n;i++){
        p=cautare(1,n,v[i].a);
        if(v[p].b<=v[i].a){
            dp[i]=max(dp[i-1],dp[p]+v[i].b-v[i].a);
        }else{
            dp[i]=max(dp[i-1],v[i].b-v[i].a);
        }
        //cout<<i<<" "<<dp[i]<<" "<<dp[i-1]<<" "<<p<<"\n";

    }
    cou<<dp[n];
}

int main()
{
    citire();
    rez();
    return 0;
}