oj.uz

Submission #540179

# Submission time Handle Problem Language Result Execution time Memory
540179 2022-03-19T14:20:44 Z xuliu Building Bridges (CEOI17_building) C++17
100 / 100
 54 ms 35524 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33136 KB Output is correct
2 Correct 14 ms 33156 KB Output is correct
3 Correct 14 ms 33108 KB Output is correct
4 Correct 15 ms 33108 KB Output is correct
5 Correct 15 ms 33108 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 35412 KB Output is correct
2 Correct 45 ms 35412 KB Output is correct
3 Correct 51 ms 35512 KB Output is correct
4 Correct 43 ms 35452 KB Output is correct
5 Correct 44 ms 35500 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33136 KB Output is correct
2 Correct 14 ms 33156 KB Output is correct
3 Correct 14 ms 33108 KB Output is correct
4 Correct 15 ms 33108 KB Output is correct
5 Correct 15 ms 33108 KB Output is correct
6 Correct 49 ms 35412 KB Output is correct
7 Correct 45 ms 35412 KB Output is correct
8 Correct 51 ms 35512 KB Output is correct
9 Correct 43 ms 35452 KB Output is correct
10 Correct 44 ms 35500 KB Output is correct
11 Correct 52 ms 35464 KB Output is correct
12 Correct 49 ms 35508 KB Output is correct
13 Correct 46 ms 35460 KB Output is correct
14 Correct 54 ms 35500 KB Output is correct
15 Correct 40 ms 35524 KB Output is correct
16 Correct 40 ms 35504 KB Output is correct
17 Correct 34 ms 35500 KB Output is correct
18 Correct 37 ms 35416 KB Output is correct