Cod sursa(job #2810866)

Utilizator TraianQTraianQ TraianQ Data 30 noiembrie 2021 14:31:34
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <algorithm>
using namespace std;
int n,rez[100005];
struct Nr
{
    int st,dr;
}v[100005];
bool cmp(Nr x,Nr y)
{
    if(x.dr!=y.dr)
        return x.dr<y.dr;
    return x.st<y.st;
}
int c_binara(int x)
{
    int st=1,dr=n;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(v[mij].dr<=x)
            st=mij+1;
        else
            dr=mij-1;
    }
    return dr;
}
int main()
{
    ifstream cin("heavymetal.in");
    ofstream cout("heavymetal.out");
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].st>>v[i].dr;
    }
    sort(v+1,v+n+1,cmp);
    int k,j,rezultat=0;
    for(int i=1;i<=n;i++)
    {
        j=c_binara(v[i].st);
        rez[i]=max(rez[i-1],rez[j]+v[i].dr-v[i].st);
        rezultat=max(rezultat,rez[i]);
    }
    cout<<rezultat;
    return 0;
}