matsutaku-library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub MatsuTaku/matsutaku-library

:warning: test/atcoder/tenka1-2016-final-open-e.cpp

Code

#define PROBLEM "https://atcoder.jp/contests/tenka1-2016-final-open/tasks/tenka1_2016_final_e"
#define IGNORE
#include "include/mtl/convex_hull_trick.hpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n,l; cin>>n>>l;
  vector<vector<int>> A(n, vector<int>(l));
  vector<long long> dp(l);
  // Cost of skewer at offset k by position j
  // = (j-k)^2 + A[i][k]
  // = j^2 - 2jk + k^2 + A[i][k]
  for (int i = 0; i < n; i++) {
    ConvexHullTrick<long long, greater<>> cht;
    for (int j = 0; j < l; j++) {
      cin>>A[i][j];
      cht.add(-2*j, j*j + A[i][j]);
    }
    for (int j = l-1; j >= 0; j--)
      dp[j] += cht.get(j) + j*j;
  }
  long long ans = *min_element(dp.begin(), dp.end());
  cout << ans << endl;
}
#line 1 "test/atcoder/tenka1-2016-final-open-e.cpp"
#define PROBLEM "https://atcoder.jp/contests/tenka1-2016-final-open/tasks/tenka1_2016_final_e"
#define IGNORE
#line 2 "include/mtl/convex_hull_trick.hpp"
#include <utility>
#include <cassert>
#include <tuple>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <limits>
#line 3 "include/mtl/search.hpp"
#include <type_traits>
#include <functional>
#include <cmath>
#line 8 "include/mtl/search.hpp"

constexpr double EPS_DEFAULT = 1e-9;

template<typename I, typename F>
typename std::remove_reference<I>::type
bisect_int(I ok, I ng, F f) {
  while (std::abs(ng - ok) > 1) {
    auto c = ok + (ng - ok) / 2;
    if (f(c))
      ok = c;
    else
      ng = c;
  }
  return ok;
}

template<typename F>
double
bisect_float(double ok, double ng, F fn, double eps = EPS_DEFAULT) {
  while (std::abs(ok - ng) > eps) {
    double c = ok + (ng - ok) / 2;
    if (fn(c))
      ok = c;
    else
      ng = c;
  }
  return ok;
}

template<class Cmp = std::less<>>
class FibonacciSearch {
 public:
  using idx_type = long long;
 private:
  std::vector<long long> fib_;
  Cmp cmp_;
  void setup_fib(long long max_distance) {
    while (fib_.back() < max_distance) fib_.push_back(fib_[fib_.size()-2] + fib_[fib_.size()-1]);
  }
 public:
  FibonacciSearch(long long max_distance = 1, const Cmp& cmp = Cmp()) : fib_{1,1}, cmp_(cmp) {
    setup_fib(max_distance);
  }

  template<class F>
  auto operator()(idx_type l, idx_type r, F fn) const 
    -> std::pair<idx_type, decltype(fn(l))> 
  {
    assert(r - l >= 2);
    idx_type d = r-l;
    setup_fib(d);
    auto k = --fib_.cend();
    idx_type il = l + *(k-2);
    idx_type ir = l + *(k-1);
    auto lv = fn(il);
    auto rv = fn(ir);
    auto ret = cmp(lv, rv) ? std::make_pair((idx_type)ir, rv) : std::make_pair((idx_type)il, lv);
    while (*k > 3) {
      if (cmp(lv, rv)) {
        l += *(k-2);
        lv = rv;
        auto i = std::min(r-1, l + *(k-2));
        rv = fn(i);
        if (cmp(ret.second, rv))
          ret = std::make_pair(i, rv);
      } else {
        rv = lv;
        auto i = std::min(r-1, l + *(k-3));
        lv = fn(i);
        if (cmp(ret.second, lv))
          ret = std::make_pair(i, lv);
      }
      --k;
    }
    return ret;
  }
};

template<typename I, typename F, typename C = std::less<>>
auto fibonacci_search(I l, I r, F fn, const C& cmp = C()) 
  -> std::pair<typename std::remove_reference<I>::type,
               decltype(fn(l))> {
  return FibonacciSearch<C>(r - l, cmp)(l, r, fn);
}
template<typename I, typename F, typename C = std::less<>>
auto trisect_int(I l, I r, F fn, const C& cmp = C())
  -> std::pair<typename std::remove_reference<I>::type, 
               decltype(fn(l))> {
  return fibonacci_search(l, r, fn, cmp);
}

