Submission #411138

#	Time	Username	Problem	Language	Result	Execution time	Memory
411138		Blagojce	Building Bridges (CEOI17_building)	C++11	100 / 100	108 ms	12816 KiB

building

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)


using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9;
const ll mod = 1e9+7;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;

mt19937 _rand(time(NULL));
clock_t z;

const int mxn = 2e5+5;

int n;
ll h[mxn];
ll w[mxn];

ll dp[mxn];

ll pref[mxn];

ll p(ll a){
	return a*a;
}
const ld inf = 1e18;

struct chtDynamic {  
	struct line {
		ll m, b; ld x; 
		ll val; bool isQuery; 
		line(ll _m = 0, ll _b = 0) : 
			m(_m), b(_b), val(0), x(-inf), isQuery(false) {} 
		
		ll eval(ll x) const { return m * x + b;	}
		bool parallel(const line &l) const { return m == l.m; }
		ld intersect(const line &l) const {
			return parallel(l) ? inf : 1.0 * (l.b - b) / (m - l.m);
		}
		bool operator < (const line &l) const {
			if(l.isQuery) return x < l.val;
			else return m < l.m; 
		}
	};

	set<line> hull; 
	typedef set<line> :: iterator iter; 

	bool cPrev(iter it) { return it != hull.begin(); }
	bool cNext(iter it) { return it != hull.end() && next(it) != hull.end(); }

	bool bad(const line &l1, const line &l2, const line &l3) {
		return l1.intersect(l3) <= l1.intersect(l2); 
	}
	bool bad(iter it) {
		return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it));
	}

	iter update(iter it) {
		if(!cPrev(it)) return it; 
		ld x = it -> intersect(*prev(it));
		line tmp(*it); tmp.x = x;
		it = hull.erase(it); 
		return hull.insert(it, tmp);
	}

	void addLine(ll m, ll b) { 
		line l(m, b); 
		iter it = hull.lower_bound(l); 
		if(it != hull.end() && l.parallel(*it)) {
			if(it -> b < b) it = hull.erase(it); 
			else return;
		}

		it = hull.insert(it, l); 
		if(bad(it)) return (void) hull.erase(it);

		while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
		while(cNext(it) && bad(next(it))) hull.erase(next(it));

		it = update(it);
		if(cPrev(it)) update(prev(it));
		if(cNext(it)) update(next(it));
	}

	ll query(ll x) const { 
		if(hull.empty()) return -inf;
		line q; q.val = x, q.isQuery = 1;
		iter it = --hull.lower_bound(q);
		return it -> eval(x);
	}
} ds;



void solve(){
	cin >> n;
	fr(i, 0, n){
		cin >> h[i];
	}
	fr(i, 0, n){
		cin >> w[i];
	}
	pref[0] = w[0];
	fr(i, 1, n){
		pref[i] = pref[i-1]+w[i];
	}
	
	dp[0] = 0;
	ds.addLine(2*h[0], -(dp[0] + p(h[0])-pref[0]));
	
	
	fr(i, 1, n){
		dp[i] = -ds.query(h[i]) + p(h[i]) + pref[i] - w[i];
		
		
		ds.addLine(2*h[i], -(dp[i] + p(h[i]) - pref[i]));
		
	}
	cout<<dp[n-1]<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();

}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0

*/

Compilation message (stderr)

building.cpp: In constructor 'chtDynamic::line::line(ll, ll)':
building.cpp:40:6: warning: 'chtDynamic::line::val' will be initialized after [-Wreorder]
   40 |   ll val; bool isQuery;
      |      ^~~
building.cpp:39:15: warning:   'ld chtDynamic::line::x' [-Wreorder]
   39 |   ll m, b; ld x;
      |               ^
building.cpp:41:3: warning:   when initialized here [-Wreorder]
   41 |   line(ll _m = 0, ll _b = 0) :
      |   ^~~~

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