Submission #860140

#	Time	Username	Problem	Language	Result	Execution time	Memory
860140		Hacv16	Building Bridges (CEOI17_building)	C++17	100 / 100	47 ms	67236 KiB

building

#include <bits/stdc++.h>
using namespace std;
 
#define int long long int
 
const int MAX = 1e5 + 15;
const int MAXC = 1e6 + 10;
const int INF = 1e18 + 10;

int n, h[MAX], sw[MAX], dp[MAX];
 
struct Line
{
	int a, b;
	Line(int x = 0, int y = INF) : a(x), b(y) { }

	int operator ()(int x){ return a * x + b; }
 
} seg[4 * MAXC];
 
void update(int p, int l, int r, Line f)
{
	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
 
	bool lessMid = f(m) < seg[p](m);
	bool lessLeft = f(l) < seg[p](l);
 
	if(lessMid) swap(seg[p], f);
 
	if(l == r) return;
 
	if(lessMid != lessLeft) update(e, l , m , f);
	else update(d, m + 1 , r , f);
}
 
int query(int x, int p, int l, int r)
{
	if(l == r) return seg[p](x);
	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
 
	if(x <= m) return min(seg[p](x), query(x, e, l, m));
	else return min(seg[p](x), query(x, d, m + 1, r));
}
 
int32_t main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	cin >> n;
 
	for(int i = 1; i <= n; i++) cin >> h[i];
	for(int i = 1; i <= n; i++) cin >> sw[i], sw[i] += sw[i - 1];
 
	auto getA = [&](int i){ return - 2 * h[i]; };
	auto getB = [&](int i){ return h[i] * h[i] - sw[i] + dp[i]; };
 
	dp[1] = 0;
	update(1, 1, MAXC, Line(getA(1), getB(1)));
 
	for(int i = 2; i <= n; i++)
	{
		dp[i] = h[i] * h[i] + sw[i - 1] + query(h[i], 1, 1, MAXC);
		update(1, 1, MAXC, Line(getA(i), getB(i)));
	}
 
	cout << dp[n] << '\n';
}

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