Submission #45256

#	Time	Username	Problem	Language	Result	Execution time	Memory
45256		qoo2p5	Building Bridges (CEOI17_building)	C++17	100 / 100	108 ms	49204 KiB

building

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y > x) {
		x = y;
		return 1;
	}
	return 0;
}

void run();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
	return 0;
}

const int N = (int) 1e5 + 123;
const int M = 1 << 20;

int n;
ll h[N], w[N];
ll dp[N], p[N];

struct Line {
	ll k, b;
	
	Line() : k(0), b(LINF) {}
	
	Line(ll k, ll b) : k(k), b(b) {}
	
	ll val(ll x) {
		return k * x + b;
	}
};

Line tree[2 * M];

void add(int i, int tl, int tr, Line l) {
	if (tl > tr) {
		return;
	}
	
	int mid = (tl + tr) / 2;
	if (l.val(mid) < tree[i].val(mid)) {
		swap(l, tree[i]);
	}
	
	if (l.val(tl) < tree[i].val(tl)) {
		add(2 * i + 1, tl, mid - 1, l);
	} else if (l.val(tr) < tree[i].val(tr)) {
		add(2 * i + 2, mid + 1, tr, l);
	}
}

void add(const Line &l) {
	add(0, 0, M - 1, l);
}

ll get(int i, int tl, int tr, ll x) {
	if (tl > tr) {
		return LINF;
	}
	
	int mid = (tl + tr) / 2;
	ll res = tree[i].val(x);
	if (x < mid) {
		mini(res, get(2 * i + 1, tl, mid - 1, x));
	} else {
		mini(res, get(2 * i + 2, mid + 1, tr, x));
	}
	return res;
}

ll get(ll x) {
	return get(0, 0, M - 1, x);
}

void update(int i) {
	add(Line(-2 * h[i], dp[i] - p[i] + h[i] * h[i]));
}

ll calc(int i) {
	return get(h[i]) + h[i] * h[i] + p[i - 1];
}

void run() {
	cin >> n;
	rep(i, 0, n) {
		cin >> h[i];
	}
	rep(i, 0, n) {
		cin >> w[i];
	}
	
	partial_sum(w, w + n, p);
	rep(i, 0, n) {
		dp[i] = LINF;
	}
	dp[0] = 0;
	update(0);
	rep(i, 1, n) {
		dp[i] = calc(i);
		update(i);
	}
	
	cout << dp[n - 1] << "\n";
}

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