Cod sursa(job #2642667)

Utilizator stefantagaTaga Stefan stefantaga Data 16 august 2020 18:04:20
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct wow
{
    int x,y;
}v[100005];
bool compare (wow a,wow b)
{
    return a.y<b.y||(a.y==b.y&&a.x<b.x);
}
int n,i,st,dr,mij,sol,din[100005],maxim[100005],solutie;
int main()
{
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;
    }
    sort (v+1,v+n+1,compare);
    for (i=1;i<=n;i++)
    {
        st=1;
        dr=i-1;
        sol=0;
        while (st<=dr)
        {
            mij=(st+dr)/2;
            if (v[i].x>=v[mij].y)
            {
                sol=mij;
                st=mij+1;
            }
            else
            {
                dr=mij-1;
            }
        }
        din[i]=maxim[sol]+v[i].y-v[i].x;
        maxim[i]=max(maxim[i-1],din[i]);
    }
    for (i=1;i<=n;i++)
    {
        solutie=max(solutie,maxim[i]);
    }
    g<<solutie;
    return 0;
}