Submission #504608

#	Time	Username	Problem	Language	Result	Execution time	Memory
504608		dutinmeow	Building Bridges (CEOI17_building)	C++17	100 / 100	79 ms	9688 KiB

building

#include <bits/stdc++.h>
using namespace std;

bool _Line_Comp_State; 
struct Line {
	// k is slope, m is intercept, p is intersection point
	mutable long long k, m, p;
	bool operator<(const Line& o) const {
		return _Line_Comp_State ? p < o.p : k < o.k;
	}
};

struct LineContainer : multiset<Line> {
	long long div(long long a, long long b) { return a / b - ((a ^ b) < 0 && a % b); }
	
	bool isect(iterator x, iterator y) {
		if (y == end()) { 
			x->p = LLONG_MAX; 
			return false; 
		}
		if (x->k == y->k) 
			x->p = x->m > y->m ? LLONG_MAX : -LLONG_MAX;
		else 
			x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}

	void add(long long k, long long 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));
	}
	
	long long query(long long x) {
		assert(!empty());
		_Line_Comp_State = 1; 
		auto l = *lower_bound({0, 0, x}); 
		_Line_Comp_State = 0;
		return l.k * x + l.m;
	}
};

const int MAX = 1e5 + 5;

int N;
long long H[MAX], W[MAX], dp[MAX];

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) 
		cin >> H[i];
	for (int i = 1; i <= N; i++) {
		cin >> W[i];
		W[i] += W[i - 1];
	}

	LineContainer lc;
	for (int i = 1; i <= N; i++) {
		if (i != 1)
			dp[i] = -lc.query(H[i]) + W[i - 1] + H[i] * H[i];
		lc.add(2 * H[i], -(dp[i] - W[i] + H[i] * H[i]));
	}
	//for (int i = 1; i <= N; i++)
	//	cout << dp[i] << " \n"[i == N];
	cout << dp[N] << '\n';
}

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