Cod sursa(job #2208395)

Utilizator testsursaSurseTest testsursa Data 29 mai 2018 16:27:03
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 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;
        for(int j=1;j<i;j++)
            if(v[i].st>=v[j].dr)
                pos=j;

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

    cout<<dp[n];

    return 0;
}