Cod sursa(job #2208396)

Utilizator testsursaSurseTest testsursa Data 29 mai 2018 16:32:51
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>

using namespace std;

const int a=100005;
int dp[a],cnt,n,i;
struct tt
{
    int st,dr;
}v[a],aux[a];
void merg(int l,int r)
{
    if(l==r)
        return;
    int mij=(l+r)/2;
    merg(l,mij);
    merg(mij+1,r);

    int i=l;
    int j=mij+1;
    cnt=0;

    while(i<=mij&&j<=r)
    {
     if(v[i].dr<=v[j].dr)
        aux[++cnt]=v[i++];
    else aux[++cnt]=v[j++];
    }
    while(i<=mij)
        aux[++cnt]=v[i++];
    while(j<=r)
        aux[++cnt]=v[j++];
    for(i=l;i<=r;i++)
        v[i]=aux[i-l+1];
}

int main()
{
    ifstream cin("heavymetal.in");
    ofstream cout("heavymetal.out");

    cin>>n;
    for(i=1;i<=n;i++)
    cin>>v[i].st>>v[i].dr;
    merg(1,n);
    //for(i=1;i<=n;i++)
      //  cout<<v[i].st<<" "<<v[i].dr<<endl;

    for(i=1;i<=n;i++)
    {
        int pos=0;
        int lef=1,rig=i-1;
        while(lef<=rig)
        {
            int mij=(lef+rig)/2;
            if(v[mij].dr<=v[i].st)
            {
                pos=mij;
                lef=mij+1;
            }
            else rig=mij-1;

        }

        dp[i]=max(dp[i-1],dp[pos]+v[i].dr-v[i].st);
    }

    cout<<dp[n];

    return 0;
}