Submission #1050816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050816		AlphaBruh	Building Bridges (CEOI17_building)	C++17	100 / 100	94 ms	13404 KiB

building

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
#define SIZE 100005
#define inf 3000000000000000000
// basic
int n;
ll h[SIZE],w[SIZE],dp[SIZE],sw=0;
// cdq stuff
int qry[19][SIZE];
void srt(int l=1, int r=n, int id=0){
	if(l==r){
		qry[id][l]=l;
		return;
	}
	int md=(l+r)>>1;
	srt(l,md,id+1);
	srt(md+1,r,id+1);
	int lp=l,rp=md+1,cnt=l;
	int *bd = qry[id+1];
	while(lp<=md){
		while((rp<=r)&&(h[bd[rp]]<h[bd[lp]])){
			qry[id][cnt]=bd[rp];
			cnt++;
			rp++;
		}
		qry[id][cnt]=bd[lp];
		cnt++;
		lp++;
	}
	while(rp<=r){
		qry[id][cnt]=bd[rp];
		cnt++;
		rp++;
	}
}
ll X[SIZE],Y[SIZE];
int ed=0,stk[SIZE];
void clear(){ed=0;}
void pb(int id){
	ll dx1,dx2,dy1,dy2;
	while(ed>1){
		int cur=stk[ed];
		dx1=X[id]-X[cur];
		dy1=Y[id]-Y[cur];
		dx2=X[cur]-X[stk[ed-1]];
		dy2=Y[cur]-Y[stk[ed-1]];
		if(dy1*dx2<=dy2*dx1) ed--;
		else break;
	}
	stk[++ed]=id;
}
ll cal(int id, ll k){return Y[id]-(X[id]*k);}
queue<int> cdq(int l=1, int r=n, int id=0){
	if(l==r){
		X[l]=2*h[l];
		Y[l]=dp[l]+h[l]*h[l];
		queue<int>ret;
		ret.push(l);
		return ret;
	}
	int md=(l+r)>>1;
	queue<int>crv(cdq(l,md,id+1));
	queue<int>lft(crv);
	int cur=crv.front();
	crv.pop();
	for(int i=md+1;i<=r;i++){
		int nq = qry[id+1][i];
		while((!crv.empty()) && (cal(cur,h[nq]) >= cal(crv.front(),h[nq]))){
			cur=crv.front();
			crv.pop();
		}
		dp[nq] = min(dp[nq],cal(cur,h[nq])+h[nq]*h[nq]-w[nq]);
	}
	queue<int>rgt(cdq(md+1,r,id+1));
	clear();
	int L,R;
	while(lft.size()){
		L=lft.front();
		while(rgt.size()){
			R=rgt.front();
			if(X[R] < X[L]){
				pb(R);
				rgt.pop();
			}
			else break;
		}
		pb(L);
		lft.pop();
	}
	while(rgt.size()){
		pb(rgt.front());
		rgt.pop();
	}
	queue<int>ret;
	for(int i=1;i<=ed;i++) ret.push(stk[i]);
	return ret;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>h[i];
	for(int i=1;i<=n;i++){
		cin>>w[i];
		sw+=w[i];
		dp[i]=inf;
	}
	if(n==1){
		printf("%lld\n",w[1]);
		return 0;
	}
	srt(1,n,0);
	dp[1]=-w[1];
	cdq(1,n,0);
	cout<<dp[n]+sw<<endl;
	return 0;
}

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