Submission #45255

#	Time	Username	Problem	Language	Result	Execution time	Memory
45255		qoo2p5	Building Bridges (CEOI17_building)	C++17	30 / 100	3040 ms	7164 KiB

building

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y > x) {
		x = y;
		return 1;
	}
	return 0;
}

void run();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
	return 0;
}

const int N = (int) 1e5 + 123;
const int M = 1 << 20;

int n;
ll h[N], w[N];
ll dp[N], p[N];

struct Line {
	ll k, b;
	
	ll val(ll x) {
		return k * x + b;
	}
};

vector<Line> tmp;

void add(const Line &l) {
	tmp.pb(l);
}

ll get(ll x) {
	ll res = LINF;
	for (auto &it : tmp) {
		mini(res, it.val(x));
	}
	return res;
}

void update(int i) {
	add({-2 * h[i], dp[i] - p[i] + h[i] * h[i]});
}

ll calc(int i) {
	return get(h[i]) + h[i] * h[i] + p[i - 1];
}

void run() {
	cin >> n;
	rep(i, 0, n) {
		cin >> h[i];
	}
	rep(i, 0, n) {
		cin >> w[i];
	}
	
	partial_sum(w, w + n, p);
	rep(i, 0, n) {
		dp[i] = LINF;
	}
	dp[0] = 0;
	update(0);
	rep(i, 1, n) {
		dp[i] = calc(i);
		update(i);
	}
	
	cout << dp[n - 1] << "\n";
}

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