Cod sursa(job #1368662)

Utilizator andrusca97Rosu Andrei andrusca97 Data 2 martie 2015 19:13:38
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");

const int Max = 100005;

int N,DP[Max],Z[Max];

struct SP{
    int a,b,timp;
}S[Max];
int Compare(SP pr, SP ul)
{
    if(pr.b==ul.b)
        return pr.a < ul.a;
    return pr.b < ul.b;
}

int Search(int Left, int Right, int pos)
{
    while(Left<=Right)
    {
        int Mid = (Left + Right) / 2;
        if(S[Mid].b <= pos)
            Left = Mid + 1;
        else
            Right = Mid - 1;
    }
    return Right;
}

void Read()
{
    in>>N;
    for(int i=1;i<=N;i++)
    {
        in>>S[i].a>>S[i].b;
        S[i].timp=S[i].b-S[i].a;
    }
    sort(S+1, S+N+1, Compare);
    for(int i=1;i<=N;i++)
    {
        DP[i]=max(DP[i-1], DP[Search(0,i,S[i].a)]+ S[i].timp);

    }
    out<<DP[N];
}

int main()
{
    Read();
    return 0;
}