Submission #528070

#	Time	Username	Problem	Language	Result	Execution time	Memory
528070		sidon	Building Bridges (CEOI17_building)	C++17	100 / 100	81 ms	15940 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define sp << ' ' <<
#define nl << '\n'

const int INF = 1e16;

struct Line {
	int m, c;
	Line(int C) : m(0), c(C) {}
	Line(int M, int C) : m(M), c(C) {}
	int operator()(int x) {
		return m * x + c;
	}
};

struct LichenTree {
	int l, r;
	Line v;
	LichenTree *L = NULL, *R = NULL;
	LichenTree(int lv, int rv) : l(lv), r(rv), v(INF) {}
	void insert(Line u) {
		int m = (l + r) / 2;
		if(v(m) > u(m)) swap(u, v);
		if(r - l > 1) {
			if(u.m >= v.m)
				(L ? : L = new LichenTree(l, m))->insert(u);
			else
				(R ? : R = new LichenTree(m, r))->insert(u);
		}
	}
	int operator()(int x) {
		if(r - l < 2) return v(x);
		if(x < (l + r) / 2) {
			return min(v(x), L ? (*L)(x) : INF);
		} else {
			return min(v(x), R ? (*R)(x) : INF);
		}
	}
} lt(0, 1e6+5);

const int Z = 1e5+1;

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

signed main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;

	for(int i = 1; i <= N; ++i)
		cin >> h[i];

	for(int i = 1; i <= N; ++i) {
		cin >> w[i];
		w[i] += w[i-1];
		dp[i] = INF;
	}

	for(int i = 1; i <= N; ++i) {
		dp[i] = h[i] * h[i] + w[i-1] + lt(h[i]);
		if(i < 2) dp[i] = 0;

		lt.insert(Line(- 2 * h[i], dp[i] + h[i] * h[i] - w[i]));
	}

	cout << dp[N];
}

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