Submission #948214

#	Time	Username	Problem	Language	Result	Execution time	Memory
948214		amirhoseinfar1385	Building Bridges (CEOI17_building)	C++17	100 / 100	2985 ms	8180 KiB

building

#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10;
long long inf=1e17;
struct func{
	long long x,y;
	func(){
		x=inf;
		y=0;
	}
	long long get(long long w){
		return x+w*y;
	}
	bool operator ==(func f){
		return (f.x==x&&f.y==y);
	}
}fakefunc;

struct lichao{
	struct node{
		long long l,r;
		node(){
			l=r=-1;
		}
		func f;
	};
	node seg[maxn];
	int te=1;
	int gor(int i){
		if(seg[i].r==-1){
			seg[i].r=te;
			te++;
		}
		return seg[i].r;
	}
	int gol(int i){
		if(seg[i].l==-1){
			seg[i].l=te;
			te++;
		}
		return seg[i].l;
	}
	void add(func f,long long i=0,long long l=-2e6,long long r=2e6){
		if(l==r){
			return ;
		}
		if(seg[i].f==fakefunc){
			seg[i].f=f;
			return ;
		}
		long long m=(l+r)/2;
		if(seg[i].f.get(l)>f.get(l)){
			swap(seg[i].f,f);
		}
		if(seg[i].f.get(m)<=f.get(m)){
			add(f,gor(i),m,r);
		}else{
			swap(seg[i].f,f);
			add(f,gol(i),l,m);
		}
	}
	long long pors(long long w,long long i=0,long long l=-2e6,long long r=2e6){
		if(l==r){
			return 0;
		}
		long long ret=seg[i].f.get(w);
		long long m=(l+r)>>1;
		if(w>=m&&seg[i].r!=-1){
			ret=min(ret,pors(w,seg[i].r,m,r));
		}
		if(w<m&&seg[i].l!=-1){
			ret=min(ret,pors(w,seg[i].l,l,m));
		}
		return ret;
	}
}lich;
long long dp[maxn],n,w[maxn],h[maxn],ps[maxn];


void vorod(){
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>h[i];
	}
	for(long long i=1;i<=n;i++){
		cin>>w[i];
	}
	for(long long i=1;i<=n;i++){
		ps[i]=ps[i-1]+w[i];
	}
}

void add(long long i){
	func f;
	f.x=dp[i]-ps[i]+h[i]*h[i];
	f.y=-2*h[i];
	//cout<<"add: "<<f.x<<" "<<f.y<<endl;
	lich.add(f);
}

void upd(long long i){
	dp[i]=+ps[i-1]+h[i]*h[i]+lich.pors(h[i]);
	//cout<<"upd: "<<dp[i]<<endl;
}

void solve(){
	dp[1]=0;
	add(1);
	for(long long i=2;i<=n;i++){
		upd(i);
		add(i);
	}
}

void khor(){
	cout<<dp[n]<<endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	solve();
	khor();
}

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