Submission #349211

#	Time	Username	Problem	Language	Result	Execution time	Memory
349211		Bill_00	Building Bridges (CEOI17_building)	C++14	100 / 100	123 ms	69612 KiB

building

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define N 1000001
using namespace std;
struct line{
	ll k,b;
	ll operator*(ll x){
		return k*x+b;
	}
};
ll n,h[N],w[N],dp[N];
line lines[20*N+4],nw;
void build(line nw,ll id,ll l,ll r){
	lines[id]=nw;
	if(r-l==1){
		return;
	}
	ll m=(l+r)>>1;
	build(nw,id*2,l,m);
	build(nw,id*2+1,m,r);
}
ll search(ll x,ll id,ll l,ll r){
	ll m=(l+r)>>1;
	if(r-l==1){
		return lines[id]*x;
	}
	if(x<m){
		return min(search(x,id*2,l,m),lines[id]*x);
	}
	else return min(search(x,id*2+1,m,r),lines[id]*x);
}
void ins(line nw,ll id,ll l,ll r){
	ll m=(l+r)>>1;
	bool lef=((nw*l)<(lines[id]*l));
	bool mid=((nw*m)<(lines[id]*m));
	if(mid) swap(lines[id],nw);
	if(r-l==1) return;
	if(lef!=mid){
		ins(nw,id*2,l,m);
	}
	else ins(nw,id*2+1,m,r);
}
ll lol;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> h[i];
	}
	for(int i=1;i<=n;i++){
		cin >> w[i];
		lol+=w[i];
	}
	dp[1]=-w[1];
	nw={h[1],dp[1]+h[1]*h[1]};
	build(nw,1,-2*N,1);
	for(int i=2;i<n;i++){
		ll k=search(-2*h[i],1,-2*N,1);
		dp[i]=h[i]*h[i]+k-w[i];
		nw={h[i],dp[i]+h[i]*h[i]};
		ins(nw,1,-2*N,1);
	}
	ll k=search(-2*h[n],1,-2*N,1);
	dp[n]=h[n]*h[n]+k-w[n];
	cout << dp[n]+lol;


}

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