Submission #166630

#	Time	Username	Problem	Language	Result	Execution time	Memory
166630		thiago4532	Building Bridges (CEOI17_building)	C++17	100 / 100	228 ms	10560 KiB

building

#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int maxn = 1e5 + 10;
int h[maxn], pref[maxn], w[maxn];
int n, dp[maxn];

bool flag = 0;
struct line {
	int a, b;
	double x;

	bool operator<(line const& l) const {
		if(flag == 0) return a > l.a;
		else return x < l.x;
	}
};

typedef set<line>::iterator sit;

set<line> lines;

bool hasPrev(sit it)
{
	return (it != lines.begin());
}

bool hasNext(sit it)
{
	return (next(it) != lines.end() && ++it != lines.end());
}

template<typename Arg>
bool bad(Arg&& l1, Arg&& l2, Arg&& l3) {
	return (l2.a - l1.a)*(l3.b - l1.b) >= (l3.a -  l1.a)*(l2.b - l1.b);
}

double intersect(line const& l1, line const& l2) {
	return (double)(l2.b-l1.b)/(l1.a-l2.a);
}

void get_x(sit it) {
	if (hasPrev(it))
	{
		line l = *it;

		l.x = intersect(*prev(it), *it);

		lines.erase(it); lines.insert(l);
	}
}

void add(line const& l) {
	auto it = lines.lower_bound(l);
	if(it != lines.end() && it->a == l.a){
		if(it->b <= l.b) return;
		lines.erase(it);
	}

	lines.insert(l);
	it = lines.find(l);

	if (hasPrev(it) && hasNext(it) && bad(*prev(it), *it, *next(it))) {
		lines.erase(it);
		return;
	}

	while(hasNext(it) && hasNext(next(it)) && bad(*it, *next(it), *next(next(it)))) 
		lines.erase(next(it));

	while(hasPrev(it) && hasPrev(prev(it)) && bad(*prev(prev(it)), *prev(it), *it))
		lines.erase(prev(it));

	get_x(it);
	if (hasNext(it)) get_x(next(it));
}

inline int f(line const& l, int x) {
	return l.a*x + l.b;
}

int query(int x) {
	flag = true;
	auto it = lines.upper_bound({0, 0, (double)x});
	flag = false;
	it--;
	return f(*it, x);
}


int32_t main() {
	cin >> n;
	for(int i=1;i<=n;i++)
		cin >> h[i];

	for(int i=1;i<=n;i++)
		cin >> w[i], pref[i] = pref[i-1] + w[i];

	dp[1] = 0;
	add({-2*h[1], h[1]*h[1] + dp[1] - pref[1]});

	for(int i=2;i<=n;i++) {
		// dp[i] = 0x3f3f3f3f3f3f3f3f;

		// for(int j=1;j<i;j++) {
		// 	dp[i] = min(dp[i], dp[j] - pref[j] + h[j]*h[j] - 2*h[j] * h[i]);
		// }

		dp[i] = query(h[i]);

		dp[i] += h[i]*h[i] + pref[i-1];
		add({-2*h[i], h[i]*h[i] + dp[i] - pref[i]});
	}
	cout << dp[n] << "\n";
	return 0;
}

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