Submission #320011

#	Time	Username	Problem	Language	Result	Execution time	Memory
320011		jungsnow	Building Bridges (CEOI17_building)	C++14	0 / 100	58 ms	4476 KiB

building

#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.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 (stderr)

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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40