李超WA80pts on #5,#10,#16~#17,#19求调
查看原帖
李超WA80pts on #5,#10,#16~#17,#19求调
477821
toolong114514楼主2024/5/27 22:22
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
#define int long long
const int INF=1e18;
const double eps=1e-10;
const int N=1e6+10;
struct node{
	int l,r,bst;
}tree[4*N];
struct ccf{
	int k,b;
}ln[N];
void build(int pos,int lft,int rgt){
	tree[pos].l=lft;
	tree[pos].r=rgt;
	if(lft==rgt) return;
	int mid=(lft+rgt)/2;
	build(pos*2,lft,mid);
	build(pos*2+1,mid+1,rgt);
}
void upd(int pos,int num){
	int mid=(tree[pos].l+tree[pos].r)/2;
	if((ln[tree[pos].bst].k==ln[num].k)&&(ln[tree[pos].bst].b==ln[num].b)) return;
	if(ln[tree[pos].bst].k*mid+ln[tree[pos].bst].b>ln[num].k*mid+ln[num].b) swap(tree[pos].bst,num);
	if(tree[pos].l==tree[pos].r) return;
	if(ln[num].k*tree[pos].l+ln[num].b<ln[tree[pos].bst].k*tree[pos].l+ln[tree[pos].bst].b) upd(pos*2,num);
	if(ln[num].k*tree[pos].r+ln[num].b<ln[tree[pos].bst].k*tree[pos].r+ln[tree[pos].bst].b) upd(pos*2+1,num);
}
int ask(int pos,int kk){
	if(kk<tree[pos].l||tree[pos].r<kk) return INF;
	if(tree[pos].l==tree[pos].r) return ln[tree[pos].bst].k*kk+ln[tree[pos].bst].b;
	return min(min(ask(pos*2,kk),ask(pos*2+1,kk)),ln[tree[pos].bst].k*kk+ln[tree[pos].bst].b);
}
int w[N],h[N],f[N];
int n,cnt,maxn,minn=INF;
signed main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
		maxn=max(maxn,h[i]);
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
		w[i]+=w[i-1];
	}
	build(1,0,maxn);
	ln[++cnt]={0,INF};
	upd(1,cnt);
	ln[++cnt]={-2*h[1],h[1]*h[1]-w[1]};
	upd(1,cnt);
	for(int i=2;i<=n;i++){   
		/*if(h[i]!=0)*/ f[i]=ask(1,h[i])+h[i]*h[i]+w[i-1];
		//else f[i]=minn+w[i-1];
		minn=min(minn,f[i]+h[i]*h[i]-w[i]);
		ln[++cnt]={-2*h[i],f[i]+h[i]*h[i]-w[i]};
		upd(1,cnt);
	}
	cout<<f[n];
	return 0;
}
2024/5/27 22:22
加载中...