Submission #1090714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090714		xnqs	Building Bridges (CEOI17_building)	C++17	100 / 100	79 ms	66584 KiB

building

// dp[1] = 0
// dp[i] = min(dp[j] + (h[i]-h[j])^2 + pfx[i-1] - pfx[j])
// dp[i] = min(dp[j] + h[i]^2 - 2*h[i]*h[j] + h[j]^2 + pfx[i-1] - pfx[j])
// dp[i] = pfx[i-1] + h[i]^2 + min(dp[j] - 2*h[i]*h[j] + h[j]^2 - pfx[j])
//
//         --------i--------       ----ij------   ------------j----------
// dp[i] = pfx[i-1] + h[i]^2 + min(-2*h[i]*h[j] + dp[j] + h[j]^2 - pfx[j])

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>

struct Line {
	int64_t m, b;
	Line():
		m(0), b(0x3f3f3f3f3f3f3f3f) {}
	Line(int64_t m, int64_t b):
		m(m), b(b) {}

	int64_t operator() (int x) {
		return m*x + b;
	}
};

class LiChaoTree {
private:
	int n;
	std::vector<Line> tree;
public:
	LiChaoTree(int n): n(n) {
		tree.assign(4*n+1,Line());
	}

	void add_line(int node, int l, int r, Line line) {
		if (l+1==r) {
			if (tree[node](l) > line(l)) {
				tree[node] = line;
			}
			return;
		}

		int m = (l+r)>>1;
		if (tree[node].m > line.m) {
			std::swap(tree[node],line);
		}
		if (tree[node](m) > line(m)) {
			std::swap(tree[node],line);
			add_line(node<<1|1,m,r,line);
		}
		else {
			add_line(node<<1,l,m,line);
		}
	}

	int64_t query(int node, int l, int r, int x) {
		if (l+1==r) {
			return tree[node](x);
		}

		int m = (l+r)>>1;
		if (x<m) {
			return std::min(tree[node](x), query(node<<1,l,m,x));
		}
		else {
			return std::min(tree[node](x), query(node<<1|1,m,r,x));
		}
	}
};

int x;
int height[100005];
int cost[100005];
int64_t pfx_cost[100005];
int64_t dp[100005];

int main() {
	std::cin >> x;
	for (int i = 1; i <= x; i++) {
		std::cin >> height[i];
	}
	for (int i = 1; i <= x; i++) {
		std::cin >> cost[i];
		pfx_cost[i] = pfx_cost[i-1] + cost[i];
	}

	LiChaoTree tree(1000005);
	for (int i = 1; i <= x; i++) {
		if (i==1) {
			dp[i] = 0;
		}
		else {
			dp[i] = pfx_cost[i-1] + 1LL*height[i]*height[i] + tree.query(1,0,1000001,height[i]);
		}
		tree.add_line(1,0,1000001,Line(-2LL*height[i],dp[i]+1LL*height[i]*height[i]-pfx_cost[i]));
	}

	std::cout << dp[x] << "\n";
}

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