Submission #63599344

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n) for(int i=0;i<(n);++i)
#define sizc(x) ((int)(x).size())
#define allc(x) (x).begin(),(x).end()
#define fir first
#define sec second
constexpr int N = 2e5+5;
int n;
bool a[N],b[N];
ll c[N];
int o[N];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;

using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n) for(int i=0;i<(n);++i)
#define sizc(x) ((int)(x).size())
#define allc(x) (x).begin(),(x).end()
#define fir first
#define sec second

constexpr int N = 2e5+5;

int n;
bool a[N],b[N];
ll c[N];
int o[N];
ll pre[N];

struct fenwick{
    ll c[N];
    void add(int x,ll y){while(x<=n)c[x]+=y,x+=x&-x;}
    ll sum(int x){ll ret=0;while(x)ret+=c[x],x-=x&-x;return ret;}
}t1,t2,t3,t4;

ll now,ans;
void add1(int p){
    now+=c[o[p]]*(t1.sum(n)-t1.sum(p));
    now+=t2.sum(p);
    t1.add(p,1),t2.add(p,c[o[p]]);
}
void add2(int p){
    now+=c[o[p]]*(t3.sum(n)-t3.sum(p)+1);
    now+=t4.sum(p);
    t3.add(p,1),t4.add(p,c[o[p]]);
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

    cin>>n;
    rep(i,1,n)cin>>a[i];
    rep(i,1,n)cin>>b[i];
    rep(i,1,n)cin>>c[i],o[i]=i;
    sort(o+1,o+n+1,[&](int x,int y){return c[x]<c[y];});
    rep(i,1,n){
        int x=a[o[i]],y=b[o[i]];
        if(x&&!y)add1(i);
        if(!x&&y)add2(i);
        pre[i]=pre[i-1];if(x&&y)pre[i]+=c[o[i]];
    }
    ll ans=now+pre[n]*(t1.sum(n)+t3.sum(n));
    per(i,n,1){
        int x=a[o[i]],y=b[o[i]];
        if(!x||!y)continue;
        add1(i),add2(i);
        ans=min(ans,now+pre[i-1]*(t1.sum(n)+t3.sum(n)));
    }
    cout<<ans<<'\n';
}

Submission Info

Judge Result