dp

[neal2018]

convex hull trick / slope trick

https://codeforces.com/contest/1715/submission/169121067

constexpr ll inf = LLONG_MAX;
struct line {
  static bool Q;
  mutable ll k, m, p;
  bool operator<(const line& o) const { return Q ? p < o.p : k < o.k; }
};
bool line::Q = false;
struct lines : multiset<line> {
  //(for doubles, use inf = 1/.0, div(a,b) = a/b)
  ll div(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
  bool isect(iterator x, iterator y) {
    if (y == end()) return x->p = inf, false;
    if (x->k == y->k) {
      x->p = x->m > y->m ? inf : -inf;
    } else {
      x->p = div(y->m - x->m, x->k - y->k);
    }
    return x->p >= y->p;
  }
  void add(ll k, ll m) {
    line::Q = false;
    auto z = insert({k, m, 0}), y = z++, x = y;
    while (isect(y, z)) z = erase(z);
    if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
    while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
  }
  ll query(ll x) {
    line::Q = true;
    auto l = lower_bound({0, 0, x});
    return l->k * x + l->m;
  }
};

[neal2018]

monotonic

function<void(int, int, int, int)> dfs = [&](int l, int r, int poss_l, int poss_r) {
  if (l >= r) return;
  int mid = (l + r) / 2;
  int best = poss_l;
  for (int i = poss_l; i < poss_r; i++) {
    ll cur = cost(mid, i);
    if (cur > dp[mid]) dp[mid] = cur, best = i;
  }
  dfs(l, mid, poss_l, best + 1);
  dfs(mid + 1, r, best, poss_r);
};
dfs(0, n, 0, n);