#398153 (C++14) No.703 ゴミ拾い Easy

提出ソース

結果

問題	No.703 ゴミ拾い Easy
ユーザー	fine
提出日時	2019-11-15 02:11:12
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	134 ms / 1,500 ms
コード長	3,059 bytes
コンパイル時間	2,276 ms
コンパイル使用メモリ	179,960 KB
実行使用メモリ	21,168 KB
最終ジャッジ日時	2023-08-30 19:13:00
合計ジャッジ時間	7,076 ms
ジャッジサーバーID （参考情報）	judge15 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	AC	2 ms 4,384 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	1 ms 4,376 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	1 ms 4,380 KB
testcase_09	AC	1 ms 4,376 KB
testcase_10	AC	2 ms 4,376 KB
testcase_11	AC	2 ms 4,384 KB
testcase_12	AC	2 ms 4,376 KB
testcase_13	AC	2 ms 4,376 KB
testcase_14	AC	2 ms 4,500 KB
testcase_15	AC	2 ms 4,376 KB
testcase_16	AC	2 ms 4,376 KB
testcase_17	AC	2 ms 4,376 KB
testcase_18	AC	2 ms 4,380 KB
testcase_19	AC	2 ms 4,376 KB
testcase_20	AC	2 ms 4,380 KB
testcase_21	AC	2 ms 4,376 KB
testcase_22	AC	2 ms 4,380 KB
testcase_23	AC	2 ms 4,380 KB
testcase_24	AC	132 ms 20,532 KB
testcase_25	AC	133 ms 20,788 KB
testcase_26	AC	131 ms 20,436 KB
testcase_27	AC	134 ms 19,864 KB
testcase_28	AC	132 ms 20,332 KB
testcase_29	AC	132 ms 20,648 KB
testcase_30	AC	132 ms 20,384 KB
testcase_31	AC	134 ms 20,688 KB
testcase_32	AC	134 ms 21,168 KB
testcase_33	AC	132 ms 20,508 KB
testcase_34	AC	95 ms 15,744 KB
testcase_35	AC	93 ms 14,868 KB
testcase_36	AC	93 ms 15,640 KB
testcase_37	AC	94 ms 14,988 KB
testcase_38	AC	93 ms 15,392 KB
testcase_39	AC	93 ms 15,080 KB
testcase_40	AC	95 ms 15,536 KB
testcase_41	AC	94 ms 16,608 KB
testcase_42	AC	94 ms 14,972 KB
testcase_43	AC	92 ms 15,148 KB
testcase_44	AC	2 ms 4,376 KB
testcase_45	AC	1 ms 4,376 KB
testcase_46	AC	106 ms 14,740 KB
testcase_47	AC	105 ms 15,024 KB
testcase_48	AC	2 ms 4,380 KB
testcase_49	AC	2 ms 4,380 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// https://lumakernel.github.io/ecasdqina/dynamic-programming/convex-hull-trick/LiChaoTree
// 最小化: Comp = less<T>, 最大化: Comp = greater<T>
template<class T = ll, class Comp = less<T> >
struct LiChaoTree {
	using Line = pair<T, T>;
	static inline T f(const Line& line, T x) { return line.first * x + line.second; }

	static Comp comp;

	int n;
	vector<Line> data;
	vector<int> used;
	vector<T> xs;

private:
	// [l, r)
	void add(int l, int r, const Line& line) {
		int l0 = l, r0 = r;
		int sz = 1;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1, sz <<= 1) {
			if (l & 1) add(l, l0, l0 + sz, line), l0 += sz, ++l;
			if (r & 1) --r, r0 -= sz, add(r, r0, r0 + sz, line);
		}
	}

	void add(int k, int l, int r, Line line) {
		if (!used[k]) {
			used[k] = true;
			data[k] = line;
			return;
		}

		T cur_ly = f(data[k], xs[l]), cur_ry = f(data[k], xs[r - 1]);
		T nex_ly = f(line, xs[l]), nex_ry = f(line, xs[r - 1]);

		if (comp(cur_ly, nex_ly) && comp(cur_ry, nex_ry)) return;
		if (comp(nex_ly, cur_ly) && comp(nex_ry, cur_ry)) {
			data[k] = line;
			return;
		}

		if (r - l == 1) return;

		int m = (l + r) >> 1;
		if (comp(cur_ly, nex_ly)) swap(data[k], line);
		if (comp(f(line, xs[m]), f(data[k], xs[m]))) {
			swap(data[k], line);
			add((k << 1) | 1, m, r, line);
		} else {
			add(k << 1, l, m, line);
		}
	}

public:
	// 前処理（事前にクエリのx座標を渡す必要あり）
	void addx(T x) { xs.emplace_back(x); }
	void prebuild() {
		sort(xs.begin(), xs.end());
		xs.erase(unique(xs.begin(), xs.end()), xs.end());

		int sz = xs.size();
		n = 1;
		while (n < sz) n <<= 1;
		xs.resize(n, xs.back());

		data.resize(n << 1);
		used.resize(n << 1);
	}

	// 直線追加: ax + b
	void add(T a, T b) { add(0, n, Line(a, b)); }

	// 線分追加: ax + b (l <= x <= r)
	void add(T a, T b, T l, T r) {
		int li = lower_bound(xs.begin(), xs.end(), l) - xs.begin();
		int ri = upper_bound(xs.begin(), xs.end(), r) - xs.begin();
		add(li, ri, Line(a, b));
	}

	// ax+bが最小/最大となる(a,b)を取得
	Line get(T x) {
		int idx = -1;
		for (int i = lower_bound(xs.begin(), xs.end(), x) - xs.begin() + n; i > 0; i >>= 1) {
			if (!used[i]) continue;
			if (idx == -1 || comp(f(data[i], x), f(data[idx], x))) idx = i;
		}
		assert(idx > 0 && idx < (n << 1));
		return data[idx];
	}

	// ax+bの最小/最大値を取得
	T query(T x) { return f(get(x), x); }
};

template<class T, class Comp>
Comp LiChaoTree<T, Comp>::comp;

constexpr ll INF = 1e18;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<ll> a(n), x(n), y(n);

	LiChaoTree<> lct;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		lct.addx(a[i]);
	}
	lct.prebuild();

	for (int i = 0; i < n; i++) cin >> x[i];
	for (int i = 0; i < n; i++) cin >> y[i];

	vector<ll> dp(n + 1, INF);
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		lct.add(-2 * x[i], x[i] * x[i] + y[i] * y[i] + dp[i]);
		dp[i + 1] = lct.query(a[i]) + a[i] * a[i];
	}
	cout << dp[n] << "\n";
	return 0;
}

yukicoder

結果

テストケース

ソースコード