Submission #390166

#	Time	Username	Problem	Language	Result	Execution time	Memory
390166		ronnith	Building Bridges (CEOI17_building)	C++14	100 / 100	61 ms	8212 KiB

building

#include <bits/stdc++.h>

using namespace std;

struct line {
	long long m, c;
	line() : m(0), c(0) {}
	line(long long mm, long long cc) : m(mm), c(cc) {}
	inline long long get_y(long long x) { return m*x+c; }
};

void swap(line& x, line& y) {
	swap(x.m, y.m);
	swap(x.c, y.c);
}

struct node {
	int l, r;
	line crr;
	node* left;
	node* right;
	node(int ll, int rr) : l(ll), r(rr), left(nullptr), right(nullptr) {}
	node(int ll, int rr, line L) : l(ll), r(rr), crr(L), left(nullptr), right(nullptr) {}
};

struct li_chao_tree {
	int MX;
	node* root;

	li_chao_tree(int _) : MX(_) {
		root = nullptr;
	}

	inline bool is_mid_range(int l, int r, node* v, line L) {
		return (v->crr.get_y(l) > L.get_y(l)) != (v->crr.get_y(r) > L.get_y(r));
	}

	void insert(node* v, int lx, int rx, line L) {
		if(lx == rx) {
			if(L.get_y(lx) < v->crr.get_y(lx)) {
				v->crr = L;
			}
		} else {
			int mid = (lx+rx)/2;
			if(is_mid_range(lx, mid, v, L)) {
				if(v->crr.get_y(rx) > L.get_y(rx)) {
					swap(v->crr, L);
				}
				if(v->left == nullptr) {
					v->left = new node(lx, mid, L);
					return;
				}
				insert(v->left, lx, mid, L);
			} else {
				if(v->crr.get_y(lx) > L.get_y(lx)) {
					swap(v->crr, L);
				}
				if(v->right == nullptr) {
					v->right = new node(mid + 1, rx, L);
					return;
				}
				insert(v->right, mid + 1, rx, L);
			}
		}
	}

	void insert(line L) {
		if(root == nullptr) {
			root = new node(0, MX, L);
			return;
		}
		insert(root, 0, MX, L);
	}

	long long query(node* v, int x) {
		if(v == nullptr) return LONG_LONG_MAX;
		int mid = (v->l+v->r)/2;
		if(x <= mid) {
			return min(query(v->left, x), v->crr.get_y(x));
		} else {
			return min(query(v->right, x), v->crr.get_y(x));
		}
	}
	
	long long query(int x) {
		return query(root, x);
	}
};

const int N = (int)1e5;
const int MX = (int)1e6;
int n;
long long H[N], W[N], dp[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for(int i = 0;i < n;i ++) {
		cin >> H[i];
	}
	for(int i = 0;i < n;i ++) {
		cin >> W[i];
		if(i != 0) W[i] += W[i - 1];
	}
	dp[0] = 0;
	li_chao_tree lct(MX);
	lct.insert(line(-2*H[0], H[0]*H[0]-W[0]+dp[0]));
	for(int i = 1;i < n;i ++) {
		dp[i] = H[i]*H[i]+W[i-1] + lct.query(H[i]);
		lct.insert(line(-2*H[i], H[i]*H[i]-W[i]+dp[i]));
	}
	cout << dp[n - 1] << '\n';
	return 0;
}

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