Cod sursa(job #2060176)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 7 noiembrie 2017 22:14:58
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <algorithm>
#include <fstream>

using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

const int NMax = 100005;
const int inf = 0x3f3f3f3f;
int N, dp[NMax];

struct Trupa
{
    int low, high;
}v[NMax];

void Read()
{
    fin >> N;
    for(int i=1; i<=N; ++i)
        fin >> v[i].low >> v[i].high;
}

bool cmp(Trupa A, Trupa B)
{
    if(A.high == B.high)
        return A.low < B.low;

    return A.high < B.high;
}

int Caut_Bin(int x)
{
    int st = 0;
    int dr = x - 1;
    int mij;

    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if (v[mij].high <= v[x].low)
            st = mij + 1;
        else
            dr = mij - 1;
    }

    return dr;
}

void Solve()
{
    sort(v+1, v+N+1, cmp);

    for(int i=1; i<=N; ++i)
    {
        dp[i] = max(v[i].high - v[i].low + dp[Caut_Bin(i)], dp[i-1]);
    }

    fout << dp[N];
}

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