結果

問題 No.703 ゴミ拾い Easy
ユーザー vjudge1
提出日時 2025-03-19 18:01:46
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 315 ms / 1,500 ms
コード長 1,871 bytes
コンパイル時間 3,551 ms
コンパイル使用メモリ 274,956 KB
実行使用メモリ 21,968 KB
最終ジャッジ日時 2025-03-19 18:01:59
合計ジャッジ時間 12,199 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
#define int long long
using ll = long long;
const double eps = 1e-7;
#define ls(i) (i << 1)
#define rs(i) (i << 1 | 1)
struct node {
	ll k, b;
	int flag;
	ll operator () (int x) {
		if (!flag) return LLONG_MAX;
		return k * x + b;
	}
	friend double cross(node x, node y) {
		return 1.0 * (x.b - y.b) / (y.k - x.k);
	}
} tree[N << 2];
void update(int i, int tl, int tr, int l, int r, node p) {
	if (l <= tl && tr <= r) {
		if (!tree[i].flag) {
			tree[i].k = p.k;
			tree[i].b = p.b;
			tree[i].flag = 1;
			return;
		}
		if (p(tl) - tree[i](tl) < 0 && p(tr) - tree[i](tr) < 0)
			tree[i].k = p.k, tree[i].b = p.b;
		else if (p(tl) - tree[i](tl) < 0 || p(tr) - tree[i](tr) < 0) {
			int tm = tl + tr >> 1;
			if (p(tm) - tree[i](tm) < 0) 
				swap(tree[i].k, p.k), swap(tree[i].b, p.b);
			if (cross(p, tree[i]) - tm < eps)
				update(ls(i), tl, tm, l, r, p);
			else
				update(rs(i), tm + 1, tr, l, r, p);
		}
	}
	else {
		int tm = tl + tr >> 1;
		if (l <= tm)
			update(ls(i), tl, tm, l, r, p);
		if (r > tm)
			update(rs(i), tm + 1, tr, l, r, p);
	}
}
ll query(int i, int tl, int tr, int pos) {
	if (tl == tr) return tree[i](pos);
	int tm = tl + tr >> 1;
	ll ans = tree[i](pos);
	if (pos <= tm)
		return min(ans, query(ls(i), tl, tm, pos));
	else
		return min(ans, query(rs(i), tm + 1, tr, pos));
}
ll a[N * 3], x[N * 3], y[N * 3], dp[N * 3];
signed main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> x[i];
	for (int i = 1; i <= n; i++) cin >> y[i];
	update(1, 0, N - 5, 0, N - 5, {-2 * x[1], x[1] * x[1] + y[1] * y[1], 1});
	for (int i = 1; i <= n; i++) {
		dp[i] = query(1, 0, N - 5, a[i]) + a[i] * a[i];
		update(1, 0, N - 5, 0, N - 5, {-2 * x[i + 1], dp[i] + x[i + 1] * x[i + 1] + y[i + 1] * y[i + 1], 1});
	}
	cout << dp[n];
	return 0;
}
0