Cod sursa(job #2135789)

Utilizator SenibelanMales Sebastian Senibelan Data 19 februarie 2018 11:06:57
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 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;
    V.push_back(Band(0, 0));
    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[1] = (V[1].end - V[1].begin);
    for(int i = 2; i <= N; ++i){
        int best = BinarySearch(i);
        DP[i] = max((V[i].end - V[i].begin) + DP[best], DP[i - 1]);
    }
    out << DP[N] << "\n";
}

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