Submission #412979

#	Time	Username	Problem	Language	Result	Execution time	Memory
412979		dynam1c	Building Bridges (CEOI17_building)	C++17	100 / 100	59 ms	6044 KiB

building

//#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40