Cod sursa(job #2050129)

Utilizator OldpugAlex Ionescu Oldpug Data 27 octombrie 2017 22:59:07
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda hlo2017_cj_av_l4 Marime 0.77 kb
#include <bits/stdc++.h>

class band_t final
{
public:
  int start, end;

  bool operator<(const band_t &band) const
  {
    return end < band.end;
  }
};

band_t bnd[100005];
long long dyn[100005];
int n;

int binary_search(int val)
{
  int step = 1 << 17, pos = 0;

  while (step != 0)
  {
    if (pos + step <= n && bnd[pos + step].end <= val)
      pos += step;

    step /= 2;
  }

  return pos;
}

int main()
{
  std::ifstream in("heavymetal.in");
  in >> n;

  for (auto i = 1; i <= n; ++i)
    in >> bnd[i].start >> bnd[i].end;

  std::sort(bnd + 1, bnd + n + 1);
  dyn[1] = bnd[1].end - bnd[1].start;

  for (auto i = 2; i <= n; ++i)
    dyn[i] = std::max((bnd[i].end - bnd[i].start) + dyn[binary_search(bnd[i].start)], dyn[i - 1]);

  std::ofstream("heavymetal.out") << dyn[n];
}