oj.uz

Submission #939099

# Submission time Handle Problem Language Result Execution time Memory
939099 2024-03-06T05:39:45 Z vjudge1 Building Bridges (CEOI17_building) C++17
100 / 100
 58 ms 12124 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
	return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
	return a < b ? (a = b) == b : false;
}
const int N = 1e5 + 5;
const int M = 1e9 + 5;
const int inf = 1e9;

int h[N], w[N], dp[N];

struct line {
	int m, b;
	int operator * (int x) {
		return m * x + b;
	}
	int operator ^ (line x) {
		return ceil(1.0 * (b - x.b) / (x.m - m));
	};
};
 
struct LiChao {
	line tree[4 * N];
	int last, L[4 * N], R[4 * N];
	LiChao() {
		last = 0;
		for (int i = 0; i < 4 * N; ++i) {
			tree[i] = {inf, inf * inf};
		}
	}
	void add(line v, int lx = 0, int rx = M, int x = 0) {
		if (lx == rx) {
			if (tree[x] * lx > v * lx) swap(tree[x], v);
			return;
		}
		if (v.m == tree[x].m) {
			tree[x].b = min(tree[x].b, v.b);
			return;
		}
		int m = (lx + rx) >> 1;
		int ix = tree[x] ^ v;
		if (ix <= m) {
			if (tree[x] * (m + 1) > v * (m + 1)) swap(tree[x], v);
			add(v, lx, m, (L[x] ? L[x] : L[x] = ++last));
		} else {
			if (tree[x] * m > v * m) swap(tree[x], v);
			add(v, m + 1, rx, (R[x] ? R[x] : R[x] = ++last));
		}
	}
	int get(int i, int lx = 0, int rx = M, int x = 0){
		if (lx == rx) return tree[x] * i;
		int m = (lx + rx) >> 1;
		if (i <= m && L[x]) return min(tree[x] * i, get(i, lx, m, L[x]));
		if (m < i && R[x]) return min(tree[x] * i, get(i, m + 1, rx, R[x]));
		return tree[x] * i;
	}
}tree;

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> h[i];
	}
	for (int i = 1; i <= n; ++i) {
		cin >> w[i];
	}
	dp[1] = 0;
	int sum = w[1];
	tree.add({-2 * h[1], dp[1] - sum + h[1] * h[1]});
	for (int i = 2; i <= n; ++i) {
		dp[i] = tree.get(h[i]) + sum + h[i] * h[i];
		sum += w[i];
		tree.add({-2 * h[i], dp[i] - sum + h[i] * h[i]});
	}
	cout << dp[n];
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 9340 KB Output is correct
2 Correct 50 ms 10076 KB Output is correct
3 Correct 56 ms 10076 KB Output is correct
4 Correct 44 ms 9816 KB Output is correct
5 Correct 34 ms 11348 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 51 ms 9340 KB Output is correct
7 Correct 50 ms 10076 KB Output is correct
8 Correct 56 ms 10076 KB Output is correct
9 Correct 44 ms 9816 KB Output is correct
10 Correct 34 ms 11348 KB Output is correct
11 Correct 58 ms 11572 KB Output is correct
12 Correct 58 ms 11556 KB Output is correct
13 Correct 47 ms 10064 KB Output is correct
14 Correct 58 ms 11540 KB Output is correct
15 Correct 33 ms 12124 KB Output is correct
16 Correct 34 ms 11348 KB Output is correct
17 Correct 14 ms 9820 KB Output is correct
18 Correct 14 ms 9816 KB Output is correct