Cod sursa(job #2095231)

Utilizator SchnitzelMannPavaloiu Gabriel SchnitzelMann Data 27 decembrie 2017 11:36:34
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
long long a[100001][2],dp[1000];
void Merge(long long l,long long r,long long m)
{
    long long n1=m-l+1,n2=r-m,i,j=0,k=l;
    long long L[n1][2],R[n2][2];
    for(i=0;i<n1;i++)
    {
        L[i][0]=a[l+i][0];
        L[i][1]=a[l+i][1];
    }
    for(i=0;i<n2;i++)
    {
        R[i][0]=a[m+i+1][0];
        R[i][1]=a[m+i+1][1];
    }
    i=0;
    while(i<n1&&j<n2)
    {
        if(L[i][1]<R[j][1])
        {
            a[k][0]=L[i][0];
            a[k][1]=L[i][1];
            i++;
        }
        else
        {
            a[k][0]=R[j][0];
            a[k][1]=R[j][1];
            j++;
        }
        k++;
    }
    while(i<n1)
    {
        a[k][0]=L[i][0];
        a[k][1]=L[i][1];
        i++;
        k++;
    }
    while(j<n2)
    {
        a[k][0]=R[j][0];
        a[k][1]=R[j][1];
        j++;
        k++;
    }
}
void mergesort(long long l,long long r)
{
    if(r>l)
    {
        long long m=(l+r)/2;
        mergesort(l,m);
        mergesort(m+1,r);
        Merge(l,r,m);
    }
}
int main()
{
    long long n,i,j=1;
    in>>n;
    for(i=1;i<=n;i++)
        in>>a[i][0]>>a[i][1];
    mergesort(1,n);
    for(i=1;i<=a[n][1];i++)
    {
        dp[i]=dp[i-1];
        while(a[j][1]==i)
        {
            dp[i]=max(dp[i],dp[a[j][0]]+a[j][1]-a[j][0]);
            j++;
        }
    }
    out<<dp[a[n][1]];
    return 0;
}