Cod sursa(job #1310588)

Utilizator contfantoma69fantoma contfantoma69 Data 6 ianuarie 2015 23:27:54
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 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 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, 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;
}