oj.uz

Submission #528070

# Submission time Handle Problem Language Result Execution time Memory
528070 2022-02-19T06:51:36 Z sidon Building Bridges (CEOI17_building) C++17
100 / 100
 81 ms 15940 KB 
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define sp << ' ' <<
#define nl << '\n'

const int INF = 1e16;

struct Line {
	int m, c;
	Line(int C) : m(0), c(C) {}
	Line(int M, int C) : m(M), c(C) {}
	int operator()(int x) {
		return m * x + c;
	}
};

struct LichenTree {
	int l, r;
	Line v;
	LichenTree *L = NULL, *R = NULL;
	LichenTree(int lv, int rv) : l(lv), r(rv), v(INF) {}
	void insert(Line u) {
		int m = (l + r) / 2;
		if(v(m) > u(m)) swap(u, v);
		if(r - l > 1) {
			if(u.m >= v.m)
				(L ? : L = new LichenTree(l, m))->insert(u);
			else
				(R ? : R = new LichenTree(m, r))->insert(u);
		}
	}
	int operator()(int x) {
		if(r - l < 2) return v(x);
		if(x < (l + r) / 2) {
			return min(v(x), L ? (*L)(x) : INF);
		} else {
			return min(v(x), R ? (*R)(x) : INF);
		}
	}
} lt(0, 1e6+5);

const int Z = 1e5+1;

int N, h[Z], w[Z], dp[Z];

signed main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;

	for(int i = 1; i <= N; ++i)
		cin >> h[i];

	for(int i = 1; i <= N; ++i) {
		cin >> w[i];
		w[i] += w[i-1];
		dp[i] = INF;
	}

	for(int i = 1; i <= N; ++i) {
		dp[i] = h[i] * h[i] + w[i-1] + lt(h[i]);
		if(i < 2) dp[i] = 0;

		lt.insert(Line(- 2 * h[i], dp[i] + h[i] * h[i] - w[i]));
	}

	cout << dp[N];
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 448 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4912 KB Output is correct
2 Correct 43 ms 4740 KB Output is correct
3 Correct 45 ms 4748 KB Output is correct
4 Correct 37 ms 3860 KB Output is correct
5 Correct 35 ms 10632 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 448 KB Output is correct
6 Correct 44 ms 4912 KB Output is correct
7 Correct 43 ms 4740 KB Output is correct
8 Correct 45 ms 4748 KB Output is correct
9 Correct 37 ms 3860 KB Output is correct
10 Correct 35 ms 10632 KB Output is correct
11 Correct 69 ms 11460 KB Output is correct
12 Correct 75 ms 11720 KB Output is correct
13 Correct 43 ms 5744 KB Output is correct
14 Correct 81 ms 12380 KB Output is correct
15 Correct 41 ms 15940 KB Output is correct
16 Correct 34 ms 10588 KB Output is correct
17 Correct 26 ms 3636 KB Output is correct
18 Correct 26 ms 3664 KB Output is correct