记录编号 |
602385 |
评测结果 |
AAAAAAAAAAA |
题目名称 |
4162.兔子集团军 |
最终得分 |
100 |
用户昵称 |
秋_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;
}