Cod sursa(job #2481481)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 26 octombrie 2019 23:06:45
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
int n,t,dp[100100],ans,l,r,p;
struct hm
{
    int l,r;
}v[100100];
bool cmp(hm a,hm b)
{
    return a.r<b.r||(a.r==b.r&&a.l<b.l);
}
int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i].l>>v[i].r;
    sort(v+1,v+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        dp[i]=dp[i-1];
        l=0;
        r=n;
        ///caut cea mai mare dreapta mai mica decat stanga intervalului curent
        p=0;
        while(l<=r)
        {
            int m=(l+r)/2;
            if(v[m].r>v[i].l) r=m-1;
            else
            {
                p=max(m,p);
                l=m+1;
            }
        }
        dp[i]=max(dp[i],dp[p]+v[i].r-v[i].l);
        ans=max(ans,dp[i]);
    }
    out<<ans;
    return 0;
}