Cod sursa(job #1939417)

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

using namespace std;

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

struct spectacol{
  int inceput, sfarsit;
};

int N;
const int NMAX = 100000;
spectacol V[NMAX];
int DP[NMAX];

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 >> V[i].inceput >> V[i].sfarsit;
  sort(V + 1, V + N + 1, cmp);
}

int BinarySearch(int poz){
  int left = 1;
  int right = poz - 1;
  int mid, sol = 1;
  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[1] = V[1].sfarsit - V[1].inceput;
  for(int i = 2; i <= N; ++i){
    int best = BinarySearch(i);
    DP[i]= max((V[i].sfarsit - V[i].inceput) + DP[best], DP[i - 1]);
  }
  out << DP[N] << "\n";
}

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