oj.uz

Submission #1100078

# Submission time Handle Problem Language Result Execution time Memory
1100078 2024-10-12T16:07:04 Z tht2005 Building Bridges (CEOI17_building) C++17
0 / 100
 480 ms 6992 KB 
#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 = 1; 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);
		// 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[n]) * (h[i] - h[n]) - w[i]);
			}
		}
	}

	cout << res + totw;

	return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 6932 KB Output is correct
2 Correct 474 ms 6992 KB Output is correct
3 Incorrect 480 ms 6916 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -