Cod sursa(job #1939414)

Utilizator SenibelanMales Sebastian Senibelan Data 25 martie 2017 18:30:34
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

struct spectacol{
  int inceput, sfarsit;
};

int N;
vector <spectacol> V;
vector <int> DP;

bool cmp(spectacol a, spectacol b){
  return a.sfarsit < b.sfarsit;
}

void Read(){
  spectacol aux;
  in >> N;
  for(int i = 1; i <= N; ++i){
    in >> aux.inceput >> aux.sfarsit;
    V.push_back(aux);
  }
  sort(V.begin(), V.end(), cmp);
}

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

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

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