oj.uz

Submission #384241

# Submission time Handle Problem Language Result Execution time Memory
384241 2021-03-31T21:23:38 Z wind_reaper Building Bridges (CEOI17_building) C++17
100 / 100
 51 ms 6124 KB 
#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct LiChaoTree{
	static const T identity = numeric_limits<T>::max();

	struct Line{
		T m, c;

		Line(){
			m = 0;
			c = identity;
		}

		Line(T m, T c) : m(m), c(c) {}

		T val(T x){
			return m*x + c;
		}
	};

	struct Node{
		Node *lc, *rc;
		Line line;

		Node() : lc(0), rc(0) {}
	};

	deque<Node> buffer;

	Node* new_node(){
		buffer.emplace_back();
		return &buffer.back();
	}

	Node *root;

	T L, R;
	LiChaoTree(T L, T R){
		this->L = L;
		this->R = R;

		root = new_node();
	}

	void insert(Node* &node, T l, T r, Line line){
		if(!node){
			node = new_node();
			node->line = line;
			return;
		}

		if(r - l == 1)
			return;

		T mid = (l + r) >> 1;
		
		if(line.val(mid) < node->line.val(mid))
			swap(line, node->line);

		if(line.val(l) < node->line.val(l)) insert(node->lc, l, mid, line);
		else insert(node->rc, mid, r, line);
	}

	T query(Node* &node, T l, T r, T x){
		if(!node)
			return identity;

		T mid = (l + r) >> 1;
		T res = node->line.val(x);

		if(r - l == 1)
			return res;

		if(x < mid) return min(res, query(node->lc, l, mid, x));
		else return min(res, query(node->rc, mid, r, x));
	}

	void insert(T m, T c) { insert(root, L, R, Line(m, c)); }
	T query(T x) { return query(root, L, R, x); }
};

int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
		
	int n;
	cin >> n; 
 
	vector<int64_t> h(n+1), w(n+1);
	for(int i = 1; i <= n; i++)
		cin >> h[i];

	int64_t sum = 0; 
	for(int i = 1; i <= n; i++){
		cin >> w[i];
		sum += w[i];
	}

	LiChaoTree<int64_t> dp(1, 1000001);
	dp.insert(-2*h[1], h[1]*h[1] - w[1]);

	int64_t ans = 0;
	for(int i = 2; i <= n; i++){
		int64_t temp = dp.query(h[i]) + h[i]*h[i] - w[i];
		dp.insert(-2*h[i], temp + h[i]*h[i]);
		if(i == n) ans = temp;
	}

	cout << ans + sum << '\n';
	return 0; 
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3436 KB Output is correct
2 Correct 47 ms 3436 KB Output is correct
3 Correct 47 ms 3436 KB Output is correct
4 Correct 45 ms 3052 KB Output is correct
5 Correct 34 ms 5356 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 47 ms 3436 KB Output is correct
7 Correct 47 ms 3436 KB Output is correct
8 Correct 47 ms 3436 KB Output is correct
9 Correct 45 ms 3052 KB Output is correct
10 Correct 34 ms 5356 KB Output is correct
11 Correct 49 ms 3820 KB Output is correct
12 Correct 51 ms 4076 KB Output is correct
13 Correct 39 ms 3052 KB Output is correct
14 Correct 51 ms 4076 KB Output is correct
15 Correct 36 ms 6124 KB Output is correct
16 Correct 40 ms 5504 KB Output is correct
17 Correct 31 ms 3052 KB Output is correct
18 Correct 25 ms 3052 KB Output is correct