提出 #24563891

---

ソースコード 拡げる

#line 1 "runtime/include/jikka/base.hpp"


#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#include <numeric>
#include <unordered_map>
#include <vector>

namespace jikka {

inline int64_t floordiv(int64_t n, int64_t d) {
  assert(d != 0);
  return n / d - ((n ^ d) < 0 && n % d);
}

inline int64_t floormod(int64_t n, int64_t d) {
  assert(d != 0);
  n %= d;
  return (n < 0 ? n + d : n);
}

inline int64_t ceildiv(int64_t n, int64_t d) {
  assert(d != 0);
  return n / d + ((n ^ d) >= 0 && n % d);
}

inline int64_t ceilmod(int64_t n, int64_t d) {
  assert(d != 0);
  return n - ceildiv(n, d) * d;
}

inline int64_t pow(int64_t x, int64_t k) {
  assert(k >= 0);
  int64_t y = 1;
  for (; k > 0; k >>= 1) {
    if (k & 1) {
      y *= x;
    }
    x *= x;
  }
  return y;
}

template <typename T, size_t H, size_t W>
using matrix = std::array<std::array<T, W>, H>;

template <size_t H, size_t W>
std::array<int64_t, H> matap(const matrix<int64_t, H, W> &a,
                             const std::array<int64_t, W> &b) {
  std::array<int64_t, H> c = {};
  for (size_t y = 0; y < H; ++y) {
    for (size_t x = 0; x < W; ++x) {
      c[y] += a[y][x] * b[x];
    }
  }
  return c;
}

template <size_t N> matrix<int64_t, N, N> matzero() { return {}; }

template <size_t N> matrix<int64_t, N, N> matone() {
  matrix<int64_t, N, N> a = {};
  for (size_t i = 0; i < N; ++i) {
    a[i][i] = 1;
  }
  return a;
}

template <size_t H, size_t W>
matrix<int64_t, H, W> matadd(const matrix<int64_t, H, W> &a,
                             const matrix<int64_t, H, W> &b) {
  matrix<int64_t, H, W> c;
  for (size_t y = 0; y < H; ++y) {
    for (size_t x = 0; x < W; ++x) {
      c[y][x] = a[y][x] + b[y][x];
    }
  }
  return c;
}

template <size_t H, size_t N, size_t W>
matrix<int64_t, H, W> matmul(const matrix<int64_t, H, N> &a,
                             const matrix<int64_t, N, W> &b) {
  matrix<int64_t, H, W> c = {};
  for (size_t y = 0; y < H; ++y) {
    for (size_t z = 0; z < N; ++z) {
      for (size_t x = 0; x < W; ++x) {
        c[y][x] += a[y][z] * b[z][x];
      }
    }
  }
  return c;
}

template <size_t N>
matrix<int64_t, N, N> matpow(matrix<int64_t, N, N> x, int64_t k) {
  matrix<int64_t, N, N> y = matone<N>();
  for (; k; k >>= 1) {
    if (k & 1) {
      y = matmul(y, x);
    }
    x = matmul(x, x);
  }
  return y;
}

inline int64_t modnegate(int64_t a, int64_t MOD) { return floormod(-a, MOD); }

inline int64_t modplus(int64_t a, int64_t b, int64_t MOD) {
  return floormod(a + b, MOD);
}

inline int64_t modminus(int64_t a, int64_t b, int64_t MOD) {
  return floormod(a - b, MOD);
}

inline int64_t modmult(int64_t a, int64_t b, int64_t MOD) {
  return floormod(a * b, MOD);
}

inline int64_t modinv(int64_t value, int64_t MOD) {
  assert(0 < value and value < MOD);
  int64_t a = value, b = MOD;
  int64_t x = 0, y = 1;
  for (int64_t u = 1, v = 0; a;) {
    int64_t q = b / a;
    x -= q * u;
    std::swap(x, u);
    y -= q * v;
    std::swap(y, v);
    b -= q * a;
    std::swap(b, a);
  }
  assert(value * x + MOD * y == b and b == 1);
  if (x < 0) {
    x += MOD;
  }
  assert(0 <= x and x < MOD);
  return x;
}

inline int64_t modpow(int64_t x, int64_t k, int64_t MOD) {
  assert(k >= 0);
  int64_t y = 1;
  for (; k > 0; k >>= 1) {
    if (k & 1) {
      y = y * x % MOD;
    }
    x = x * x % MOD;
  }
  if (y < 0) {
    y += MOD;
  }
  return y;
}

template <size_t H, size_t W>
std::array<int64_t, H> modmatap(const matrix<int64_t, H, W> &a,
                                const std::array<int64_t, W> &b, int64_t MOD) {
  std::array<int64_t, H> c = {};
  for (size_t y = 0; y < H; ++y) {
    for (size_t x = 0; x < W; ++x) {
      c[y] += a[y][x] * b[x] % MOD;
    }
    c[y] = floormod(c[y], MOD);
  }
  return c;
}

template <size_t H, size_t W>
matrix<int64_t, H, W> modmatadd(const matrix<int64_t, H, W> &a,
                                const matrix<int64_t, H, W> &b, int64_t MOD) {
  matrix<int64_t, H, W> c;
  for (size_t y = 0; y < H; ++y) {
    for (size_t x = 0; x < W; ++x) {
      c[y][x] = floormod(a[y][x] + b[y][x], MOD);
    }
  }
  return c;
}

template <size_t H, size_t N, size_t W>
matrix<int64_t, H, W> modmatmul(const matrix<int64_t, H, N> &a,
                                const matrix<int64_t, N, W> &b, int64_t MOD) {
  matrix<int64_t, H, W> c = {};
  for (size_t y = 0; y < H; ++y) {
    for (size_t z = 0; z < N; ++z) {
      for (size_t x = 0; x < W; ++x) {
        c[y][x] += a[y][z] * b[z][x] % MOD;
      }
    }
  }
  for (size_t y = 0; y < H; ++y) {
    for (size_t x = 0; x < W; ++x) {
      c[y][x] = floormod(c[y][x], MOD);
    }
  }
  return c;
}

template <size_t N>
matrix<int64_t, N, N> modmatpow(matrix<int64_t, N, N> x, int64_t k,
                                int64_t MOD) {
  matrix<int64_t, N, N> y = matone<N>();
  for (; k; k >>= 1) {
    if (k & 1) {
      y = modmatmul(y, x, MOD);
    }
    x = modmatmul(x, x, MOD);
  }
  return y;
}

inline std::vector<int64_t> range(int64_t n) {
  if (n < 0) {
    return std::vector<int64_t>();
  }
  std::vector<int64_t> xs(n);
  std::iota(xs.begin(), xs.end(), 0);
  return xs;
}

inline int64_t fact(int64_t n) {
  assert(0 <= n);
  int64_t ans = 1;
  for (int i = 0; i < n; ++i) {
    ans *= i + 1;
  }
  return ans;
}

inline int64_t choose(int64_t n, int64_t r) {
  assert(0 <= r and r <= n);
  int64_t ans = 1;
  for (int i = 0; i < r; ++i) {
    ans *= n - i;
    ans /= i + 1;
  }
  return ans;
}

inline int64_t permute(int64_t n, int64_t r) {
  assert(0 <= r and r <= n);
  int64_t ans = 1;
  for (int i = 0; i < r; ++i) {
    ans *= n - i;
  }
  return ans;
}

inline int64_t multichoose(int64_t n, int64_t r) {
  assert(0 <= r and r <= n);
  if (n == 0 and r == 0) {
    return 1;
  }
  return choose(n + r - 1, r);
}

inline int64_t modfact(int64_t n, int64_t MOD) {
  assert(0 <= n);
  assert(1 <= MOD);
  static std::unordered_map<int64_t, std::vector<int64_t>> memos;
  auto &memo = memos[MOD];
  while (static_cast<int64_t>(memo.size()) <= n) {
    if (memo.empty()) {
      memo.push_back(1);
    }
    memo.push_back(memo.size() * memo.back() % MOD);
  }
  return memo[n];
}

inline int64_t modchoose(int64_t n, int64_t r, int64_t MOD) {
  assert(0 <= r and r <= n);
  assert(1 <= MOD);
  return modfact(n, MOD) * modinv(modfact(r, MOD), MOD) % MOD;
}

inline int64_t modpermute(int64_t n, int64_t r, int64_t MOD) {
  assert(0 <= r and r <= n);
  assert(1 <= MOD);
  return modfact(n, MOD) *
         modinv(modfact(n - r, MOD) * modfact(r, MOD) % MOD, MOD) % MOD;
}

inline int64_t modmultichoose(int64_t n, int64_t r, int64_t MOD) {
  assert(0 <= r and r <= n);
  assert(1 <= MOD);
  if (n == 0 and r == 0) {
    return 1;
  }
  return modchoose(n + r - 1, r, MOD);
}

template <class T> inline T error(const std::string &message) {
  std::cerr << message << std::endl;
  assert(false);
}

} // namespace jikka


