Contest Duration: ~ (local time) (300 minutes)

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) {
}

// 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 2020-04-18 12:18:15+0900 Z - Frog 3 bobuhiro11 C++14 (GCC 5.4.1) 100 1974 Byte AC 112 ms 14692 KB

#### Judge Result

Set Name All
Score / Max Score 100 / 100
Status
 AC × 39
Set Name Test Cases
All 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