oj.uz

Submission #412979

# Submission time Handle Problem Language Result Execution time Memory
412979 2021-05-27T22:08:17 Z dynam1c Building Bridges (CEOI17_building) C++17
100 / 100
 59 ms 6044 KB 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;

#define endl "\n"
#define all(c) (c).begin(),(c).end()

// when you ponder, divide and conquer

constexpr ll INF = 1LL<<62;
struct line {
	ll m, b;
	ll eval(ll x) {
		return m*x + b;
	}
	ld ix(line o) {
		return (ld) (b - o.b) / (o.m - m);
	}
	line() : m(0), b(-INF) {}
	line(ll m, ll b) : m(m), b(b) {}
};

struct node {
	node *l, *r;
	line f;
	node() : l(0), r(0), f() {}
};

struct LiChao {
	deque<node> buf;
	node *create() {
		buf.emplace_back();
		return &buf.back();
	}
	node *root;
	ll n;
	LiChao(ll n) : n(n), root(0) {}
	void update(node *&v, ll l, ll r, line f) {
		if (!v) {
			v = create();
			v->f = f;
			return;
		}
		ll m = l+r>>1;
		if (f.eval(m) > v->f.eval(m)) swap(f, v->f);
		if (r-l <= 1) return;
		if (f.eval(l) > v->f.eval(l))
			update(v->l, l, m, f);
		else
			update(v->r, m, r, f);
	}
	void update(line f) {
		update(root, -n, n, f);
	}
	ll query(node *v, ll l, ll r, ll x) {
		if (!v) return -INF;
		ll m = l+r>>1;
		return max(v->f.eval(x), x < m ? query(v->l, l, m, x) : query(v->r, m, r, x));
	}
	ll query(ll x) {
		return query(root, -n, n, x);
	}
};

signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	vector<ll> h(n), pref(n+1);
	for (int i = 0; i < n; i++)
		cin >> h[i];
	for (int i = 0, x; i < n; i++)
		cin >> x, pref[i+1] = pref[i] + x;

	LiChao lc(1e6+5);
	ll ans = 0;

	lc.update({2 * h[0], -h[0]*h[0] + pref[1]});
	for (int i = 1; i < n; i++) {
		ll f = -lc.query(h[i]) + pref[i] + h[i]*h[i];
		ans = f;
		lc.update({2 * h[i], -h[i]*h[i] - f + pref[i+1]});
	}
	cout << ans << endl;
		
}
/* --- PSolving ---
 * Simplifying (getting rid of variables, conditions, code logic, etc.)
 * Reframing
 * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.)
 * Inducing
 * Divide and conquer
 * Working backwards
 * Visual intuition
 * !! Reductions don't have to be specializations, they can be generalizations
 */

Compilation message

building.cpp: In constructor 'LiChao::LiChao(ll)':
building.cpp:41:5: warning: 'LiChao::n' will be initialized after [-Wreorder]
   41 |  ll n;
      |     ^
building.cpp:40:8: warning:   'node* LiChao::root' [-Wreorder]
   40 |  node *root;
      |        ^~~~
building.cpp:42:2: warning:   when initialized here [-Wreorder]
   42 |  LiChao(ll n) : n(n), root(0) {}
      |  ^~~~~~
building.cpp: In member function 'void LiChao::update(node*&, ll, ll, line)':
building.cpp:49:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   ll m = l+r>>1;
      |          ~^~
building.cpp: In member function 'll LiChao::query(node*, ll, ll, ll)':
building.cpp:62:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |   ll m = l+r>>1;
      |          ~^~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3344 KB Output is correct
2 Correct 47 ms 3268 KB Output is correct
3 Correct 59 ms 3284 KB Output is correct
4 Correct 43 ms 2948 KB Output is correct
5 Correct 36 ms 5128 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 47 ms 3344 KB Output is correct
7 Correct 47 ms 3268 KB Output is correct
8 Correct 59 ms 3284 KB Output is correct
9 Correct 43 ms 2948 KB Output is correct
10 Correct 36 ms 5128 KB Output is correct
11 Correct 51 ms 3776 KB Output is correct
12 Correct 54 ms 3912 KB Output is correct
13 Correct 43 ms 3024 KB Output is correct
14 Correct 51 ms 3984 KB Output is correct
15 Correct 35 ms 6044 KB Output is correct
16 Correct 35 ms 5184 KB Output is correct
17 Correct 26 ms 2952 KB Output is correct
18 Correct 26 ms 2912 KB Output is correct