Submission #939315

#	Time	Username	Problem	Language	Result	Execution time	Memory
939315		iskhakkutbilim	Building Bridges (CEOI17_building)	C++17	100 / 100	106 ms	52808 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define int long long
const int inf = 1e9;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
struct Line{
	int k, b;
	int operator * (int x){
		return k * x + b;
	}
	int operator ^ (Line x){
		return ceil((b - x.b) / (x.k - k));
	};
};

struct LiChao{
	Line tree[N * 30];
	int last, L[N * 30], R[N * 30];
	LiChao(){
		last = 0;
		for(int i=0;i<(N*30);i++) tree[i] = {inf, inf * inf};
	}
	
	void add(Line v, int lx = 0, int rx = mod, int x = 0){
		if(lx == rx){
			if(tree[x] * lx > v * lx) swap(tree[x], v);
			return;
		}
		if(v.k == tree[x].k){
			tree[x].b = min(tree[x].b, v.b);
			return;
		}
		
		int m = (lx + rx) >> 1;
		int ix = tree[x] ^ v;
		if(ix <= m){
			if(tree[x] * (m + 1) > v * (m + 1)) swap(tree[x], v);
			add(v, lx, m, (L[x] ? L[x] : L[x] = ++last));
		} else {
			if(tree[x] * m > v * m) swap(tree[x], v);
			add(v, m + 1, rx, (R[x] ? R[x] : R[x] = ++last));
		}
	}
	
	int get(int i, int lx = 0, int rx = mod, int x = 0){
		if(lx == rx) return tree[x] * i;
		int m = (lx + rx) >> 1;
		if(i <= m && L[x]) return min(tree[x] * i, get(i, lx, m, L[x]));
		if(m < i && R[x]) return min(tree[x] * i, get(i, m + 1, rx, R[x]));
		return tree[x] * i;
	}
}tree;
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/
signed main(){
	int n; cin >> n;
	vector<int> h(n+1);
	for(int i = 1;i <= n; i++) cin >> h[i];
	vector<int> w(n+1, 0);
	for(int i = 1;i <= n; i++){
		cin >> w[i];
		w[i]+= w[i-1];
	}
	
	vector<int> dp(n+1);
	dp[1] = 0;
	tree.add({-2 * h[1], dp[1] - w[1] + h[1] * h[1]});
	for(int i = 2;i <= n; i++){
			
		// kx + b
		/*
		
			new_dp[i] = (h[i] - h[j])^2 + dp[j]
			(h[i] - h[j]) * (h[i] - h[j]) = kx
			h[i] * h[i] - h[i] * h[j] - h[j] * h[i] + h[j] * h[j]
			dp[i] = min(dp[i], -2 * h[i] * h[j] + dp[j] - w[j] + h[j] * h[j] + w[i-1] + h[i] * h[i]);
		
		*/
		/*
		for(int j = 1; j < i; j++){
			//dp[i] = min(dp[i], -2 * h[i] * h[j] + dp[j] - w[j] + h[j] * h[j] + w[i-1] + h[i] * h[i]);
		}
		*/
		int mn = tree.get(h[i]);
		
		dp[i] = mn + h[i]*h[i] + w[i-1];
		tree.add({-2 * h[i], dp[i] - w[i] + h[i] * h[i]});
	}
	cout << dp[n];
	return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40