Cod sursa(job #2153591)

Utilizator TeoMiliMilitaru Teodora TeoMili Data 6 martie 2018 12:31:01
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <algorithm>
using namespace std;
int n,i,Max,d[100001],st,dr,mid,sol;
struct numar{
int st;
int dr;
}t[100001];
int cmp(numar a,numar b){
    if(a.dr==b.dr)
        return(a.st<b.st);
    return(a.dr<b.dr);
}
int main()
{
    ifstream cin("heavymetal.in");
    ofstream cout("heavymetal.out");
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>t[i].st>>t[i].dr;
    sort(t+1,t+n+1,cmp);
    d[1]=t[1].dr-t[1].st;
    for(i=2;i<=n;i++){
        Max=t[i].dr-t[i].st;
        if(t[i].st>=t[i-1].dr)
            Max=d[i-1]+t[i].dr-t[i].st;
        st=1;dr=i-1;
        sol=0;
        while(st<=dr){
            mid=(st+dr)/2;
            if(t[mid].dr<=t[i].st){
                sol=mid;
                st=mid+1;
            }
            else
                dr=mid-1;
        }
        Max=max(Max,d[sol]+t[i].dr-t[i].st);
        d[i]=Max;
    }
    Max=0;
    for(i=1;i<=n;i++)
        if(d[i]>Max)
            Max=d[i];
    cout<<Max;


    return 0;
}