oj.uz

Submission #941220

# Submission time Handle Problem Language Result Execution time Memory
941220 2024-03-08T09:46:15 Z viwlesxq Building Bridges (CEOI17_building) C++17
100 / 100
 65 ms 12128 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 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 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 50 ms 10328 KB Output is correct
2 Correct 50 ms 10332 KB Output is correct
3 Correct 50 ms 10352 KB Output is correct
4 Correct 45 ms 10072 KB Output is correct
5 Correct 35 ms 11604 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 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 50 ms 10328 KB Output is correct
7 Correct 50 ms 10332 KB Output is correct
8 Correct 50 ms 10352 KB Output is correct
9 Correct 45 ms 10072 KB Output is correct
10 Correct 35 ms 11604 KB Output is correct
11 Correct 59 ms 11916 KB Output is correct
12 Correct 59 ms 11604 KB Output is correct
13 Correct 46 ms 10328 KB Output is correct
14 Correct 65 ms 12128 KB Output is correct
15 Correct 33 ms 12124 KB Output is correct
16 Correct 41 ms 11604 KB Output is correct
17 Correct 16 ms 10056 KB Output is correct
18 Correct 14 ms 10076 KB Output is correct