oj.uz

답안 #941220

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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