Submission #540176

#	Time	Username	Problem	Language	Result	Execution time	Memory
540176		xuliu	Building Bridges (CEOI17_building)	C++17	100 / 100	111 ms	28620 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; // ax + b
	Line() { a = 0; b = inf; }
	Line(ll _a, ll _b) { a = _a; b = _b; }
	ll operator()(ll x) { return a*x + b; }
};

const int N = 1e9 + 4;
int chg(int x) { return x-N; }
int chgg(int x) { return x+N; }

struct node {
	ll l, r;
	Line line;
	node *left = NULL, *right = NULL;
	node(int lb, int rb) {
		l = lb; r = rb;
	}
	void extend() {
		if(!left && l != r) {
			ll m = (l+r)/2;
			left = new node(l, m);
			right = new node(m+1, r);
		}
	}
	void add(Line seg) {
		debug cerr<<"adding seg.a = "<<seg.a<<", seg.b = "<<seg.b<<"\n";
		if(l == r) {
			if(seg(chg(l)) < line(chg(l))) line = seg;
			return;
		}
		extend();
		ll m = (l+r)/2;
		if(line.a < seg.a) swap(line, seg);
		if(line(chg(m)) > seg(chg(m))) {
			swap(line, seg);
			left->add(seg);
		}
		else right->add(seg);
	}
	ll get(ll x) {
		if(l == r) return line(chg(x));
		extend();
		int m = (l+r)/2;
		if(x <= m) return min(line(chg(x)), left->get(x));
		else return min(line(chg(x)), right->get(x));
	}
};

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	node root(0, 2*N+4);
	vector<ll> h(n), w(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]; }
	vector<ll> dp(n, inf);
	dp[0] = -w[0];
	root.add(Line(-2LL*h[0], dp[0]+h[0]*h[0]));
	for(int i=1; i<n; i++) {
		dp[i] = h[i]*h[i] - w[i];
		dp[i] += root.get(chgg(h[i]));
		root.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