Submission #1099269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099269		tht2005	Building Bridges (CEOI17_building)	C++17	0 / 100	90 ms	5200 KiB

building

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = (int)1e5 + 10;

int h[N];
ll s[N], f[N];

struct line_t {
	ll k, m;
	ll operator() (ll x) {
		return k * x + m;
	}
	bool operator< (const line_t& rhs) const {
		if(k != rhs.k) return k > rhs.k;
		return m > rhs.m;
	}
	bool operator== (const line_t& rhs) const {
		return k == rhs.k;
	}
};
struct cht {
	deque<line_t> dq;

	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }

	bool check(const line_t& a, const line_t& b, const line_t& c) {
		return div(b.m - a.m, a.k - b.k) >= div(c.m - b.m, b.k - c.k);
	}

	void add(const line_t& l) {
		while((int)dq.size() > 1 && check(dq[(int)dq.size() - 2], dq.back(), l))
			dq.pop_back();
		dq.push_back(l);
	}

	ll query(int x) {
		while((int)dq.size() > 1 && dq[0](x) >= dq[1](x))
			dq.pop_front();
		return dq.front()(x);
	}
};

line_t lf[N];
int rt[N];

void dq(int l, int r) {
	if(l == r)
		return;
	int m = (l + r) >> 1;
	dq(l, m);

	for(int i = l; i <= m; ++i)
		lf[i] = { -2LL * h[i], f[i] + (ll)h[i] * h[i] - s[i] };
	sort(lf + l, lf + m + 1);
	int ptr = unique(lf + l, lf + m + 1) - lf;

	cht c;
	for(int i = l; i < ptr; ++i)
		c.add(lf[i]);

	for(int i = m + 1; i <= r; ++i)
		rt[i] = i;
	sort(rt + m + 1, rt + r + 1, [&](int i, int j) {
		return h[i] < h[j];
	});

	for(int j = m + 1; j <= r; ++j) {
		int i = rt[j];
		f[i] = min(f[i], c.query(h[i]) + (ll)h[i] * h[i] + s[i - 1]);
	}

	dq(m + 1, r);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin >> h[i];
	for(int i = 1; i <= n; ++i) {
		cin >> s[i];
		s[i] += s[i - 1];
	}

	memset(f, 0x3f, sizeof(f));
	f[1] = 0;
	dq(1, n);

	cout << f[n];

	return 0;
}

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