제출 #939090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
939090		vjudge1	Building Bridges (CEOI17_building)	C++17	0 / 100	69 ms	3544 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 N = 3e6;
const int MAX = 1e16;
struct Line{
	int k, b;
	Line(int k = MAX, int b = MAX) : k(k), b(b) {}
};

int F(Line &a, int x){
	if(a.k == MAX && a.b == MAX) return -MAX;
	return -(a.k*x + a.b);
}

struct LiChao{
	struct Node{
		Line k;
		Node *l, *r;
		Node(){
			l = nullptr, r = nullptr;
		}
	};
	int n;
	Node *root;
	LiChao(int sz) : n(sz), root(nullptr) {}
	void addLine(Node *&p, int l, int r, Line &a){
		if(!p) p = new Node();	
		int mid = (l + r) / 2;
		int l_side = F(a, l) > F(p->k, l);
		int m_side = F(a, mid) > F(p->k, mid);
		if(m_side) p->k = a;
		if(l == r-1) return;
		if(l_side == m_side){
			addLine(p->r, mid, r, a);
		}else{
			addLine(p->l, l, mid, a);
		}
	}
	void addLine(Line a){
		addLine(root, -n, n, a);
	}
	int get(Node *&p, int l, int r, int x){
		if(!p) return -MAX;
		if(l == r-1){
			return F(p->k, x);
		}
		int mid = (l + r) / 2;
		if(mid > x){
			return max(F(p->k, x), get(p->l, l, mid, x));
		}else{
			return max(F(p->k, x), get(p->r, mid, r, x));
		}
	}
	
	int get(int x){
		return get(root, -n, n, x);
	}
	
};
/*
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];
	}
	LiChao lch(N);
	vector<int> dp(n+1, MAX);
	dp[1] = 0;
	lch.addLine(Line(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]);
		
		*/
		/*int ans = MAX;
		for(int j = 1; j < i; j++){
			ans = min(ans, -2 * h[i] * h[j] + dp[j] - w[j] + h[j] * h[j] + w[i-1] + h[i] * h[i]);
			//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 = lch.get(-2*h[i]);
		mn = -mn;
		//cout << i << " = " << ans << " , " << mn + h[i] * h[i] + w[i-1] << '\n';
		dp[i] = min(dp[i], mn + h[i]*h[i] + w[i-1]);
		lch.addLine(Line(h[i], dp[i] - w[i] + h[i] * h[i]));
	}
	cout << dp[n];
	return 0;
}

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