oj.uz

Submission #320012

# Submission time Handle Problem Language Result Execution time Memory
320012 2020-11-07T09:15:46 Z jungsnow Building Bridges (CEOI17_building) C++14
100 / 100
 103 ms 66732 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

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

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.init();
	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];
}

Compilation message

building.cpp:8:15: warning: overflow in conversion from 'double' to 'll' {aka 'long long int'} changes value from '1.0e+19' to '9223372036854775807' [-Woverflow]
    8 | const ll oo = 1e19;
      |               ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 62948 KB Output is correct
2 Correct 34 ms 62956 KB Output is correct
3 Correct 34 ms 62956 KB Output is correct
4 Correct 38 ms 62948 KB Output is correct
5 Correct 34 ms 62956 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 65252 KB Output is correct
2 Correct 81 ms 65252 KB Output is correct
3 Correct 82 ms 65252 KB Output is correct
4 Correct 80 ms 65380 KB Output is correct
5 Correct 78 ms 65252 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 62948 KB Output is correct
2 Correct 34 ms 62956 KB Output is correct
3 Correct 34 ms 62956 KB Output is correct
4 Correct 38 ms 62948 KB Output is correct
5 Correct 34 ms 62956 KB Output is correct
6 Correct 80 ms 65252 KB Output is correct
7 Correct 81 ms 65252 KB Output is correct
8 Correct 82 ms 65252 KB Output is correct
9 Correct 80 ms 65380 KB Output is correct
10 Correct 78 ms 65252 KB Output is correct
11 Correct 89 ms 66732 KB Output is correct
12 Correct 103 ms 66276 KB Output is correct
13 Correct 73 ms 66528 KB Output is correct
14 Correct 89 ms 66532 KB Output is correct
15 Correct 88 ms 66276 KB Output is correct
16 Correct 74 ms 66276 KB Output is correct
17 Correct 68 ms 66372 KB Output is correct
18 Correct 75 ms 66532 KB Output is correct