记录编号	602350	评测结果	AAAAAAAAAAA
题目名称	4162.兔子集团军	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	2.865 s
提交时间	2025-07-03 16:54:21	内存使用	27.55 MiB

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const ll INF = 1e18;

int n;
int c[N];
int A[N], B[N];
int vis[N], T = 0;
ll v[N], f[N];
ll ans = INF;

void solve(int l, int r){
    if (l > r) return;
    int mid = (l + r) >> 1;
    int i = mid, j = mid;
    queue<int> q;T ++;
    q.push(c[mid]);
    vis[c[mid]] = T;
    bool flag = true;
    while(!q.empty() && flag){
        int x = q.front();
        q.pop();
        if(A[x] < l || B[x] > r){
            flag = false;
            break;
        }
        for(int k = i - 1;k >= A[x];k --){
            if(vis[c[k]] != T){
                vis[c[k]] = T;
                q.push(c[k]);
            }
        }
        for(int k = j + 1;k <= B[x];k ++){
            if(vis[c[k]] != T){
                vis[c[k]] = T;
                q.push(c[k]);
            }
        }
        i = min(i, A[x]);
        j = max(j, B[x]);
    }
    if(flag){
        ll cost = 0;
        for (int k = i, d = 1;k <= j;k ++,d ++){
            cost += v[k] * f[d] * f[d];
        }
        ans = min(ans, cost);
    }
    solve(l, mid - 1);
    solve(mid + 1, r);
}

int main(){
    scanf("%d", &n);
    for(int i = 1;i <= n;i ++) scanf("%d", &c[i]);
    for(int i = 1;i <= n;i ++) scanf("%lld", &v[i]);
    for(int i = 1;i <= n;i ++) scanf("%lld", &f[i]);
    memset(A, 0x3f, sizeof(A));
    memset(B, 0, sizeof(B));
    for(int i = 1;i <= n;i ++){
        A[c[i]] = min(A[c[i]], i);
        B[c[i]] = max(B[c[i]], i);
    }
    memset(vis, 0, sizeof(vis));
    T = 0;
    solve(1, n);
    printf("%lld\n", ans);
    return 0;
}