Cod sursa(job #1310618)

Utilizator hopingsteamMatraguna Mihai-Alexandru hopingsteam Data 7 ianuarie 2015 00:05:21
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include    <iostream>
#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) //Aparent, se pot face variabile ce incep cu "_" ... Smecher
{
    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++)
    {
        cout << S[i].A << " " << S[i].B << "\n";
    }*/

    for(int i = 1; i <= N; i++)
    {
        DP[i] = max(    DP[i-1],
                        DP[Search(0, i, S[i].A)] + S[i].Cost  );
    }

    cout << DP[N];
}

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