Submission #45322

#	Time	Username	Problem	Language	Result	Execution time	Memory
45322		Noam527	Building Bridges (CEOI17_building)	C++11	0 / 100	117 ms	3820 KiB

building

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <time.h>
#include <stack>
#include <queue>
#include <random>
#include <fstream>
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;

// 1 for maximum, -1 for minimum
struct cht {
	struct line {
		ll m, b;
		bool q;
		ll nxtm, nxtb;
		line(ll mm = 0, ll bb = 0, bool qq = false) {
			m = mm;
			b = bb;
			q = qq;
			nxtm = nxtb = 9e18;
		}
		bool operator < (const line &x) const {
			if (!q && !x.q)
				return m < x.m;
			if (x.q) {
//				cout << "comparison with line " << -m << " " << -b << endl;
				if (nxtm == (ll)9e18) return false;
//				cout << "has next slope as " << nxtm << endl;
//				cout << (ldb)(b - nxtb) / (nxtm - m) << endl;
				return (b - nxtb) < x.m * (nxtm - m);
			}
			return !(x < *this);
		}
	};

	int sign;
	set<line> h;

	cht(int type = 1) {
		sign = type;
	}
	void upd(set<line>::iterator &it) {
		if (next(it) == h.end()) return;
		line l1 = *it, l2 = *next(it);
		h.erase(it);
		l1.nxtm = l2.m, l1.nxtb = l2.b;
		it = h.insert(l1).first;
	}
	bool ok(set<line>::iterator it) {
		if (it == h.begin() || next(it) == h.end()) return true;
		auto it1 = prev(it), it2 = next(it);
		bool rtn = (it1->b - it->b) * (it2->m - it->m) < (it->b - it2->b) * (it->m - it1->m);
		if (!rtn) {
//			cout << "erasing " << sign * it->m << " " << sign * it->b << endl;
			h.erase(it);
			upd(it1);
		}
		return rtn;
	}
	void insert(ll constant, ll slope) {
		line l(sign * slope, sign * constant);
		auto it = h.insert(l).first;
		if (!ok(it)) return;
		upd(it);
		if (it != h.begin()) upd(--it), ++it;
		if (it != h.begin()) while (!ok(prev(it)));
		if (next(it) != h.end()) while (!ok(next(it)));
	}
	ll query(ll x) {
//		cout << "looking for optimum on x " << x << endl;
		line l(x, 0, true);
		auto it = h.lower_bound(l);
//		cout << "optimum for x " << x << " is line ";
//		cout << sign * it->m << " " << sign * it->b << endl;
		return sign * (x * it->m + it->b);
	}
};

int n;
vector<ll> h, w, sw, dp;
cht c(-1);

int main() {
	fast;
	cin >> n;
	h.resize(n);
	w.resize(n);
	sw.resize(n);
	dp.resize(n);
	for (auto &i : h) cin >> i;
	for (auto &i : w) cin >> i;
	sw[0] = w[0];
	for (int i = 1; i < n; i++) sw[i] = sw[i - 1] + w[i];

	dp[0] = 0;
//	cout << "for i " << 0 << " inserted " << dp[0] + h[0] * h[0] - sw[0] << " " << -2 * h[0] << endl;
	c.insert(dp[0] + h[0] * h[0] - sw[0], -2 * h[0]);
	for (int i = 1; i < n; i++) {
		dp[i] = c.query(h[i]) + sw[i - 1] + h[i] * h[i];
//		cout << "for i " << i << " inserted " << -2 * h[i] << " " << dp[i] + h[i] * h[i] - sw[i] << endl;
		c.insert(dp[i] + h[i] * h[i] - sw[i], -2 * h[i]);
	}
//	for (int i = 0; i < n; i++) cout << dp[i] << " "; cout << endl;
	cout << dp.back() << endl;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40