Submission #1261061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261061		kaiboy	Building Bridges (CEOI17_building)	C++20	100 / 100	85 ms	2376 KiB

building

// coached by rainboy
#include <algorithm>
#include <iostream>

using namespace std;

const       int   N = 100000;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

int aa[N], cc[N], ii0[N], ii1[N];
long long dp[N], xx[N];

__int128_t cross(long long x0, long long y0, long long x1, long long y1) {
	return (__int128_t) x0 * y1 - (__int128_t) x1 * y0;
}

__int128_t cross(int i, int j, int k) {
	long long xi = aa[i], yi = dp[i] + xi * xi;
	long long xj = aa[j], yj = dp[j] + xj * xj;
	long long xk = aa[k], yk = dp[k] + xk * xk;
	return cross(xj - xi, yj - yi, xk - xi, yk - yi);
}

long long calc(int i, int j) {
	return dp[i] + (long long) (aa[i] - aa[j]) * (aa[i] - aa[j]) - cc[j];
}

void solve(int l, int r) {
	if (r - l == 1)
		return;
	int m = l + r >> 1;
	solve(l, m);
	int k0 = 0;
	for (int i = l; i < m; i++)
		ii0[k0++] = i;
	sort(ii0, ii0 + k0, [] (int i, int j) { return aa[i] != aa[j] ? aa[i] < aa[j] : dp[i] < dp[j]; });
	int k0_ = 0;
	for (int h0 = 0; h0 < k0; h0++) {
		int i = ii0[h0];
		if (h0 && aa[i] == aa[ii0[h0 - 1]])
			continue;
		while (k0_ >= 2 && cross(ii0[k0_ - 2], ii0[k0_ - 1], i) <= 0)
			k0_--;
		ii0[k0_++] = i;
	}
	k0 = k0_;
	int k1 = 0;
	for (int i = m; i < r; i++)
		ii1[k1++] = i;
	sort(ii1, ii1 + k1, [] (int i, int j) { return aa[i] < aa[j]; });
	for (int h0 = 0, h1 = 0; h1 < k1; h1++) {
		int i = ii1[h1];
		while (h0 + 1 < k0 && calc(ii0[h0], i) > calc(ii0[h0 + 1], i))
			h0++;
		dp[i] = min(dp[i], calc(ii0[h0], i));
	}
	solve(m, r);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> aa[i];
	for (int i = 0; i < n; i++)
		cin >> cc[i];
	for (int i = 1; i < n; i++)
		dp[0] += cc[i], dp[i] = INF;
	solve(0, n);
	cout << dp[n - 1] << '\n';
	return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40