Submission #107508

#	Time	Username	Problem	Language	Result	Execution time	Memory
107508		luciocf	Building Bridges (CEOI17_building)	C++14	100 / 100	126 ms	11300 KiB

building

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

typedef long long ll;

typedef double dd;

struct Line
{
	char type;

	dd left;

	ll m, b;
};

typedef set<Line>::iterator sli;

ll h[maxn], w[maxn];
ll dp[maxn];

set<Line> env;

bool operator< (const Line &a, const Line &b)
{
	if (a.type+b.type > 0) return a.left < b.left;

	return a.m > b.m;
}

bool first(sli it)
{
	return (it == env.begin());
}

bool last(sli it)
{
	return (next(it) == env.end());
}

bool bad(Line l1, Line l2, Line l3)
{
	return (l3.b-l1.b)*(l1.m-l2.m) < (l1.m-l3.m)*(l2.b-l1.b);
}

dd intersect(Line l1, Line l2)
{
	return (dd)(l2.b-l1.b)/(l1.m-l2.m);
}

void get_left(sli it)
{
	if (!first(it))
	{
		Line l = *it;

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

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

void add(ll m, ll b)
{
	Line l = {0, 0, m, b};

	sli it = env.lower_bound(l);

	if (it != env.end() && it->m == l.m)
	{
		if (it->b <= l.b) return;
		env.erase(it);
	}

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

	if (!first(it) && !last(it) && bad(*prev(it), *it, *next(it)))
	{
		env.erase(it);
		return;
	}

	while (!last(it) && !last(next(it)) && bad(*it, *next(it), *next(next(it))))
		env.erase(next(it));

	while (!first(it) && !first(prev(it)) && bad(*prev(prev(it)), *prev(it), *it))
		env.erase(prev(it));

	get_left(it);
	if (!last(it)) get_left(next(it));
}

ll query(ll x)
{
	sli it = env.upper_bound({1, (dd)x, 0, 0});
	it--;

	return (it->m * x + it->b);
}

int main(void)
{
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%lld", &h[i]);

	ll S = 0;
	for (int i = 1; i <= n; i++)
		scanf("%lld", &w[i]), S += 1ll*w[i];

	dp[1] = -w[1];

	add(-2*h[1], h[1]*h[1]-w[1]);

	for (int i = 2; i <= n; i++)
	{
		ll val = query(h[i]);

		dp[i] = h[i]*h[i] - w[i] + val;

		add(-2*h[i], h[i]*h[i]+dp[i]);
	}

	printf("%lld\n", S+dp[n]);
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
building.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &h[i]);
   ~~~~~^~~~~~~~~~~~~~~
building.cpp:115:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &w[i]), S += 1ll*w[i];
   ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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