Submission #1247391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247391		MateiKing80	Building Bridges (CEOI17_building)	C++20	100 / 100	51 ms	8372 KiB

building

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

const int inf = 1e17;

/*
dp[i] costu minim pana la i
dp[i] = min(dp[j] + (hi - hj)^2 + w_i-1 + .. + w_j+1)
dp[i] = min((dp[j] + hj^2 - w_1 - w_2 - .. - w_j) + (-2hj) * hi) + w_1 + w_2 + ... + w_i-1 + h_i^2
LiChAo
*/

const int N = 1e6 + 1;

struct line {
	int a, b;
	int operator() (int x) {
		return a * x + b;
	}
};

struct node {
	int fst = -1, fdr = -1;
	line l;
};

vector<node> aint;
bool gol = true;

void update(int pos, int st, int dr, line l) {
	int mid = (st + dr) / 2;
	if (aint[pos].l(mid) > l(mid))
		swap(aint[pos].l, l);
	if (st == dr)
		return;
	if (aint[pos].l(st) > l(st)) {
		if (aint[pos].fst == -1) {
			aint[pos].fst = aint.size();
			aint.push_back({-1, -1, l});
			return;
		}
		update(aint[pos].fst, st, mid, l);
	} else if (aint[pos].l(dr) > l(dr)) {
		if (aint[pos].fdr == -1) {
			aint[pos].fdr = aint.size();
			aint.push_back({-1, -1, l});
			return;
		}
		update(aint[pos].fdr, mid + 1, dr, l);
	}
}

int query(int pos, int st, int dr, int x) {
	int mid = (st + dr) / 2;
	if (st == dr)
		return aint[pos].l(x);
	if (x <= mid) {
		if (aint[pos].fst == -1)
			return aint[pos].l(x);
		return min(aint[pos].l(x), query(aint[pos].fst, st, mid, x));
	} else {
		if (aint[pos].fdr == -1)
			return aint[pos].l(x);
		return min(aint[pos].l(x), query(aint[pos].fdr, mid + 1, dr, x));
	}
}

int getMin(int x) {
	return query(0, 1, N, x);
}

void addLine(line x) {
	if (gol) {
		aint.push_back({-1, -1, x});
		gol = false;
	}
	else
		update(0, 1, N, x);
}

signed main() {
	int n;
	cin >> n;
	vector<int> dp(n + 1), coef(n + 1), inm(n + 1), w(n + 1), h(n + 1);
	for (int i = 1; i <= n; i ++)
		cin >> h[i];
	for (int i = 1; i <= n; i ++)
		cin >> w[i];
	dp[1] = 0;
	coef[1] = h[1] * h[1] - w[1];
	inm[1] = -2 * h[1];
	addLine({inm[1], coef[1]});
	int sumw = 0;
	for (int i = 2; i <= n; i ++) {
		sumw += w[i - 1];
		int mn = getMin(h[i]);
		dp[i] = mn + sumw + h[i] * h[i];
		coef[i] = dp[i] + h[i] * h[i] - sumw - w[i];
		inm[i] = -2 * h[i];
		addLine({inm[i], coef[i]});
	}
	cout << dp[n] << '\n';
}

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