Submission #531418

#	Time	Username	Problem	Language	Result	Execution time	Memory
531418		blue	Building Bridges (CEOI17_building)	C++17	100 / 100	58 ms	36676 KiB

building

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
#define sz(x) int(x.size())

const int mxh = (1<<20);
const ll INF = 1'000'000'000'000'000'000LL;

struct segtree
{
	vll a = vll(mxh<<1, 0);
	vll b = vll(mxh<<1, INF);

	void addline(ll A, ll B, int i = 1, ll l = 0, ll r = 1'000'000)
	{
		if(A * l + B <= a[i] * l + b[i]  &&  A * r + B <= a[i] * r + b[i])
		{
			a[i] = A;
			b[i] = B;
			return;
		}

		if(A * l + B >= a[i] * l + b[i]  && A * r + B >= a[i] * r + b[i])
		{
			return;
		}

		ll m = (l+r)/2;


		if(A * l + B <= a[i] * l + b[i])
		{
			if(A * m + B <= a[i] * m + b[i])
			{
				addline(a[i], b[i], 2*i+1, m+1, r);
				a[i] = A;
				b[i] = B;
			}
			else
			{
				addline(A, B, 2*i, l, m);
			}
		}
		else
		{
			if(A * (m+1) + B <= a[i] * (m+1) + b[i])
			{
				addline(a[i], b[i], 2*i, l, m);
				a[i] = A;
				b[i] = B;
			}
			else
			{
				addline(A, B, 2*i+1, m+1, r);
			}
		}
	}

	ll query(ll x, int i = 1, ll l = 0, ll r = 1'000'000)
	{
		if(l == r) return a[i] * x + b[i];
		else if(x <= (l+r)/2) return min(a[i] * x + b[i], query(x, 2*i, l, (l+r)/2));
		else return min(a[i] * x + b[i], query(x, 2*i+1, (l+r)/2+1, r));
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;

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

	ll wsum[1+n];
	wsum[0] = 0;
	for(int i = 1; i <= n; i++)
	{
		cin >> wsum[i];
		wsum[i] += wsum[i-1];
	}

	ll dp[1+n];
	dp[1] = 0;

	segtree lct;

	lct.addline(-2 * h[1], dp[1] + h[1]*h[1] - wsum[1]);


	for(int i = 2; i <= n; i++)
	{
		dp[i] = h[i]*h[i] + wsum[i-1] + lct.query(h[i]);
		lct.addline(-2 * h[i], dp[i] + h[i]*h[i] - wsum[i]);
	}

	cout << dp[n] << '\n';
}

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