Submission #1143060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143060		owoovo	Monochrome Points (JOI20_monochrome)	C++20	0 / 100	0 ms	328 KiB

monochrome

#include<bits/stdc++.h>
#define ll long long 
#define F first 
#define S second 
using namespace std;
struct BIT{
    ll val[4010];
    void init(){
        for(int i=1;i<=4005;i++)val[i]=0;
    }
    void modify(int p,ll x){
        while(p<4005){
            val[p]+=x;
            p+=p&(-p);
        }
    }
    ll query(int p){
        ll ans=0;
        while(p){
            ans+=val[p];
            p-=p&(-p);
        }
        return ans;
    }
}bit;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll ans=0;
    int n;
    cin>>n;
    vector<int> tp,o,x;
    for(int i=1;i<=n*2;i++){
        char c;
        cin>>c;
        if(c=='W'){
            tp.push_back(i);
        }else{
            x.push_back(i);
        }
    }
    for(auto u:tp)o.push_back(u);
    for(auto u:tp)o.push_back(u);
    for(int i=0;i<n;i++){
        if(i<n-1){
            int a1=x[0],a2=o[i],b1=x[n-1-i],b2=o[n-1];
            if(min(a1,a2)>max(b1,b2)||max(a1,a2)<min(b1,b2))continue;
        }
        // if(i>0){
        //     int a1=x[n-i],a2=o[n],b1=x[n-1],b2=o[n-1+i];
        //     if(min(a1,a2)>max(b1,b2)||max(a1,a2)<min(b1,b2))continue;
        // }
        vector<pair<int,int>> op;
        for(int j=0;j<n;j++){
            int a=x[j],b=o[i+j];
            //cout<<"pair "<<a<<" "<<b<<'\n';
            if(a>b)swap(a,b);
            op.push_back({a,b});
        }
        sort(op.begin(),op.end());
        reverse(op.begin(),op.end());
        bit.init();
        ll now=0;
        queue<int> q;
        for(auto [a,b]:op){
            now+=bit.query(b);
            bit.modify(b+1,-1);
            bit.modify(a,1);
        }
        //cout<<i<<" "<<now<<"\n";
        ans=max(ans,now);
    }
    cout<<ans<<"\n";

    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 21
• Subtask 3: 0 / 10
• Subtask 4: 0 / 65