Submission #941220

#	Time	Username	Problem	Language	Result	Execution time	Memory
941220		viwlesxq	Building Bridges (CEOI17_building)	C++17	100 / 100	65 ms	12128 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
	return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
	return a < b ? (a = b) == b : false;
}
const int N = 1e5 + 5;
const int M = 1e9 + 5;
const int inf = 1e9;

int h[N], w[N], dp[N];

struct line {
	int m, b;
	int operator * (int x) {
		return m * x + b;
	}
	int operator ^ (line x) {
		return ceil(1.0 * (b - x.b) / (x.m - m));
	};
};
 
struct LiChao {
	line tree[4 * N];
	int last, L[4 * N], R[4 * N];
	LiChao() {
		last = 0;
		for (int i = 0; i < 4 * N; ++i) {
			tree[i] = {inf, inf * inf};
		}
	}
	void add(line v, int lx = 0, int rx = M, int x = 0) {
		if (lx == rx) {
			if (tree[x] * lx > v * lx) swap(tree[x], v);
			return;
		}
		if (v.m == tree[x].m) {
			tree[x].b = min(tree[x].b, v.b);
			return;
		}
		int m = (lx + rx) >> 1;
		int ix = tree[x] ^ v;
		if (ix <= m) {
			if (tree[x] * (m + 1) > v * (m + 1)) swap(tree[x], v);
			add(v, lx, m, (L[x] ? L[x] : L[x] = ++last));
		} else {
			if (tree[x] * m > v * m) swap(tree[x], v);
			add(v, m + 1, rx, (R[x] ? R[x] : R[x] = ++last));
		}
	}
	int get(int i, int lx = 0, int rx = M, int x = 0){
		if (lx == rx) return tree[x] * i;
		int m = (lx + rx) >> 1;
		if (i <= m && L[x]) return min(tree[x] * i, get(i, lx, m, L[x]));
		if (m < i && R[x]) return min(tree[x] * i, get(i, m + 1, rx, R[x]));
		return tree[x] * i;
	}
}tree;

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> h[i];
	}
	for (int i = 1; i <= n; ++i) {
		cin >> w[i];
	}
	dp[1] = 0;
	int sum = w[1];
	tree.add({-2 * h[1], dp[1] - sum + h[1] * h[1]});
	for (int i = 2; i <= n; ++i) {
		dp[i] = tree.get(h[i]) + sum + h[i] * h[i];
		sum += w[i];
		tree.add({-2 * h[i], dp[i] - sum + h[i] * h[i]});
	}
	cout << dp[n];
}

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