Cod sursa(job #2271068)

Utilizator pionierul22aNa LiZa pionierul22 Data 27 octombrie 2018 23:43:43
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n,maxi,st,dr,mid,sol;
int d[100001];

struct numar
{
    int st,dr;

}t[100001];

int criteriu(numar a,numar b){
    if(a.dr==b.dr)
        return(a.st<b.st);
    return(a.dr<b.dr);
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>t[i].st>>t[i].dr;

    sort(t+1,t+n+1,criteriu);

    d[1]=t[1].dr-t[1].st;

    for(int i=2;i<=n;i++)
        {
            d[i]=max(t[i].dr-t[i].st,d[i-1]);
            if(t[i].st>=t[i-1].dr)
                d[i]=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;
            }
            if(sol!=0)
            d[i]=max(d[i],d[sol]+t[i].dr-t[i].st);
    }

    maxi=0;
    for(int i=1;i<=n;i++)
        if(d[i]>maxi)
            maxi=d[i];
    fout<<maxi;
    return 0;
}