oj.uz

Submission #988646

# Submission time Handle Problem Language Result Execution time Memory
988646 2024-05-25T11:20:01 Z Aviansh Building Bridges (CEOI17_building) C++17
100 / 100
 76 ms 10576 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

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;
}

set<Line> cht;
ll h[100001], w[100001], tot = 0, dp[100001];

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_line(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(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> h[i];
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
		tot += w[i];
	}

	dp[1] = -w[1];
	for (int i = 2; i <= n; i++) {
		add_line(-2 * h[i - 1], dp[i - 1] + h[i - 1] * h[i - 1]);
		dp[i] = query(h[i]) - w[i] + h[i] * h[i];
	}

	cout << tot + dp[n];
	return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2864 KB Output is correct
2 Correct 58 ms 2884 KB Output is correct
3 Correct 57 ms 2884 KB Output is correct
4 Correct 58 ms 2648 KB Output is correct
5 Correct 51 ms 4248 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 58 ms 2864 KB Output is correct
7 Correct 58 ms 2884 KB Output is correct
8 Correct 57 ms 2884 KB Output is correct
9 Correct 58 ms 2648 KB Output is correct
10 Correct 51 ms 4248 KB Output is correct
11 Correct 51 ms 2828 KB Output is correct
12 Correct 59 ms 2648 KB Output is correct
13 Correct 36 ms 2648 KB Output is correct
14 Correct 56 ms 2672 KB Output is correct
15 Correct 76 ms 10576 KB Output is correct
16 Correct 49 ms 4260 KB Output is correct
17 Correct 17 ms 2648 KB Output is correct
18 Correct 15 ms 2652 KB Output is correct