WA on #5 #10 #16 #17 #19

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=1e6+10,inf=1e18;
LL n,tot,h[N],w[N],f[N];
struct line { LL k,b; }a[N];
struct node { LL l,r,id; }t[N<<2];
#define ls (k<<1)
#define rs (k<<1|1)
__int128 val(__int128 x,LL id) { return a[id].k*x+a[id].b; }
LL Tmax(LL i,LL j,LL x) { return val(x,i)<val(x,j)?i:j; }
void build(LL k,LL l,LL r)
{
	t[k].l=l; t[k].r=r;
	if(l==r) return;
	LL mid=l+r>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void modify(LL k,LL l,LL r,LL u)
{
	if(t[k].l>r||t[k].r<l) return;
	if(l<=t[k].l&&t[k].r<=r)
	{
		LL mid=t[k].l+t[k].r>>1;
		LL &v=t[k].id;
		if(Tmax(u,v,mid)!=v) swap(u,v);
		if(t[k].l==t[k].r) return;
		if(Tmax(u,v,t[k].l)==u) modify(ls,l,r,u);
		if(Tmax(u,v,t[k].r)==u) modify(rs,l,r,u);
		return;
	}
	modify(ls,l,r,u);
	modify(rs,l,r,u);
}
__int128 query(LL k,LL x)
{
	if(t[k].l>x||t[k].r<x) return 0;
	if(t[k].l==t[k].r) return val(x,t[k].id);
	__int128 res=min(query(ls,x),query(rs,x));
	if(t[k].l<=x&&x<=t[k].r) res=min(res,val(x,t[k].id));
	return res;
}
int main()
{
	scanf("%lld",&n);
	build(1,0,1e6);
	for(int i=1;i<=n;i++) scanf("%lld",h+i);
	for(int i=1;i<=n;i++) scanf("%lld",w+i),w[i]+=w[i-1];
	a[0]=(line){0,inf};
	a[++tot]=(line){-2*h[1],h[1]*h[1]-w[1]};
	modify(1,0,1e6,tot);
	for(int i=2;i<=n;i++)
	{
		f[i]=query(1,h[i])+h[i]*h[i]+w[i-1];
		a[++tot]=(line){-2*h[i],f[i]+h[i]*h[i]-w[i]};
		modify(1,0,1e6,tot);
	}
	printf("%lld",f[n]);
	return 0;
}