oj.uz

Submission #45256

# Submission time Handle Problem Language Result Execution time Memory
45256 2018-04-12T08:18:02 Z qoo2p5 Building Bridges (CEOI17_building) C++17
100 / 100
 108 ms 49204 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y > x) {
		x = y;
		return 1;
	}
	return 0;
}

void run();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
	return 0;
}

const int N = (int) 1e5 + 123;
const int M = 1 << 20;

int n;
ll h[N], w[N];
ll dp[N], p[N];

struct Line {
	ll k, b;
	
	Line() : k(0), b(LINF) {}
	
	Line(ll k, ll b) : k(k), b(b) {}
	
	ll val(ll x) {
		return k * x + b;
	}
};

Line tree[2 * M];

void add(int i, int tl, int tr, Line l) {
	if (tl > tr) {
		return;
	}
	
	int mid = (tl + tr) / 2;
	if (l.val(mid) < tree[i].val(mid)) {
		swap(l, tree[i]);
	}
	
	if (l.val(tl) < tree[i].val(tl)) {
		add(2 * i + 1, tl, mid - 1, l);
	} else if (l.val(tr) < tree[i].val(tr)) {
		add(2 * i + 2, mid + 1, tr, l);
	}
}

void add(const Line &l) {
	add(0, 0, M - 1, l);
}

ll get(int i, int tl, int tr, ll x) {
	if (tl > tr) {
		return LINF;
	}
	
	int mid = (tl + tr) / 2;
	ll res = tree[i].val(x);
	if (x < mid) {
		mini(res, get(2 * i + 1, tl, mid - 1, x));
	} else {
		mini(res, get(2 * i + 2, mid + 1, tr, x));
	}
	return res;
}

ll get(ll x) {
	return get(0, 0, M - 1, x);
}

void update(int i) {
	add(Line(-2 * h[i], dp[i] - p[i] + h[i] * h[i]));
}

ll calc(int i) {
	return get(h[i]) + h[i] * h[i] + p[i - 1];
}

void run() {
	cin >> n;
	rep(i, 0, n) {
		cin >> h[i];
	}
	rep(i, 0, n) {
		cin >> w[i];
	}
	
	partial_sum(w, w + n, p);
	rep(i, 0, n) {
		dp[i] = LINF;
	}
	dp[0] = 0;
	update(0);
	rep(i, 1, n) {
		dp[i] = calc(i);
		update(i);
	}
	
	cout << dp[n - 1] << "\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33144 KB Output is correct
2 Correct 24 ms 33252 KB Output is correct
3 Correct 24 ms 33252 KB Output is correct
4 Correct 23 ms 33304 KB Output is correct
5 Correct 26 ms 33488 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 36508 KB Output is correct
2 Correct 78 ms 37528 KB Output is correct
3 Correct 108 ms 38796 KB Output is correct
4 Correct 71 ms 39624 KB Output is correct
5 Correct 69 ms 40572 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33144 KB Output is correct
2 Correct 24 ms 33252 KB Output is correct
3 Correct 24 ms 33252 KB Output is correct
4 Correct 23 ms 33304 KB Output is correct
5 Correct 26 ms 33488 KB Output is correct
6 Correct 108 ms 36508 KB Output is correct
7 Correct 78 ms 37528 KB Output is correct
8 Correct 108 ms 38796 KB Output is correct
9 Correct 71 ms 39624 KB Output is correct
10 Correct 69 ms 40572 KB Output is correct
11 Correct 80 ms 41776 KB Output is correct
12 Correct 80 ms 42840 KB Output is correct
13 Correct 68 ms 43968 KB Output is correct
14 Correct 84 ms 45116 KB Output is correct
15 Correct 76 ms 46104 KB Output is correct
16 Correct 69 ms 47032 KB Output is correct
17 Correct 55 ms 47996 KB Output is correct
18 Correct 53 ms 49204 KB Output is correct