Submission #113900

#	Time	Username	Problem	Language	Result	Execution time	Memory
113900		MAMBA	Building Bridges (CEOI17_building)	C++17	100 / 100	155 ms	19524 KiB

building

#include <bits/stdc++.h> 

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef complex<ld> point;
typedef pair<ld , ld> pld;
typedef vector<ll> vi;

inline void fileIO(string s) {
	//	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }

constexpr int N = 1e5 + 10;
constexpr int MOD = 1e9 + 7;

template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }

class ConvexHullDynamic {
	typedef long double coef_t, coord_t, val_t;
	//Line 'y=a*x+b' represented by 2 coefficients 'a' and 'b'
private:
	struct Line {
		coef_t a, b;
		long double xLeft;
		enum Type { line, maxQuery, minQuery } type;
		coord_t val;
		explicit Line(coef_t aa = 0, coef_t bb = 0) : a(aa), b(bb), xLeft(-INFINITY), type(Type::line), val(0) {}
		val_t valueAt(coord_t x) const { return a * x + b; }
		friend bool areParallel(const Line& l1, const Line& l2) { return l1.a == l2.a; }
		friend long double intersectX(const Line& l1, const Line& l2) { return areParallel(l1, l2) ? INFINITY : 1.0*(l2.b - l1.b) / (l1.a - l2.a); }
		bool operator<(const Line& l2) const {
			if (l2.type == line) return this->a < l2.a;
			if (l2.type == maxQuery) return this->xLeft < l2.val;
			if (l2.type == minQuery) return this->xLeft < l2.val;
			assert(0);
			return false;
		}
	};
private:
	bool            isMax; //whether or not saved envelope is top(search of max value)
	std::set<Line>  hull;  //envelope itself
private:
	bool hasPrev(std::set<Line>::iterator it) { return it != hull.begin(); }
	bool hasNext(std::set<Line>::iterator it) { return it != hull.end() && std::next(it) != hull.end(); }
	bool irrelevant(const Line& l1, const Line& l2, const Line& l3) { return intersectX(l1, l3) <= intersectX(l1, l2); }
	bool irrelevant(std::set<Line>::iterator it) {
		return hasPrev(it) && hasNext(it) && ((isMax && irrelevant(*std::prev(it), *it, *std::next(it)))
			|| (!isMax && irrelevant(*std::next(it), *it, *std::prev(it))));
	}
	std::set<Line>::iterator updateLeftBorder(std::set<Line>::iterator it) {
		if ((isMax && !hasPrev(it)) || (!isMax && !hasNext(it))) return it;
		long double val = intersectX(*it, isMax ? *std::prev(it) : *std::next(it));
		Line buf(*it);
		it = hull.erase(it), buf.xLeft = val, it = hull.insert(it, buf);
		return it;
	}
public:
	explicit ConvexHullDynamic() : isMax(true) {} // true is for max and false is for min
	void addLine(coef_t a, coef_t b) {
		Line l3 = Line(a, b);
		auto it = hull.lower_bound(l3);
		if (it != hull.end() && areParallel(*it, l3)) {
			if ((isMax && it->b < b) || (!isMax && it->b > b)) it = hull.erase(it);
			else return;
		}
		it = hull.insert(it, l3);
		if (irrelevant(it)) { hull.erase(it); return; }
		while (hasPrev(it) && irrelevant(std::prev(it))) hull.erase(std::prev(it));
		while (hasNext(it) && irrelevant(std::next(it))) hull.erase(std::next(it));
		it = updateLeftBorder(it);
		if (hasPrev(it)) updateLeftBorder(std::prev(it));
		if (hasNext(it)) updateLeftBorder(std::next(it));
	}
	val_t getBest(coord_t x) const {
		Line q;
		q.val = x, q.type = isMax ? Line::Type::maxQuery : Line::Type::minQuery;
		auto bestLine = hull.lower_bound(q);
		if (isMax) --bestLine;
		return bestLine->valueAt(x);
	}
} ziba;

int n;
long double h[N], psum[N], w[N], dp[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	rep(i , 0 , n) 
		cin >> h[i];
	rep(i , 0 , n) {
		cin >> w[i];
		psum[i] = w[i];
		if (i) psum[i] += psum[i - 1];
	}

	ziba.addLine(2 * h[0] , -(dp[0] - psum[0] + h[0] * h[0]));

	rep(i ,1  ,n) {
		dp[i] = -(ziba.getBest(h[i]) - ( psum[i - 1] + h[i] * h[i]));
		ziba.addLine(2 * h[i] , -(dp[i] - psum[i] + h[i] * h[i]));
	}
	cout << (ll)dp[n - 1] << endl;

	return 0;
}

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