oj.uz

Submission #1100082

# Submission time Handle Problem Language Result Execution time Memory
1100082 2024-10-12T16:20:10 Z tht2005 Building Bridges (CEOI17_building) C++17
30 / 100
 501 ms 6740 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 = 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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 5812 KB Output is correct
2 Correct 472 ms 5720 KB Output is correct
3 Correct 501 ms 5752 KB Output is correct
4 Correct 109 ms 6740 KB Output is correct
5 Correct 383 ms 6676 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -