Submission #528082

#	Time	Username	Problem	Language	Result	Execution time	Memory
528082		sidon	Building Bridges (CEOI17_building)	C++17	100 / 100	60 ms	36648 KiB

building

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

const int SZ = 1<<20, INF = 1e16;

struct Line {
	int m = 0, c = INF;
	Line() {}
	int operator()(int x) { return m * x + c; }
};

Line s[SZ<<1], u;

void add(int x, int l, int r) {
	int m = (l + r) / 2;
	if(s[x](m) > u(m)) swap(u, s[x]);
	if(r - l > 1)
		u.m >= s[x].m ? add(2*x, l, m) : add(2*x+1, m, r);
}

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) {

		for(int j = h[i] + SZ; j; j/=2)
			dp[i] = min(dp[i], s[j](h[i]));

		dp[i] += h[i] * h[i] + w[i-1];
		if(i < 2) dp[i] = 0;

		u.m = - 2 * h[i];
		u.c = dp[i] + h[i] * h[i] - w[i];

		add(1, 0, SZ);
	}

	cout << dp[N];
}

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