记录编号	587110	评测结果	AAAAAAAAAA
题目名称	[CEOI 2017] Building Bridges	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.259 s
提交时间	2024-03-14 11:50:57	内存使用	56.46 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10,M = 1e6+10;
const ll inf = 1e17;
int n,m;
ll h[N],s[N],k[N],b[N],f[N];
struct LiChao_tree{
    int mi[M<<4];
    ll get(int x,int i){return k[i] * x + b[i];}
    void modify(int p,int l,int r,int x){
        int mid = l + r >> 1;
        if(get(mid,x) < get(mid,mi[p]))swap(x,mi[p]);
        if(get(l,x) < get(l,mi[p]))modify(p<<1,l,mid,x);
        else if(get(r,x) < get(r,mi[p]))modify(p<<1|1,mid+1,r,x);
    }
    ll query(int p,int l,int r,int x){
        if(l == r)return get(x,mi[p]);
        int mid = l + r >> 1;
        if(x <= mid)return min(query(p<<1,l,mid,x),get(x,mi[p]));
        else return min(query(p<<1|1,mid+1,r,x),get(x,mi[p]));
    }
}t;
int main(){
	freopen("jiaqiao.in","r",stdin);
    freopen("jiaqiao.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)scanf("%lld",&h[i]);
    for(int i = 1;i <= n;i++)scanf("%lld",&s[i]),s[i] += s[i-1];
    b[0] = inf;
    for(int i = 1;i <= n;i++){
        if(i > 1)f[i] = h[i] * h[i] + s[i-1] + t.query(1,1,1e6,h[i]);
        k[++m] = -2 * h[i],b[m] = f[i] - s[i] + h[i] * h[i];
        t.modify(1,1,1e6,m);
    }
    printf("%lld\n",f[n]);

	return 0;

}