Submission #250345

#	Time	Username	Problem	Language	Result	Execution time	Memory
250345		oolimry	Building Bridges (CEOI17_building)	C++14	0 / 100	130 ms	131076 KiB

building

#include <bits/stdc++.h>
#define m first
#define c second;
#define int long long
using namespace std;
typedef pair<int,int> line;

const int inf = 102345678901234567;

int get(line L, int x){ return L.m * x + L.c; }

int H[100005];
int C[100005];

struct lichao{
	int s, e, m;
	lichao *l, *r;
	line val = line(0,inf);
	
	lichao(int S, int E){
		s = S, e = E, m = (s+e)/2;
		if(s == e-1) return;
		l = new lichao(s, m);
		r = new lichao(m, e);
	}
	
	void insert(line L){
		if(get(L, m) < get(val, m)) swap(L, val); ///make val the dominant one
		
		if(s == e-1) return;
		
		if(get(L, s) < get(val, s)) l->insert(L); ///L has some chance in l
		else r->insert(L); ///L has some chance in r
	}
	
	int query(int x){
		if(s == e-1) return get(val, x);
		else if(x >= m) return min(get(val,x), r->query(x));
		else return min(get(val,x), l->query(x));
	}
	
} *root;

signed main(){
	ios_base::sync_with_stdio(false);
	
	int ans = 0;
	
	int n; cin >> n;
	for(int i = 0;i < n;i++) cin >> H[i];
	for(int i = 0;i < n;i++){
		cin >> C[i];
		ans += C[i];
		C[i] *= -1;
	}
	
	root = new lichao(-2000005, 0);
	
	int dp = C[0];
	root->insert(line(-2*H[0], dp + H[0]*H[0]));
	
	for(int i = 1;i < n;i++){
		dp = root->query(H[i]);
		dp += H[i]*H[i] + C[i];
		
		root->insert(line(-2*H[i], dp + H[i]*H[i]));
		
	}
	cout << dp + ans << "\n";
}

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