Submission #1100082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100082		tht2005	Building Bridges (CEOI17_building)	C++17	30 / 100	501 ms	6740 KiB

building

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = (int)1e5 + 10;

set<pair<int, int>> S[50];
void add(int w, int h, int i) {
	w += 22;
	S[w].emplace(h, i);
}

vector<int> find_opt(int w, double h) {
	w += 22;
	auto it = S[w].lower_bound(make_pair(h, -1));
	vector<int> res;
	if(it != S[w].end())
		res.push_back(it->second);
	if(it != S[w].begin())
		res.push_back((--it)->second);
	return res;
}

int h[N], w[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin >> h[i];
	for(int i = 1; i <= n; ++i)
		cin >> w[i];

	ll totw = 0;
	for(int i = 2; i < n; ++i)
		totw += w[i];
	
	ll res = (ll)(h[1] - h[n]) * (h[1] - h[n]);
	for(int i = 2; i < n; ++i)
		res = min(res, (ll)(h[1] - h[i]) * (h[1] - h[i]) - w[i] + (ll)(h[i] - h[n]) * (h[i] - h[n]));

	for(int i = 3; i < n; ++i) {
		// add (i-1)
		add(w[i - 1], h[i - 1], i - 1);
		// query best(i)
		// = (h[j] - h[1])^2 - w[j] + (h[j] - h[i])^2
		// dao ham theo h[j]: 2 * (h[j] - h[1]) + 2 * (h[j] - h[i])
		// cuc tri: dao ham = 0, suy ra h[j] = (h[1] + h[i]) / 2
		for(int ww = -20; ww <= 20; ++ww) {
			vector<int> ret(find_opt(ww, (h[1] + h[i]) / 2.));
			for(int j : ret) {
				res = min(res, (ll)(h[j] - h[1]) * (h[j] - h[1]) - w[j] + (ll)(h[i] - h[j]) * (h[i] - h[j]) + (ll)(h[i] - h[n]) * (h[i] - h[n]) - w[i]);
			}
		}
	}

	cout << res + totw;

	return 0;
}

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