제출 #411140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
411140		Blagojce	Building Bridges (CEOI17_building)	C++11	100 / 100	185 ms	12748 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 inf = 1e18;
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;
}


struct line{
	ll m, b;
	ld x;
	ll val;
	bool query;

	line(ll m1, ll b1, ld x1, bool q1){
		m = m1, b = b1, x = x1, query = q1;
	}
	bool operator <(const line &l) const{
		if(l.query) return x < l.val;
		else return m < l.m;
	}
	bool parallel(const line &l) const{
		return m == l.m;
	}
	ld intersect(const line &l) const{
		return 1.0*(l.b-b)/(m-l.m);
	}
	ll eval(ll x) const{
		return m*x + b;
	}
	
	
};
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->m, it->b, x, false);
	hull.erase(it);
	hull.insert(tmp);
	return hull.find(tmp);
}


void addLine(ll m, ll b){
	line l(m, b, -inf, false);
	iter it = hull.lower_bound(l);
	if(it != hull.end() && l.parallel(*it)){
		if(it->b < b) it = hull.erase(it);
		else return;
	}
	hull.insert(l);
	it = hull.find(l);
	
	if(bad(it)){
		hull.erase(it);
		return;
	}
	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){
	if(hull.empty()) return -inf;
	line q(0, 0, 0, true);
	q.val = x;
	iter it = --hull.lower_bound(q);
	return it->eval(x);
}



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;
	addLine(2*h[0], -(dp[0] + p(h[0])-pref[0]));
	
	
	fr(i, 1, n){
		dp[i] = -query(h[i]) + p(h[i]) + pref[i] - w[i];
		
		
		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

*/

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