Cod sursa(job #2575586)

Utilizator Codrut112Codrut Copas Codrut112 Data 6 martie 2020 14:32:34
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int n,i,dp[100000],mx;
struct metal
{
    int start;
    int sf;
} v[100];
bool comp(metal a,metal b)
{
    return a.start<b.start;
}
int caut(int poz)
{
    int st=1;
    int dr=poz;
    int mx=0;
    while(st<=dr)
    {
       int  mid=(st+dr)/2;
        if(dp[mid]!=0)
        {
            mx=max(mx,dp[mid]);
            st=mid+1;

        }
        else dr=mid-1;

    }
    return mx;
}

int main()
{
    f>>n;
    for(i=1; i<=n; i++)
        f>>v[i].start>>v[i].sf;
    sort(v+1,v+n+1,comp);
    for(i=1; i<=n; i++)
    {
        if(dp[v[i].start]==0 and i!=1)
        {
            dp[v[i].start]=caut(v[i].start);

        }
        dp[v[i].sf]=max(dp[v[i].sf],dp[v[i].start]+v[i].sf-v[i].start);
                    mx=max(mx,dp[v[i].sf]);

    }g<<mx;

}