Submission #99030

#	Time	Username	Problem	Language	Result	Execution time	Memory
99030		arman_ferdous	Building Bridges (CEOI17_building)	C++17	100 / 100	143 ms	67396 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 v, int l, int r, pt nw) {
	    int m = (l + r) / 2;
	    bool lef = eval(nw, l) < eval(t[v], l);
	    bool mid = eval(nw, m) < eval(t[v], m);
	    if(mid) {
	        swap(t[v], nw);
	    }
	    if(r - l == 1) {
	        return;
	    } else if(lef != mid) {
	        insert(2 * v, l, m, nw);
	    } else {
	        insert(2 * v + 1, m, r, nw);
	    }
	}
	ll get(int v, int l, int r, ll x) {
	    int m = (l + r) / 2;
	    if(r - l == 1) {
	        return eval(t[v], x);
	    } else if(x < m) {
	        return min(eval(t[v], x), get(2 * v, l, m, x));
	    } else {
	        return min(eval(t[v], x), get(2 * v + 1, m, 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:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  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("%lld", &h[i]);
   ~~~~~^~~~~~~~~~~~~~~
building.cpp:51: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