constexpr double GOLDEN_RATIO = 1.61803398875;
template<typename F, typename C = std::less<>>
auto golden_ratio_search(double l, double r, F fn, double eps = EPS_DEFAULT, const C& cmp = C())
  -> std::pair<double, decltype(fn(l))> {
  using value_type = decltype(fn(l));
  std::pair<double, value_type> ret;
  while (std::abs(r - l) > eps) {
    double il = (l * GOLDEN_RATIO + r) / (GOLDEN_RATIO + 1.);
    double ir = (l + r * GOLDEN_RATIO) / (GOLDEN_RATIO + 1.);
    auto vl = fn(il);
    auto vr = fn(ir);
    if (cmp(vr, vl)) {
      ret = std::make_pair(il, vl);
      r = ir;
    } else {
      ret = std::make_pair(ir, vr);
      l = il;
    }
  }
  return ret;
}
template<typename F, typename C = std::less<>>
auto trisect_float(double l, double r, F fn, double eps = EPS_DEFAULT, const C& cmp = C())
  -> std::pair<double, decltype(fn(l))> {
  return golden_ratio_search(l, r, fn, eps, cmp);
}
#line 14 "include/mtl/convex_hull_trick.hpp"

template<typename T, typename C = std::less<T>>
struct ConvexHullTrickDeque {
  std::deque<std::pair<T, T>> L;
  C cmp;
  ConvexHullTrickDeque() = default;

 private:
  template<typename U, typename V, typename W>
  bool intersect_less(const U& g, const V& h, const W& i) {
    assert(g.first != h.first and h.first != i.first);
    // x0 = (d-b)/(a-c)
    // x1 = (f-d)/(c-e)
    // x0 < x1 <=> (d-b)/(a-c) < (f-d)/(c-e)
    //         <=> (d-b)(c-e) < (f-d)(a-c)
    return (h.second-g.second)*(h.first-i.first) <
        (i.second-h.second)*(g.first-h.first);
  }

 public:
  void clear() {
    L.clear();
  }
  void push_back(T a, T b) {
    assert(L.empty() or cmp(L.back().first, a));
    auto l = std::make_pair(a, b);
    while (L.size() >= 2 and !intersect_less(L[L.size()-2], L[L.size()-1], l))
      L.pop_back();
    L.push_back(l);
  }
  void push_front(T a, T b) {
    assert(L.empty() or cmp(a, L.front().first));
    auto l = std::make_pair(a, b);
    while (L.size() >= 2 and !intersect_less(l, L[0], L[1]))
      L.pop_front();
    L.push_front(l);
  }

  T get(T x) const {
    auto i = bisect_int(-1, (int)L.size()-1, [&](int c) {
      if (c == -1) return true;
      auto yl = L[c].first * x + L[c].second;
      auto yr = L[c+1].first * x + L[c+1].second;
      return cmp(yl, yr);
    });
    int r = i+1;
    return L[r].first * x + L[r].second;
  }

  T get_incremental(T x) {
    assert(!L.empty());
    T ret = L[0].first * x + L[0].second;
    while (L.size() >= 2 and cmp(ret, L[1].first * x + L[1].second)) {
      ret = L[1].first * x + L[1].second;
      L.pop_front();
    }
    return ret;
  }

  T get_decremental(T x) {
    assert(!L.empty());
    T ret = L.back().first * x + L.back().second;
    while (L.size() >= 2 and cmp(ret, L[L.size()-2].first * x + L[L.size()-2].second)) {
      ret = L[L.size()-2].first * x + L[L.size()-2].second;
      L.pop_back();
    }
    return ret;
  }
};


template<typename T, typename C = std::less<T>>
struct ConvexHullTrick {
  using Line = std::pair<T, T>;
  struct Node;
  std::map<Node, Line> tr;
  std::map<T, T, C> L;
  C cmp;
  static constexpr T INF = std::numeric_limits<T>::max();
  static constexpr T MINF = std::numeric_limits<T>::min();
  static constexpr T AX_LO = C()(MINF, INF) ? MINF : INF;
  static constexpr T AX_HI = C()(MINF, INF) ? INF : MINF;
  ConvexHullTrick() {
    Line lo = {AX_LO, 0};
    Line hi = {AX_HI, 0};
    tr.emplace(Node(lo, hi), lo);
    L.insert(lo);
    L.emplace_hint(L.end(), hi);
  }

  struct Node {
    T u,v; // a-c, d-b
    Node() = default;
    Node(T _u, T _v) : u(_u), v(_v) {}
    explicit Node(const Line& f, const Line& g) {
      if (f.first == AX_LO) {
        u = 0, v = MINF;
      } else if (g.first == AX_HI) {
        u = 0, v = INF;
      } else {
        u = f.first - g.first, v = g.second - f.second;
        if (u < 0) {
          u = -u;
          v = -v;
        }
      }
    }
    inline bool operator==(const Node& rhs) const {
      return u == rhs.u and v == rhs.v;
    }
    inline bool operator<(const Node& rhs) const {
      if (v == INF or rhs.v == MINF)
        return false;
      if (v == MINF or rhs.v == INF)
        return true;
      // x0 = (d-b)/(a-c)
      // x1 = (f-d)/(c-e)
      // x0 < x1 <=> (d-b)/(a-c) < (f-d)/(c-e)
      //         <=> (d-b)(c-e) < (f-d)(a-c)
      assert((double)MINF < (double) v*rhs.u and (double) v*rhs.u < (double)INF);
      assert((double)MINF < (double) rhs.v * u and (double) rhs.v * u < (double)INF);
      return v * rhs.u < rhs.v * u;
    }
  };

