oj.uz

Submission #1040065

# Submission time Handle Problem Language Result Execution time Memory
1040065 2024-07-31T15:28:22 Z mat_jur Building Bridges (CEOI17_building) C++17
100 / 100
 63 ms 11352 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
using ld = long double;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

struct Line {
	bool type;
	double x;
	ll m, c;
};

bool operator<(Line l1, Line l2) {
	if (l1.type || l2.type) return l1.x < l2.x;
	return l1.m > l2.m;
}


struct CHT {
	set<Line> cht;

	bool has_prev(set<Line>::iterator it) { return it != cht.begin(); }
	bool has_next(set<Line>::iterator it) {
		return it != cht.end() && next(it) != cht.end();
	}

	double intersect(set<Line>::iterator l1, set<Line>::iterator l2) {
		return (double)(l1->c - l2->c) / (l2->m - l1->m);
	}

	void calc_x(set<Line>::iterator it) {
		if (has_prev(it)) {
			Line l = *it;
			l.x = intersect(prev(it), it);
			cht.insert(cht.erase(it), l);
		}
	}

	bool bad(set<Line>::iterator it) {
		if (has_next(it) && next(it)->c <= it->c) return true;
		return (has_prev(it) && has_next(it) &&
				intersect(prev(it), next(it)) <= intersect(prev(it), it));
	}

	void add(ll m, ll c) {
		set<Line>::iterator it;

		it = cht.lower_bound({0, 0, m, c});
		if (it != cht.end() && it->m == m) {
			if (it->c <= c) return;
			cht.erase(it);
		}

		it = cht.insert({0, 0, m, c}).first;
		if (bad(it)) cht.erase(it);
		else {
			while (has_prev(it) && bad(prev(it))) cht.erase(prev(it));
			while (has_next(it) && bad(next(it))) cht.erase(next(it));

			if (has_next(it)) calc_x(next(it));
			calc_x(it);
		}
	}

	ll query(ll h) {
		Line l = *prev(cht.upper_bound({1, (double)h, 0, 0}));
		return l.m * h + l.c;
	}
};


int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n;
	cin >> n;
	vector<int> h(n), w(n);
	for (int &x : h) cin >> x;
	for (int &x : w) cin >> x;

	vector<ll> pref(n);
	for (int i = 0; i < n; ++i)
		pref[i] = w[i] + (i-1 < 0 ? 0 : pref[i-1]);

	vector<ll> dp(n);

	CHT cht;

	for (int j = 0; j < n; ++j) {
		if (j > 0)
			dp[j] = ll(h[j])*h[j] + (j-1 < 0 ? 0 : pref[j-1]) + cht.query(h[j]);
		else 
			dp[j] = 0;

		cht.add(-2 * h[j], ll(h[j]) * h[j] + dp[j] - pref[j]);
	}

	cout << dp[n-1] << '\n';

	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3920 KB Output is correct
2 Correct 44 ms 3920 KB Output is correct
3 Correct 44 ms 3900 KB Output is correct
4 Correct 45 ms 3676 KB Output is correct
5 Correct 39 ms 5276 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 44 ms 3920 KB Output is correct
7 Correct 44 ms 3920 KB Output is correct
8 Correct 44 ms 3900 KB Output is correct
9 Correct 45 ms 3676 KB Output is correct
10 Correct 39 ms 5276 KB Output is correct
11 Correct 39 ms 3932 KB Output is correct
12 Correct 45 ms 3672 KB Output is correct
13 Correct 27 ms 3796 KB Output is correct
14 Correct 51 ms 4052 KB Output is correct
15 Correct 63 ms 11352 KB Output is correct
16 Correct 39 ms 5184 KB Output is correct
17 Correct 12 ms 3672 KB Output is correct
18 Correct 11 ms 3676 KB Output is correct