제출 #240047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
240047		eohomegrownapps	Building Bridges (CEOI17_building)	C++14	100 / 100	209 ms	129248 KiB

building

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll INF = 1e18;
struct Line{
	ll m,c;
	Line(ll _m, ll _c){
		m=_m;c=_c;
	}
	ll operator()(ll x){
		return m*x+c;
	}
};

struct Node{
	ll s,e,m;
	Line f = Line(0,INF);
	Node *l, *r;

	Node(ll _s, ll _e){
		s=_s;e=_e;
		if (s==e){return;}
		m=(s+e)/2;
		l = new Node(s,m);
		r = new Node(m+1,e);
	}

	void insert(Line ins){
		if (s==e){
			if (ins(s)<f(s)){
				f=ins;
			}
			return;
		}
		if (ins.m==f.m){
			if (ins.c<f.c){
				f=ins;
			}
			return;
		}
		//wlog insert line has higher gradient
		if (ins.m<f.m){
			swap(ins,f);
		}
		if (ins(m)<f(m)){
			r->insert(f);
			f=ins;
		} else {
			l->insert(ins);
		}
	}

	ll query(ll x){
		if (s==e){
			return f(x);
		}
		if (x<=m){
			return min(f(x),l->query(x));
		} else {
			return min(f(x),r->query(x));
		}
	}
};

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	ll n;
	int nv;
	cin>>nv;
	n=nv;
	vector<ll> h(n);
	vector<ll> pref(n+1);
	for (ll i = 0; i<n; i++){
		long long tmp;
		cin>>tmp;
		h[i]=tmp;
	}
	for (ll i = 0; i<n; i++){
		long long tmp;
		cin>>tmp;
		pref[i+1]=tmp;
		pref[i+1]+=pref[i];
	}
	vector<ll> dp(n);
	Node *lichao = new Node(0,1000000);
	lichao->insert(Line(-2*h[0],dp[0]-pref[1]+h[0]*h[0]));
	for (ll x = 1; x<n; x++){
		ll minval = lichao->query(h[x]);
		dp[x]=h[x]*h[x]+pref[x]+minval;
		lichao->insert(Line(-2*h[x],dp[x]-pref[x+1]+h[x]*h[x]));
	}
	cout<<(long long)(dp[n-1])<<'\n';
}

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