Submission #855914

#	Time	Username	Problem	Language	Result	Execution time	Memory
855914		wakandaaa	Building Bridges (CEOI17_building)	C++17	100 / 100	38 ms	15844 KiB

building

#include <bits/stdc++.h>
#define int long long

using namespace std;

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
	return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
	return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
	a += b;
	if (a >= mod) a -= mod;
	if (a < 0) a += mod;
}
 
struct line {
	mutable int a, b, p;
	bool operator < (const line &x) const {
		return a < x.a;
	}
	bool operator < (const int &x) const {
		return p < x;
	}
};
 
struct cht : multiset<line, less<>> {
	const int inf = LLONG_MAX;
	int div(int a, int b) {
		return a / b - ((a ^ b) < 0 && a % b);
	}
	bool intersect(iterator x, iterator y) {
		if (y == end()) {
			x->p = inf;
			return false;
		}
		if (x->a == y->a) {
			x->p = x->b > y->b ? inf : -inf;
		}
		else x->p = div(x->b - y->b, y->a - x->a);
		return x->p >= y->p;
	}
	void add(int a, int b) {
		a = -a;
		b = -b;
		auto z = insert({a, b, 0}), y = z++, x = y;
		while (intersect(y, z)) z = erase(z);
		if (x != begin() && intersect(--x, y)) intersect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p) intersect(x, erase(y));
	}
	int get(int x) {
		auto l = *lower_bound(x);
		return -(l.a * x + l.b);
	}
} T;

int n;
int h[N], w[N];
int f[N];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	// freopen(file".inp", "r", stdin);
	// freopen(file".out", "w", stdout);

	cin >> n;
	int sum = 0;
	for (int i = 1; i <= n; ++i) cin >> h[i];
	for (int i = 1; i <= n; ++i) cin >> w[i], sum += w[i];

	f[1] = -w[1];
	T.add(-2 * h[1], h[1] * h[1] + f[1]);

	for (int i = 2; i <= n; ++i) {
		f[i] = T.get(h[i]) + h[i] * h[i] - w[i];
		T.add(-2 * h[i], h[i] * h[i] + f[i]);
	}

	cout << f[n] + sum;

	return 0;
}

/*
f[i] = ax + b + c
a : -2 * h[i]
b : h[i] * h[i] + f[i]
c : h[i] * h[i] - w[i]
*/

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