Cod sursa(job #2026707)

Utilizator cella.florescuCella Florescu cella.florescu Data 24 septembrie 2017 21:44:47
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;

struct Stuff {
  int a, b;
  bool operator < (const Stuff &other) const {
    return b < other.b;
  }
} v[MAXN + 1];

int dp[MAXN + 1];

int main()
{
    int n;
    ifstream fin("heavymetal.in");
    fin >> n;
    for (int i = 1; i <= n; ++i)
      fin >> v[i].a >> v[i].b;
    fin.close();
    sort(v, v + n + 1);
    for (int i = 1; i <= n; ++i) {
      int ans = 0;
      for (int step = (1 << 3); step > 0; step >>= 1)
        if (ans + step < i && v[ans + step].b <= v[i].a)
          ans += step;
      dp[i] = max(dp[i - 1], dp[ans] + v[i].b - v[i].a);
    }
    ofstream fout("heavymetal.out");
    fout << dp[n];
    fout.close();
    return 0;
}