Cod sursa(job #3184841)

Utilizator Dia3141Costea Diana Stefania Dia3141 Data 17 decembrie 2023 10:52:22
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
int n,i,k,d[100003];
struct formatie{
int st,dr;
}v[100003];
bool cmp(formatie a,formatie b){
    if(a.dr==b.dr)
        return a.st<b.st;
    return a.dr<b.dr;
}
int main()
{
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>v[i].st>>v[i].dr;
    }
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++){
        int st=1,dr=i-1,poz=0;
        while(st<=dr){
            int mid=(st+dr)/2;
            if(v[mid].dr>v[i].st)
                dr=mid-1;
            else{
                st=mid+1;
                poz=mid;
            }
        }
        d[i]=d[poz]+v[i].dr-v[i].st;
        d[i]=max(d[i-1],d[i]);
    }
    cout<<d[n];
    return 0;
}