Submission #540179

#	Time	Username	Problem	Language	Result	Execution time	Memory
540179		xuliu	Building Bridges (CEOI17_building)	C++17	100 / 100	54 ms	35524 KiB

building

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)
 
const ll inf = 1e18 + 4;

struct Line {
	ll a, b;
	Line(ll _a, ll _b) { a = _a; b = _b; }
	Line() { a = 0; b = inf; }
	ll operator()(ll x) { return a*x+b; }
};

struct segtree {
	int sz;
	vector<Line> seg;
	void init(int n) {
		sz = 1;
		while(sz < n) sz<<=1;
		seg.assign(2*sz+4, Line());
	}
	void add(Line line, int x, int lx, int rx) {
		int m = (lx+rx)/2;
		if(seg[x](m) > line(m)) swap(seg[x], line);
		if(lx == rx) return;
		if(line.a >= seg[x].a) add(line, 2*x, lx, m);
		else add(line, 2*x+1, m+1, rx);
	}
	void add(Line line) { add(line, 1, 0, sz-1); }
	ll get(ll x) {
		ll v = x, ret = inf;
		x += sz;
		while(x) {
			ret = min(ret, seg[x](v));
			x >>= 1;
		}
		return ret;
	}
};

const int N = 1e6 + 4;

/*
 * 
 * dp[i] = -wi + min(dp[j] + (hj-hi)^2) = -wi + min(dp[j] + hj^2 - 2hihj + hi^2) = -wi + hi^2 + min(dp[j]+hj^2-2hihj)
 * fj(x) = (dp[j]+hj^2) + (-2hj)*x
 * dp[i] = -wi+hi^2 + min(fj(hi)), for j < i
 * result = dp[n] + W, where W = sum of all wi 
 * 
 */

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	vector<ll> w(n), h(n), dp(n, inf);
	segtree st; st.init(N);
	ll W  = 0;
	for(int i=0; i<n; i++) cin>>h[i];
	for(int i=0; i<n; i++) { cin>>w[i]; W += w[i]; }
	dp[0] = -w[0]; st.add(Line(-2LL*h[0], dp[0]+h[0]*h[0]));
	for(int i=1; i<n; i++) {
		dp[i] = -w[i] + h[i]*h[i] + st.get(h[i]);
		st.add(Line(-2LL*h[i], dp[i]+h[i]*h[i]));
	}
	cout<<dp[n-1]+W;
}

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