令 (f_i) 表示最后一座桥的右端点在第 (i) 根柱子所需的最小代价，对 (w) 做一遍前缀和：
[f_i=min{f_j+(h_i-h_j)^2+w_{i-1}-w_j|0leq j<i}
]
考虑两个决策点 (j,k(h_j<h_k))，假设 (j) 对于当前点 (i) 更优：
[f_j+(h_i-h_j)^2+w_{i-1}-w_j<f_k+(h_i-h_k)^2+w_{i-1}-w_k
]
[f_j-w_j-(f_k-w_k)<(h_i-h_k)^2-(h_i-h_j)^2
]
[f_j-w_j+h_j^2-(f_k-w_k+h_k^2)<2h_i(h_j-h_k)
]
[frac{f_j-w_j+h_j^2-(f_k-w_k+h_k^2)}{h_j-h_k}>2h_i
]
对 ((h,f-w+h^2)) 维护一个下凸包，为了方便第 (i) 个点的信息我们记为 ((x_i,y_i,z))，其中 (z) 表示转移到 (i) 点时直线的斜率。
考虑 CDQ 分治，首先将点按 (z) 从小到大排序。处理 ([l,r]) 时，先将点按照编号分成两半，当然两半内部 (z) 仍然递增。
然后递归处理前一半。前一半返回的时候 (x) 递增，而后一半因为没有操作过，所以 (z) 仍然递增。
这样就可以用单调队列进行斜率优化了。处理完前一半对后一半的转移后，递归处理后一半。
现在两部分 (x) 都递增了，归并一下就行了。
时间复杂度 (O(nlog n))。
code:
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define Db double
#define Min(x,y)((x)<(y)?x:y)
#define For(i,x,y)for(i=x;i<=(y);i++)
#define int long long
struct point
{
int x,y,id,rake;
}a[N],b[N];
int f[N],w[N],h[N],que[N];
int read()
{
int A;
bool K;
char C;
C=A=K=0;
while(C<'0'||C>'9')K|=C=='-',C=getchar();
while(C>'/'&&C<':')A=(A<<3)+(A<<1)+(C^48),C=getchar();
return(K?-A:A);
}
inline bool cmp(point _,point __)
{
return _.rake<__.rake;
}
inline Db slope(int j,int k)
{
return(a[j].x==a[k].x?(a[j].y<a[k].y?1e18:-1e18):Db(a[j].y-a[k].y)/Db(a[j].x-a[k].x));
}
void cdq(int l,int r)
{
int k;
if(l==r)
{
k=a[l].id;
a[l].y=f[k]-w[k]+h[k]*h[k];
return;
}
int mid=(l+r)>>1,i=l,j,head=1,tail=0,pos;
j=mid+1;
For(k,l,r)b[(a[k].id<=mid?i++:j++)]=a[k];
For(k,l,r)a[k]=b[k];
cdq(l,mid);
For(k,l,mid)
{
while(head<tail&&slope(que[tail-1],que[tail])>=slope(que[tail],k))tail--;
que[++tail]=k;
}
For(k,mid+1,r)
{
while(head<tail&&slope(que[head],que[head+1])<=a[k].rake)head++;
pos=a[que[head]].id;
f[a[k].id]=Min(f[a[k].id],f[pos]+(h[a[k].id]-h[pos])*(h[a[k].id]-h[pos])+w[a[k].id-1]-w[pos]);
}
cdq(mid+1,r);
i=l;
j=mid+1;
For(k,l,r)b[k]=a[(i<=mid&&(j>r||a[i].x<a[j].x)?i++:j++)];
For(k,l,r)a[k]=b[k];
}
signed main()
{
int n,i;
n=read();
For(i,1,n)h[i]=read();
For(i,1,n)
{
w[i]=read()+w[i-1];
f[i]=LONG_LONG_MAX>>1;
a[i].rake=h[i]<<1;
a[i].x=h[i];
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
f[1]=0;
cdq(1,n);
cout<<f[n];
return 0;
}