제출 #992715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
992715		PoPularPlusPlus	Building Bridges (CEOI17_building)	C++17	0 / 100	39 ms	68440 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vf first
#define vs second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)

struct Line {
	ll m = 0 , c = 1e18;
};

ll value(Line a , int x){
	return a.m * x + a.c;
}

struct Lichao {
	vector<Line> v;
	int siz;
	
	void init(int n){
		siz = 1;
		while(siz < n){
			siz *= 2;
		}
		
		v.resize(siz * 2);
	}
	
	void set(Line l, int x , int lx , int rx){
		if(rx - lx == 0){
			if(value(l,lx) < value(v[x],lx)){
				v[x] = l;
			}
			return;
		}
		int m = (lx + rx)/2;
		
		if(v[x].m < l.m)swap(v[x],l);
		
		
		if(value(l,m) < value(v[x] , m)){
			swap(l,v[x]);
			set(l , 2 * x , lx , m);
		}
		else {
			set(l , 2 * x + 1 , m + 1 ,rx);
		}
	}
	
	ll query(int x_val , int x , int lx, int rx){
		ll ans = value(v[x],x_val);
		if(rx == lx)return ans;
		int mid = (lx + rx)/2;
		if(x_val <= mid){
			ans = min(ans , query(x_val , 2 *x, lx,mid));
		}
		else ans = min(ans , query(x_val, 2 * x + 1 , mid + 1 ,rx));
		return ans;
	}
};

void solve(){
	int n;
	cin >> n;
	ll h[n];
	for(int i = 0; i < n; i++){
		cin >> h[i];
	}
	ll w[n];
	for(int i = 0; i < n; i++){
		cin >> w[i];
	}
	
	ll dp[n];
	
	Lichao li;
	li.init(2000005);
	
	dp[0] = -w[0];
	li.set({-2*h[0] , h[0]*h[0] + w[0]},0,0,li.siz-1);
	
	ll ans = 0;
	for(int i = 0; i < n; i++){
		ans += w[i];
	}
	
	for(int i = 1; i < n; i++){
		dp[i] = li.query(h[i],0,0,li.siz-1) + h[i] * h[i] - w[i];
		
		li.set({-2*h[i] , h[i]*h[i] +dp[i]},0,0,li.siz-1);
	}
	
	cout << dp[n-1] + ans << '\n';
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//int t;
	//cin >> t;
	//	while(t--)
	solve();
}

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