oj.uz

Submission #1099278

# Submission time Handle Problem Language Result Execution time Memory
1099278 2024-10-11T04:25:12 Z tht2005 Building Bridges (CEOI17_building) C++17
100 / 100
 102 ms 5920 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int N = (int)1e5 + 10;
 
int h[N];
ll s[N], f[N];
 
struct line_t {
	ll k, m;
	ll operator() (ll x) {
		return k * x + m;
	}
	bool operator< (const line_t& rhs) const {
		if(k != rhs.k) return k > rhs.k;
		return m < rhs.m;
	}
	bool operator== (const line_t& rhs) const {
		return k == rhs.k;
	}
};
struct cht {
	deque<line_t> dq;
 
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
 
	bool check(const line_t& a, const line_t& b, const line_t& c) {
		return div(b.m - a.m, a.k - b.k) >= div(c.m - b.m, b.k - c.k);
	}
 
	void add(const line_t& l) {
		while((int)dq.size() > 1 && check(dq[(int)dq.size() - 2], dq.back(), l))
			dq.pop_back();
		dq.push_back(l);
	}
 
	ll query(int x) {
		while((int)dq.size() > 1 && dq[0](x) >= dq[1](x))
			dq.pop_front();
		return dq.front()(x);
	}
};
 
line_t lf[N];
int rt[N];
 
void dq(int l, int r) {
	if(l == r)
		return;
	int m = (l + r) >> 1;
	dq(l, m);
 
	for(int i = l; i <= m; ++i)
		lf[i] = { -2LL * h[i], f[i] + (ll)h[i] * h[i] - s[i] };
	sort(lf + l, lf + m + 1);
	int ptr = unique(lf + l, lf + m + 1) - lf;
 
	cht c;
	for(int i = l; i < ptr; ++i)
		c.add(lf[i]);
 
	for(int i = m + 1; i <= r; ++i)
		rt[i] = i;
	sort(rt + m + 1, rt + r + 1, [&](int i, int j) {
		return h[i] < h[j];
	});
 
	for(int j = m + 1; j <= r; ++j) {
		int i = rt[j];
		f[i] = min(f[i], c.query(h[i]) + (ll)h[i] * h[i] + s[i - 1]);
	}
 
	dq(m + 1, r);
}
 
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 >> s[i];
		s[i] += s[i - 1];
	}
 
	memset(f, 0x3f, sizeof(f));
	f[1] = 0;
	dq(1, n);
 
	cout << f[n];
 
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 5312 KB Output is correct
2 Correct 88 ms 5192 KB Output is correct
3 Correct 91 ms 5392 KB Output is correct
4 Correct 102 ms 5208 KB Output is correct
5 Correct 48 ms 5460 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 88 ms 5312 KB Output is correct
7 Correct 88 ms 5192 KB Output is correct
8 Correct 91 ms 5392 KB Output is correct
9 Correct 102 ms 5208 KB Output is correct
10 Correct 48 ms 5460 KB Output is correct
11 Correct 95 ms 5556 KB Output is correct
12 Correct 95 ms 5200 KB Output is correct
13 Correct 89 ms 5472 KB Output is correct
14 Correct 93 ms 5480 KB Output is correct
15 Correct 42 ms 5920 KB Output is correct
16 Correct 50 ms 5588 KB Output is correct
17 Correct 29 ms 5208 KB Output is correct
18 Correct 29 ms 5212 KB Output is correct