oj.uz

Submission #1099242

# Submission time Handle Problem Language Result Execution time Memory
1099242 2024-10-11T02:49:04 Z tht2005 Building Bridges (CEOI17_building) C++17
100 / 100
 43 ms 9476 KB 
#include <bits/stdc++.h>
using namespace std;

/**
 * Author: Simon Lindholm
 * Date: 2017-04-20
 * License: CC0
 * Source: own work
 * Description: Container where you can add lines of the form kx+m, and query maximum values at points x.
 *  Useful for dynamic programming (``convex hull trick'').
 * Time: O(\log N)
 * Status: stress-tested
 */

typedef long long ll;

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};

const int N = (int)1e5 + 10;

int h[N];
ll s[N], f[N];

LineContainer L;

void add(int i) {
	L.add(2LL * h[i], -f[i] - (ll)h[i] * h[i] + s[i]);
}

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

	f[1] = 0;
	add(1);
	for(int i = 2; i <= n; ++i) {
		f[i] = -L.query(h[i]) + (ll)h[i] * h[i] + s[i - 1];
		add(i);
	}

	cout << f[n];

	return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3412 KB Output is correct
2 Correct 30 ms 3420 KB Output is correct
3 Correct 29 ms 3420 KB Output is correct
4 Correct 28 ms 3152 KB Output is correct
5 Correct 25 ms 4444 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 504 KB Output is correct
6 Correct 32 ms 3412 KB Output is correct
7 Correct 30 ms 3420 KB Output is correct
8 Correct 29 ms 3420 KB Output is correct
9 Correct 28 ms 3152 KB Output is correct
10 Correct 25 ms 4444 KB Output is correct
11 Correct 26 ms 3420 KB Output is correct
12 Correct 29 ms 3412 KB Output is correct
13 Correct 22 ms 3404 KB Output is correct
14 Correct 29 ms 3584 KB Output is correct
15 Correct 43 ms 9476 KB Output is correct
16 Correct 25 ms 4436 KB Output is correct
17 Correct 14 ms 3416 KB Output is correct
18 Correct 14 ms 3420 KB Output is correct