Cod sursa(job #2135784)

Utilizator SenibelanMales Sebastian Senibelan Data 19 februarie 2018 11:01:27
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct Band{
    int begin, end;

    Band(int b, int e){
        begin = b;
        end = e;
    }

    bool const operator<(const Band &other)const{
        return end < other.end;
    }
};

const int NMAX = 100005;
int N;
int DP[NMAX];
vector <Band> V;

void Read(){
    in >> N;
    for(int i = 1; i <= N; ++i){
        int a, b;
        in >> a >> b;
        V.push_back(Band(a, b));
    }
    sort(V.begin(), V.end());
}

int BinarySearch(int poz){
    int sol = 0;
    int left = 0, right = N + 5;
    while(left <= right){
        int mid = (left + right) / 2;
        if(mid < N && V[mid].end <= V[poz].begin){
            sol = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
    return sol;
}

void SolveAndPrint(){
    DP[0] = (V[0].end - V[0].begin);
    for(int i = 1; i < N; ++i){
        int best = BinarySearch(i);
        DP[i] = max((V[i].end - V[i].begin) + DP[best], DP[i - 1]);
    }
    out << DP[N - 1] << "\n";
}

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