比赛 |
集训 |
评测结果 |
TTTTWWWTTEW |
题目名称 |
兔子集团军 |
最终得分 |
0 |
用户昵称 |
KKZH |
运行时间 |
13.834 s |
代码语言 |
C++ |
内存使用 |
23.92 MiB |
提交时间 |
2025-07-03 12:38:25 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
struct node{
int l,r;
};
int n,r,cnt,ans,cn;
map <int,int> mp;
int c[N],v[N],f[N],a[N],num[N],he[N];
int h[N],t[N],sum[N];
node find(int l,int r){
node u,k;
u.l=l;
u.r=r;
if(l==r) return u;
int hea=l,tai=r;
for(int i=l;i<=r;i++){
u.l=min(u.l,h[a[i]]);
u.r=max(u.r,t[a[i]]);
}
k=find(hea,l);
u.l=min(u.l,k.l);
u.r=max(u.r,k.r);
k=find(r,tai);
u.l=min(u.l,k.l);
u.r=max(u.r,k.r);
return u;
}
void solve1(){
int ans=100000000;
for(int i=1;i<=cnt;i++){
// cout<<h[i]<<t[i]<<endl;
node y=find(h[i],t[i]);
// cout<<y.l<<y.r<<endl;
ans=min(ans,sum[y.r]-sum[y.l-1]);
}
cout<<ans;
}
void solve2(){
int ans=100000000;
for(int i=1;i<=cnt;i++){
// cout<<h[i]<<t[i]<<endl;
node y=find(h[i],t[i]);
// cout<<y.l<<y.r<<endl;
int tot=0;
for(int j=y.l;j<=y.r;j++){
tot+=v[j]*f[j-y.l+1];
// cout<<v[j]*f[j-y.l+1]<<" "<<j<<endl ;
}
ans=min(ans,tot+sum[y.r]-sum[y.l-1]);
}
cout<<ans;
}
int main(){
freopen("RRR.in","r",stdin);
freopen("RRR.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i];
if(mp.find(c[i])==mp.end())
mp[c[i]]=++cnt;
if(h[mp[c[i]]]==0) h[mp[c[i]]]=i;
t[mp[c[i]]]=i;
if(c[i]!=c[i-1]){
num[cn]=i-1;
a[++cn]=c[i];
he[cn]=i;
}
}
// cout<<cnt;
for(int i=1;i<=n;i++){
cin>>v[i];
sum[i]=sum[i-1]+v[i];
}
for(int i=1;i<=n;i++){
cin>>f[i];
if(f[i]!=1) r=1;
f[i]=f[i]^2;
}
if(r==0) solve1();
else solve2();
return 0;
}