Submission #46340

#	Time	Username	Problem	Language	Result	Execution time	Memory
46340		RezwanArefin01	Building Bridges (CEOI17_building)	C++17	100 / 100	167 ms	18004 KiB

building

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

typedef long long ll;
typedef pair<int, int> ii; 

const int maxn = 1e5 + 10; 
const ll isQuery = -(1ll << 62);

struct line {
	ll m, b;
	mutable function<const line*()> succ; 
	bool operator < (const line &l) const {
		if(l.b != isQuery) return m < l.m; 
		const line* s = succ(); 
		if(!s) return 0;
		return b - s -> b < (s -> m - m) * l.m;
	}	
};
struct cht : public multiset<line> {
	bool bad(iterator y) {
		auto z = next(y);
		if(y == begin()) {
			if(z == end()) return 0; 
			return y -> m == z -> m && y -> b <= z -> b;
		}
		auto x = prev(y);
		if(z == end()) return y -> m == x -> m && y -> b <= x -> b;
		return 1.0 * (z -> b - x -> b) * (x -> m - y -> m) <= 1.0 * (y -> b - x -> b) * (x -> m - z -> m);
	}
	void add(ll m, ll b) { 
		auto y = insert({-m, -b}); 
		y -> succ = [=]{ return next(y) == end() ? 0 : &*next(y); }; 
		if(bad(y)) return (void) erase(y); 
		while(next(y) != end() && bad(next(y))) erase(next(y)); 
		while(y != begin() && bad(prev(y))) erase(prev(y));
	}
	ll eval(ll x) {
		auto it = *lower_bound({x, isQuery}); 
		return -(it.m * x + it.b);
	}
} ds;
int n, h[maxn], w[maxn]; 
ll dp[maxn], sum;

int main(int argc, char const *argv[]) {
	int n; scanf("%d", &n); 
	for(int i = 1; i <= n; i++) 
		scanf("%d", &h[i]);
	for(int i = 1; i <= n; i++) 
		scanf("%d", &w[i]), sum += w[i]; 

	dp[1] = -w[1]; 
	ds.add(-2ll * h[1], dp[1] + (ll) h[1] * h[1]);
	for(int i = 2; i <= n; i++) {
		dp[i] = ds.eval(h[i]) + (ll) h[i] * h[i] - w[i];
		ds.add(-2ll * h[i], dp[i] + (ll) h[i] * h[i]);
	}

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

Compilation message (stderr)

building.cpp: In function 'int main(int, const char**)':
building.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n); 
         ~~~~~^~~~~~~~~~
building.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &h[i]);
   ~~~~~^~~~~~~~~~~~~
building.cpp:51:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &w[i]), sum += w[i]; 
   ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

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