oj.uz

Submission #855914

# Submission time Handle Problem Language Result Execution time Memory
855914 2023-10-02T08:58:10 Z wakandaaa Building Bridges (CEOI17_building) C++17
100 / 100
 38 ms 15844 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4560 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9928 KB Output is correct
2 Correct 33 ms 9820 KB Output is correct
3 Correct 31 ms 9800 KB Output is correct
4 Correct 28 ms 9556 KB Output is correct
5 Correct 26 ms 10844 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4560 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 34 ms 9928 KB Output is correct
7 Correct 33 ms 9820 KB Output is correct
8 Correct 31 ms 9800 KB Output is correct
9 Correct 28 ms 9556 KB Output is correct
10 Correct 26 ms 10844 KB Output is correct
11 Correct 35 ms 9816 KB Output is correct
12 Correct 32 ms 9796 KB Output is correct
13 Correct 24 ms 9816 KB Output is correct
14 Correct 30 ms 9876 KB Output is correct
15 Correct 38 ms 15844 KB Output is correct
16 Correct 26 ms 10840 KB Output is correct
17 Correct 16 ms 9816 KB Output is correct
18 Correct 17 ms 9804 KB Output is correct