提出 #33645641

---

ソースコード 拡げる

#include <bits/stdc++.h>

using num = int64_t;
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

#define INF 0x3f3f3f3f3f3f3f3f

class LiChao {
	vector<ll> m, b;
	int n, sz; ll *x;
#define gx(i) (i < sz ? x[i] : x[sz-1])
	void update(int t, int l, int r, ll nm, ll nb) {
		ll xl = nm * gx(l) + nb, xr = nm * gx(r) + nb;
		ll yl = m[t] * gx(l) + b[t], yr = m[t] * gx(r) + b[t];
        if (yl >= xl && yr >= xr) return;
		if (yl <= xl && yr <= xr) {
			m[t] = nm, b[t] = nb; return;
		}
		int mid = (l + r) / 2;
		update(t<<1, l, mid, nm, nb);
		update(1+(t<<1), mid+1, r, nm, nb);
	}
public:
	LiChao(ll *st, ll *en) : x(st) {
		sz = int(en - st);
		for(n = 1; n < sz; n <<= 1);
		m.assign(2*n, 0); b.assign(2*n, -INF);
	}
	void insert_line(ll nm, ll nb) {
		update(1, 0, n-1, nm, nb);
	}
	ll query(int i) {
		ll ans = -INF;
		for(int t = i+n; t; t >>= 1)
			ans = max(ans, m[t] * x[i] + b[t]);
		return ans;
	}
};

ll xs[1000000];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

    ll N, C;
    cin >> N >> C;
    rep(i, 1, 1000001) xs[i-1] = i;
    LiChao chtTree(xs, xs+1000000);

    ll minCost = 0;
    rep(i, 0, N) {
        ll newLocation;
        cin >> newLocation;
        if (i > 0) {
            minCost = -chtTree.query(newLocation-1)+newLocation*newLocation;
        }
        chtTree.insert_line(2*newLocation, -(minCost+newLocation*newLocation+C));
    }
    cout << minCost << "\n";
}

提出情報

ジャッジ結果