Cod sursa(job #1310605)

Utilizator contfantoma69fantoma contfantoma69 Data 6 ianuarie 2015 23:48:57
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 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)
{
    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 - 1;
    return 0;
}*/

int Search(int s,int e,int lim)
{
    if(s==e)
        return s-1;
    int m=(s+e)/2;
    if(S[m].B>lim)
        return Search(s,m,lim);
    return Search(m+1,e,lim);
}

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;
}