Submission #148116

#	Time	Username	Problem	Language	Result	Execution time	Memory
148116		WhipppedCream	Building Bridges (CEOI17_building)	C++17	100 / 100	84 ms	9848 KiB

building

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

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

struct LineContainer : multiset<Line, less<>>
{
	const ll inf = LLONG_MAX;
	ll div(ll a, ll b)
	{
		return a/b - ((a^b)< 0 && a%b);
	}
	bool isect(iterator x, iterator y)
	{
		if(y == end()){ x->p = inf; return false; }
		if(x->m == y->m) x->p = x->b> y->b ? inf : -inf;
		else x->p = div(x->b - y->b, y->m - x->m);
		return x->p >= y->p;
	}
	void add(ll m, ll b)
	{
		auto z = insert({m, b, 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, y = erase(y));
	}
	ll query(ll x)
	{
		assert(!empty());
		auto l = *lower_bound(x);
		return l.m*x+l.b;
	}
};

LineContainer foo;

const int maxn = 1e5+5;
ll h[maxn];
ll qs[maxn];
ll dp[maxn];
int n;

int main()
{
	scanf("%d", &n);
	for(int i = 1; i<= n; i++) scanf("%lld", h+i);
	for(int i = 1; i<= n; i++)
	{
		scanf("%lld", qs+i);
		qs[i] += qs[i-1];
	} 
	dp[1] = 0;
	foo.add(2*h[1], -dp[1]+qs[1]-h[1]*h[1]);
	for(int i = 2; i<= n; i++)
	{
		dp[i] = qs[i-1]+h[i]*h[i]-foo.query(h[i]);
		foo.add(2*h[i], -dp[i]+qs[i]-h[i]*h[i]);
	}
	printf("%lld\n", dp[n]);
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
building.cpp:58:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i<= n; i++) scanf("%lld", h+i);
                             ~~~~~^~~~~~~~~~~~~
building.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", qs+i);
   ~~~~~^~~~~~~~~~~~~~

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