Submission #99040

#	Time	Username	Problem	Language	Result	Execution time	Memory
99040		arman_ferdous	Building Bridges (CEOI17_building)	C++17	100 / 100	134 ms	66140 KiB

building

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
const int N = 1e5+100;
const int MAX = 1e6+100;
const ll inf = 1e18;
 
struct LiChao{
	struct pt{ ll m, c; };
	ll eval(pt p, ll x) { return p.m * x + p.c; }
 
	pt t[MAX<<2];
	LiChao() { for(int i = 0; i < (MAX<<2); i++) t[i] = {0,inf}; }
	
	void insert(int node, int L, int R, pt p) {
		if(L == R) {
			if(eval(p,L) < eval(t[node],L)) t[node] = p;
			return;
		} int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
 
		bool one = eval(p,L) < eval(t[node],L);
		bool two = eval(p,mid) < eval(t[node],mid);
 
		if(two) swap(t[node], p);
		if(one != two) insert(lc, L, mid, p);
		else insert(rc, mid+1, R, p);
	}
	ll get(int node, int L, int R, ll x) {
		if(L == R) return eval(t[node], x);
		int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		if(x <= mid) return min(eval(t[node], x), get(lc, L, mid, x));
		return min(eval(t[node], x), get(rc, mid+1, R, x));
	}
}ds;
 
int n;
ll h[N], w[N], S[N], dp[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", &w[i]);
		S[i] = S[i-1] + w[i];
	}
	dp[1] = 0;
	ds.insert(1, 0, MAX-1, {-2ll*h[1], h[1]*h[1] - S[1]});
	for(int i = 2; i <= n; i++) {
		ll got = ds.get(1, 0, MAX-1, h[i]);
		dp[i] = got + h[i] * h[i] + S[i-1];
		ds.insert(1, 0, MAX-1, {-2ll*h[i], dp[i] - S[i] + h[i] * h[i]});
	}
	printf("%lld\n", dp[n]);
	return 0;
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
building.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &h[i]);
   ~~~~~^~~~~~~~~~~~~~~
building.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &w[i]);
   ~~~~~^~~~~~~~~~~~~~~

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