记录编号 602385 评测结果 AAAAAAAAAAA
题目名称 4162.兔子集团军 最终得分 100
用户昵称 Gravatar秋_Water 是否通过 通过
代码语言 C++ 运行时间 5.382 s
提交时间 2025-07-03 20:35:57 内存使用 23.33 MiB
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+7; 
int n,c[N],f[N],v[N],l[N],r[N],ans=1e18;
int fun(int l,int r){
	int res=0;
	for(int i=l;i<=r;i++){
		res+=v[i]*f[i-l+1]*f[i-l+1];
	}
	return res;
} 
queue<int>q;
void solve(int ll,int rr){
	if(ll>rr) return;
	int mid=ll+rr>>1;
	while(!q.empty()) q.pop(); 
	q.push(c[mid]);
	bool fl=0;
	int i=mid,j=mid;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		if(l[x]<ll||rr<r[x]){
			fl=1;
			break;
		}
		else{
			for(int k=i-1;k>=l[x];k--){
				q.push(c[k]);
			}
			for(int k=j+1;k<=r[x];k++){
				q.push(c[k]);
			}			
			i=min(i,l[x]),j=max(j,r[x]);
		}
	} 
	if(!fl) ans=min(ans,fun(i,j)); 
	if(ll==rr){
		return; 
	}
	else{
		solve(ll,mid-1);
		solve(mid+1,rr); 
	} 
	return;
} 
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i];
	}
	for(int i=1;i<=n;i++){
		cin>>v[i];
	}	
	for(int i=1;i<=n;i++){
		cin>>f[i];
	}
	for(int i=1;i<=n;i++){
		if(!l[c[i]]) l[c[i]]=i;
		r[c[i]]=i;
	}
	solve(1,n);
	cout<<ans;
	
	return 0;
}