Cod sursa(job #1310583)

Utilizator hopingsteamMatraguna Mihai-Alexandru hopingsteam Data 6 ianuarie 2015 23:23:08
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 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(_2.B > _1.B)
        return 1;
    return 0;
}

int Search(int Left, int Right, int nr)
{
    int Sol = 0;
    while(Left < Right)
    {
        int Mid = (Left + Right) / 2;
        if(S[Mid].B >= nr)
        {
            Sol = Mid;
            Right = Mid - 1;
        }
        else
            Left = Mid + 1;
    }
    if(Left == Right) return Sol;
}

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, S+N+1, Compare);

    //DP[1] = S[1].Cost;

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

    cout << DP[N];
}

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