Cod sursa(job #1028356)

Utilizator Anca_PaneaPanea Anca Anca_Panea Data 13 noiembrie 2013 21:49:13
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<fstream>
#include<algorithm>
#define Nmax 100005
using namespace std;
ifstream eu("heavymetal.in");
ofstream tu("heavymetal.out");
struct Interval{
    int left,right;
}Int[Nmax];
int N,DP[Nmax];
bool Cmp(Interval X,Interval Y)
{
    return X.right<Y.right;
}
void Read()
{
    eu>>N;
    for(int i=1;i<=N;i++)
        eu>>Int[i].left>>Int[i].right;
    sort(Int+1,Int+N+1,Cmp);
}
int Binary(int left,int right,int val)
{
    int p=0,middle;
    while(left<=right)
    {
        middle=(left+right)/2;
        if(Int[middle].right<=val)
        {
            p=middle;
            left=middle+1;
        }
        else
            right=middle-1;
    }
    return p;
}
void Solve()
{
    for(int i=1;i<=N;i++)
    {
        int j=Binary(1,i-1,Int[i].left);
        DP[i]=max(DP[i-1],DP[j]+Int[i].right-Int[i].left);
    }
}
void Print()
{
    tu<<DP[N]<<"\n";
}
int main()
{
    Read();
    Solve();
    Print();
    return 0;
}