제출 #1224787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224787		radodododo	Building Bridges (CEOI17_building)	C++20	100 / 100	67 ms	7608 KiB

building

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

long long inf = 1e18;

struct line {
	long long k, b;
	line(long long k = 0, long long b = inf) {
		this->k = k;
		this->b = b;
	}
	long long val(long long x) {
		return k * x + b;
	}
	bool operator==(line a) {
		return a.b == b && a.k == k;
	}
};

line pust;

struct node {
	line lin;
	long long l, r;
	node(line lin = pust, long long l = -1, long long r = -1) {
		this->lin = lin;
		this->l = l;
		this->r = r;
	}
};

vector<node> li_chao(1);

void add_line(long long i, long long l, long long r, line new_l) {
	if (li_chao[i].lin == pust) {
		li_chao[i].lin = new_l;
		return;
	}
	long long mid = (l + r) / 2;
	if (li_chao[i].lin.val(mid) > new_l.val(mid)) {
		swap(new_l, li_chao[i].lin);
	}
	if (l + 1 == r) {
		return;
	}
	if (new_l.k > li_chao[i].lin.k) {
		if (li_chao[i].l == -1) {
			li_chao[i].l = li_chao.size();
			li_chao.push_back({});
		}
		add_line(li_chao[i].l, l, mid, new_l);
	}
	else {
		if (li_chao[i].r == -1) {
			li_chao[i].r = li_chao.size();
			li_chao.push_back({});
		}
		add_line(li_chao[i].r, mid, r, new_l);
	}
}

long long get_min(long long i, long long l, long long r, long long qx) {
	if (l + 1 == r) {
		return li_chao[i].lin.val(qx);
	}
	long long mid = (l + r) / 2;
	if (qx < mid && li_chao[i].l != -1) {
		return min(li_chao[i].lin.val(qx), get_min(li_chao[i].l, l, mid, qx));
	}
	if (mid <= qx && li_chao[i].r != -1) {
		return min(li_chao[i].lin.val(qx), get_min(li_chao[i].r, mid, r, qx));
	}
	return li_chao[i].lin.val(qx);
}

int main() {
	long long n;
	long long R = 1e6 + 10;
	cin >> n;
	vector<long long> h(n), w(n);
	for (long long i = 0; i < n; i++) {
		cin >> h[i];
	}
	for (long long i = 0; i < n; i++) {
		cin >> w[i];
	}
	vector<long long> dp(n);
	dp[0] = 0;
	vector<long long> pref(n);
	pref[0] = w[0];
	for (long long i = 1; i < n; i++) {
		pref[i] = pref[i - 1] + w[i];
	}
	add_line(0, 0, R, line(-2 * h[0], dp[0] + h[0] * h[0] - pref[0]));
	for (long long i = 1; i < n; i++) {
		long long mni = get_min(0, 0, R, h[i]);
		dp[i] = mni + pref[i] - w[i] + h[i] * h[i];
		add_line(0, 0, R, line(-2 * h[i], dp[i] + h[i] * h[i] - pref[i]));
	}
	cout << dp[n - 1];
}

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