oj.uz

Submission #320010

# Submission time Handle Problem Language Result Execution time Memory
320010 2020-11-07T09:13:20 Z jungsnow Building Bridges (CEOI17_building) C++14
0 / 100
 50 ms 5348 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int maxm = 1e6 + 1;
const int maxn = 100001;
const ll oo = 1e18;

struct line {
	ll a, b;
	line () {}
	line (ll a, ll b) : a(a), b(b) {}
	ll get(ll x) {
		return a * x + b;
	}
} it[4 * maxm];

struct lichaotree {
	#define m ((l + r) >> 1)
	void init() {
		for (int i = 0; i < 4 * maxm; ++i) it[i].a = 0, it[i].b = oo; 
	}
	void insert(int node, int l, int r, line u) {
		bool lef = u.get(l) < it[node].get(l);
		bool mid = u.get(m) < it[node].get(m);
		if (mid) swap(u, it[node]);
		if (l == r) return;
		if (lef != mid) insert(node << 1, l, m, u);
		else insert(node << 1 | 1, m + 1, r, u);
	}
	ll get(int node, int l, int r, ll u) {
		if (l == r) return it[node].get(u);
		if (u <= m) return min(it[node].get(u), get(node << 1, l, m, u));
		else return min(it[node].get(u), get(node << 1 | 1, m + 1, r, u));
	}
	#undef m
} A;

int n;
ll dp[maxn], h[maxn], w[maxn];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> h[i];
	for (int i = 1; i <= n; ++i) cin >> w[i];
	dp[1] = -w[1];
	A.insert(1, 0, maxm - 1, line(-2 * h[1], h[1] * h[1] - w[1]));
	for (int i = 2; i <= n; ++i) {
		dp[i] = A.get(1, 0, maxm - 1, h[i]) + h[i] * h[i] - w[i];
		A.insert(1, 0, maxm - 1, line(-2 * h[i], h[i] * h[i] + dp[i]));
	}
	for (int i = 1; i <= n; ++i) dp[n] += w[i];
	cout << dp[n];
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 2 ms 748 KB Output is correct
5 Incorrect 1 ms 876 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 4196 KB Output is correct
2 Correct 47 ms 4196 KB Output is correct
3 Correct 49 ms 4192 KB Output is correct
4 Correct 44 ms 3940 KB Output is correct
5 Incorrect 40 ms 5348 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 2 ms 748 KB Output is correct
5 Incorrect 1 ms 876 KB Output isn't correct