Cod sursa(job #1310717)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 7 ianuarie 2015 09:03:41
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include    <fstream>
#include    <algorithm>
 
using namespace std;
 
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
 
const int NMax = 100005;
 
struct Spectacol
{
    int A, B, Cost;
}S[NMax];
 
int N;
int DP[NMax];
 
int Compare(Spectacol _1, Spectacol _2)
{
    if(_1.B == _2.B)
        return _1.A < _2.A;
    return _1.B < _2.B;
}
 
int Search(int Left, int Right, int nr)
{
    while(Left <= Right)
    {
        int Mid = (Left + Right) / 2;
        if(S[Mid].B <= nr)
            Left = Mid + 1;
        else
            Right = Mid - 1;
    }
    return Right;
}
 
void Read()
{
    fin >> N;
    for(int i = 1; i <= N; i++)
    {
        fin >> S[i].A >> S[i].B;
        S[i].Cost = 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].Cost  );
    }
 
    fout << DP[N];
}
 
int main()
{
    Read();
    return 0;
}