Submission #12025890


Source Code Expand

Copy
#include <bits/stdc++.h>
typedef long long int ll;
#define rep(i, a) for (ll i = 0; i < (a); i++)
 
using namespace std;

// {{{ Li Chao Tree
// 順番の関係ない Convex hull Trickの実装
// 直線追加と最小値計算がどちらも O(long N)
// Nはxの取りうる座標
struct LiChaoTree {
  const ll INF = ((ll)1) << 62;

  ll f(std::pair<ll, ll> line, ll x) {
    return line.first * x + line.second;
  }

  std::vector< ll > xs;
  std::vector< std::pair<ll, ll> > seg;
  ll N;

  explicit LiChaoTree(const std::vector< ll > &x) : xs(x) {
    N = 1;
    while (N < xs.size())
      N *= 2;
    while (xs.size() < N)
      xs.push_back(xs.back() + 1);
    seg.assign(2 * N - 1, std::pair<ll, ll>(0, INF));
  }

  void add_line(std::pair<ll, ll> line, int k, int l, int r) {
    ll m = (l + r) / 2;
    bool left = f(line, xs[l]) < f(seg[k], xs[l]);
    bool mid = f(line, xs[m]) < f(seg[k], xs[m]);

    if (mid)
      swap(seg[k], line);

    if (l + 1 >= r)
      return;
    else if (left != mid)
      add_line(line, 2 * k + 1, l, m);
    else
      add_line(line, 2 * k + 2, m, r);
  }

  void add_line(ll a, ll b) {
    add_line({a, b}, 0, 0, N);
  }

  // xの値、ただしxはコンストラクタに含まれていなければならない
  ll get_min(ll x) {
    ll k = lower_bound(begin(xs), end(xs), x) - begin(xs);
    k += N - 1;
    ll res = f(seg[k], x);
    while (k > 0) {
      k = (k - 1) / 2;
      res = std::min(res, f(seg[k], x));
    }
    return res;
  }
};
// }}}

ll N, C;
vector<ll> h;
ll dp[300000];

signed main() {
  cin >> N >> C;
  h.resize(N);
  rep(i, N) {
    cin >> h[i];
  }

  LiChaoTree lct(h);
  dp[0] = 0;
  lct.add_line(-2 * h[0], dp[0] + h[0] * h[0]);
  for (int i=1; i<N; i++) {
    dp[i] = lct.get_min(h[i]) + h[i] * h[i] + C;
    lct.add_line(-2 * h[i], dp[i] + h[i] * h[i]);
  }
  cout << dp[N-1] << endl;

  return 0;
}

Submission Info

Submission Time
Task Z - Frog 3
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1974 Byte
Status
Exec Time 112 ms
Memory 14692 KB

Judge Result

Set Name Score / Max Score Test Cases
All 100 / 100 0_00, 0_01, 0_02, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20, 1_21, 1_22, 1_23, 1_24, 1_25, 1_26, 1_27, 1_28, 1_29, 1_30, 1_31, 1_32, 1_33, 1_34, 1_35
Case Name Status Exec Time Memory
0_00 1 ms 256 KB
0_01 1 ms 256 KB
0_02 1 ms 256 KB
1_00 1 ms 256 KB
1_01 1 ms 256 KB
1_02 110 ms 14436 KB
1_03 112 ms 14180 KB
1_04 108 ms 14180 KB
1_05 110 ms 14308 KB
1_06 108 ms 14308 KB
1_07 105 ms 13684 KB
1_08 105 ms 13688 KB
1_09 108 ms 13936 KB
1_10 105 ms 13696 KB
1_11 105 ms 14080 KB
1_12 105 ms 13468 KB
1_13 107 ms 13672 KB
1_14 106 ms 13816 KB
1_15 107 ms 13676 KB
1_16 105 ms 13552 KB
1_17 104 ms 14692 KB
1_18 105 ms 13560 KB
1_19 107 ms 13560 KB
1_20 103 ms 14336 KB
1_21 102 ms 14436 KB
1_22 102 ms 13932 KB
1_23 101 ms 14064 KB
1_24 105 ms 14324 KB
1_25 103 ms 14312 KB
1_26 101 ms 14356 KB
1_27 106 ms 13552 KB
1_28 104 ms 13552 KB
1_29 104 ms 13804 KB
1_30 105 ms 14460 KB
1_31 104 ms 13576 KB
1_32 104 ms 13800 KB
1_33 106 ms 14052 KB
1_34 106 ms 13580 KB
1_35 107 ms 13556 KB