Submission #444027

#	Time	Username	Problem	Language	Result	Execution time	Memory
444027		penguinhacker	Building Bridges (CEOI17_building)	C++14	100 / 100	83 ms	8156 KiB

building

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

#define ll long long
#define ar array

const int mxN=1e5;
const ll INF=1e18;
int n, h[mxN], w[mxN];

struct Line {
	ll m, b;
	mutable ll p;
	bool operator<(const Line& o) const { return m>o.m; }
	bool operator<(ll x) const { return p<x; }
};

set<Line, less<>> s;

ll ix(set<Line>::iterator l1, set<Line>::iterator l2) {
	assert(l1->m>l2->m);
	ll x=l2->b-l1->b, y=l1->m-l2->m;
	return x>=0?(x+y-1)/y:x/y;
}

bool bad(set<Line>::iterator it) {
	assert(it!=s.end());
	return it!=s.begin()&&next(it)!=s.end()&&ix(it, next(it))<=ix(prev(it), it);
}

void ins(ll m, ll b) {
	Line cur={m, b};
	auto it=s.lower_bound(cur);
	if (it!=s.end()&&it->m==m) {
		if (it->b<=b)
			return;
		it=s.erase(it);
	}
	it=s.insert(it, cur);
	if (bad(it)) {
		s.erase(it);
		return;
	}
	while(it!=s.begin()&&bad(prev(it))) s.erase(prev(it));
	while(next(it)!=s.end()&&bad(next(it))) s.erase(next(it));
	it->p=it==s.begin()?-INF:ix(prev(it), it);
	if (next(it)!=s.end())
		next(it)->p=ix(it, next(it));
}

ll qry(ll x) {
	auto it=s.lower_bound(x);
	if (it==s.end()||it->p>x) {
		assert(it!=s.begin());
		--it;
	}
	return it->m*x+it->b;
}

ll sq(int i) {
	return (ll)h[i]*h[i];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=0; i<n; ++i)
		cin >> h[i];
	for (int i=0; i<n; ++i)
		cin >> w[i];
	ins(-2*h[0], sq(0));
	for (int i=1; i<n-1; ++i) {
		ll dp=qry(h[i])-w[i]+sq(i);
		ins(-2*h[i], dp+sq(i));
	}
	ll ans=qry(h[n-1])+sq(n-1);
	cout << ans+accumulate(w+1, w+n-1, 0ll);
	return 0;
}

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