 private:
  template<typename U, typename V, typename W>
  bool intersect_less(const U& g, const V& h, const W& i) {
    if (g.first == h.first)
      return cmp(g.second, h.second);
    if (h.first == i.first)
      return cmp(i.second, h.second);
    if (g.first == AX_LO or i.first == AX_HI)
      return true;
    // x0 = (d-b)/(a-c)
    // x1 = (f-d)/(c-e)
    // x0 < x1 <=> (d-b)/(a-c) < (f-d)/(c-e)
    //         <=> (d-b)(c-e) < (f-d)(a-c)
    auto s = (g.first-h.first), t = (h.second-g.second);
    auto u = (h.first-i.first), v = (i.second-h.second);
    assert((double)MINF < (double)t*u and (double)t*u < (double)INF);
    assert((double)MINF < (double)t*u and (double)v*s < (double)INF);
    return t * u < v * s;
  }

 public:
  void add(T a, T b) {
    Line line{a,b};
    auto it = L.lower_bound(a);
    assert(it != L.begin());
    assert(it != L.end());
    using std::prev;
    using std::next;
    auto lit = prev(it);
    if (it->first == a) {
      if (!cmp(it->second, b))
        return;
      lit = it++;
    } else if (!intersect_less(*lit, line, *it)) {
      return;
    }
    auto tit = tr.find(Node(*lit, *it));
    assert(tit != tr.end());
    auto teit = next(tit);
    while (lit != L.begin() and !intersect_less(*prev(lit), *lit, line)) {
      --tit;
      --lit;
    }
    while (next(it) != L.end() and !intersect_less(line, *it, *next(it))) {
      ++teit;
      ++it;
    }
    tit = tr.erase(tit, teit);
    it = L.erase(next(lit), it);
    assert(tit == tr.end() or Node(line,*it) < tit->first);
    tit = tr.emplace_hint(tit, Node(line, *it), line);
    assert(tit != tr.end() and Node(*lit,line) < tit->first);
    tr.emplace_hint(tit, Node(*lit, line), *lit);
    L.emplace_hint(it, line);
  }

 private:
  inline T f(const Line& l, T x) const {
    return l.first * x + l.second;
  }

 public:
  T get(T x) const {
    auto it = tr.lower_bound(Node(1,x));
    assert(it != tr.end());
    return f(it->second, x);
  }

  T get_incremental(T x) {
    auto ts = tr.begin();
    auto te = ts;
    auto s = next(L.begin());
    auto e = s;
    auto ne = next(e);
    auto le = prev(L.end());
    while (ne != le and cmp(f(*e, x), f(*ne, x))) {
      ++te;
      e = ne++;
    }
    if (ts != te) {
      ++te;
      ts = tr.erase(ts, te);
      s = L.erase(s, e);
      tr.emplace_hint(ts, Node(*prev(s), *s), *prev(s));
    }
    return f(*s, x);
  }

  T get_decremental(T x) {
    auto ts = tr.end();
    auto te = ts;
    auto s = prev(prev(L.end()));
    auto ps = prev(s);
    auto e = s;
    while (ps != L.begin() and cmp(f(*s, x), f(*ps, x))) {
      --ts;
      s = ps--;
    }
    if (ts != te) {
      --ts;
      ts = tr.erase(ts, te);
      L.erase(next(s), next(e));
      tr.emplace_hint(ts, Node(*s, *next(s)), *s);
    }
    return f(*s, x);
  }
};
#line 4 "test/atcoder/tenka1-2016-final-open-e.cpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n,l; cin>>n>>l;
  vector<vector<int>> A(n, vector<int>(l));
  vector<long long> dp(l);
  // Cost of skewer at offset k by position j
  // = (j-k)^2 + A[i][k]
  // = j^2 - 2jk + k^2 + A[i][k]
  for (int i = 0; i < n; i++) {
    ConvexHullTrick<long long, greater<>> cht;
    for (int j = 0; j < l; j++) {
      cin>>A[i][j];
      cht.add(-2*j, j*j + A[i][j]);
    }
    for (int j = l-1; j >= 0; j--)
      dp[j] += cht.get(j) + j*j;
  }
  long long ans = *min_element(dp.begin(), dp.end());
  cout << ans << endl;
}
Back to top page