#line 1 "runtime/include/jikka/convex_hull_trick.hpp"


#line 4 "runtime/include/jikka/convex_hull_trick.hpp"
#include <climits>
#line 6 "runtime/include/jikka/convex_hull_trick.hpp"
#include <map>
#include <set>
#include <utility>

namespace jikka {

namespace details {
/**
 * @note y = ax + b
 */
struct line_t {
  int64_t a, b;
};
bool operator<(line_t lhs, line_t rhs) {
  return std::make_pair(-lhs.a, lhs.b) < std::make_pair(-rhs.a, rhs.b);
}

struct rational_t {
  int64_t num, den;
};
bool operator<(rational_t lhs, rational_t rhs) {
  if (lhs.num == INT64_MAX or rhs.num == -INT64_MAX)
    return false;
  if (lhs.num == -INT64_MAX or rhs.num == INT64_MAX)
    return true;
  return (__int128_t)lhs.num * rhs.den < (__int128_t)rhs.num * lhs.den;
}
} // namespace details

/*
 * @brief Convex Hull Trick (非単調, online)
 * @docs data_structure/convex_hull_trick.md
 */
class convex_hull_trick {
  typedef details::line_t line_t;
  typedef details::rational_t rational_t;
  static rational_t make_rational(int64_t num, int64_t den = 1) {
    if (den < 0) {
      num *= -1;
      den *= -1;
    }
    return {num, den}; // NOTE: no reduction
  }

public:
  convex_hull_trick() {
    lines.insert({+INT64_MAX, 0}); // sentinels
    lines.insert({-INT64_MAX, 0});
    cross.emplace(make_rational(-INT64_MAX), (line_t){-INT64_MAX, 0});
  }
  /**
   * @note O(log n)
   */
  void add_line(int64_t a, int64_t b) {
    auto it = lines.insert({a, b}).first;
    if (not is_required(*prev(it), {a, b}, *next(it))) {
      lines.erase(it);
      return;
    }
    cross.erase(cross_point(*prev(it), *next(it)));
    { // remove right lines
      auto ju = prev(it);
      while (ju != lines.begin() and not is_required(*prev(ju), *ju, {a, b}))
        --ju;
      cross_erase(ju, prev(it));
      it = lines.erase(++ju, it);
    }
    { // remove left lines
      auto ju = next(it);
      while (next(ju) != lines.end() and
             not is_required({a, b}, *ju, *next(ju)))
        ++ju;
      cross_erase(++it, ju);
      it = prev(lines.erase(it, ju));
    }
    cross.emplace(cross_point(*prev(it), *it), *it);
    cross.emplace(cross_point(*it, *next(it)), *next(it));
    assert(not empty());
  }
  bool empty() const { return lines.size() <= 2; }
  /**
   * @note O(log n)
   */
  int64_t get_min(int64_t x) const {
    assert(not empty());
    line_t f = prev(cross.lower_bound(make_rational(x)))->second;
    return f.a * x + f.b;
  }

private:
  std::set<line_t> lines;
  std::map<rational_t, line_t> cross;
  template <typename Iterator> void cross_erase(Iterator first, Iterator last) {
    for (; first != last; ++first) {
      cross.erase(cross_point(*first, *next(first)));
    }
  }
  rational_t cross_point(line_t f1, line_t f2) const {
    if (f1.a == INT64_MAX)
      return make_rational(-INT64_MAX);
    if (f2.a == -INT64_MAX)
      return make_rational(INT64_MAX);
    return make_rational(f1.b - f2.b, f2.a - f1.a);
  }
  bool is_required(line_t f1, line_t f2, line_t f3) const {
    if (f1.a == f2.a and f1.b <= f2.b)
      return false;
    if (f1.a == INT64_MAX or f3.a == -INT64_MAX)
      return true;
    return (__int128_t)(f2.a - f1.a) * (f3.b - f2.b) <
           (__int128_t)(f2.b - f1.b) * (f3.a - f2.a);
  }
};

} // namespace jikka


#line 9 "foo.cpp"
#include <string>
#include <tuple>
#line 12 "foo.cpp"
int64_t solve(int64_t n_0, int64_t c_1, std::vector<int64_t> h_2) {
  std::vector<int64_t> x3;
  x3.push_back(0);
  jikka::convex_hull_trick x4_10;
  for (int32_t x5 = 0; x5 < n_0 - 1; ++x5) {
    x4_10.add_line(h_2[x5], h_2[x5] * h_2[x5] + x3[x5]);
    x3.push_back(c_1 + h_2[(x5 + 1)] * h_2[(x5 + 1)] +
                 x4_10.get_min(h_2[(x5 + 1)] * -2));
  }
  return x3[(n_0 - 1)];
}
int main() {
  int64_t n_12 = -1;
  int64_t c_13 = -1;
  std::cin >> n_12;
  std::vector<int64_t> h_14(n_12, -1);
  std::cin >> c_13;
  for (int32_t i15 = 0; i15 < n_12; ++i15) {
    std::cin >> h_14[i15];
  }
  auto ans_16 = solve(n_12, c_13, h_14);
  std::cout << ans_16 << ' ';
  std::cout << '\n' << ' ';
}

提出情報

ジャッジ結果