Submission #1226861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226861		Aviansh	Chorus (JOI23_chorus)	C++20	16 / 100	49 ms	328 KiB

chorus

#include <bits/stdc++.h>

using namespace std;

int check(int mask, int n){
    //0 is a, 1 is b
    vector<int>as;
    vector<int>bs;
    for(int i = 0;i<n;i++){
        if((1<<i)&mask){
            bs.push_back(i);
        }
        else{
            as.push_back(i);
        }
    }
    for(int i = 0;i<n/2;i++){
        if(as[i]>bs[i]){
            return 1e9;
        }
    }
    //valid arrangement
    int i = 0;
    int cn = 0;
    while(i<n/2){
        //at ith a
        cn++;
        i=lower_bound(as.begin(),as.end(),bs[i])-as.begin();
    }
    return cn;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int>as;
    n*=2;
    for(int i = 0;i<n;i++){
        if(s[i]=='A'){
            as.push_back(i);
        }
    }
    int ans = 1e9;
    for(int mask = 0;mask<(1<<n);mask++){
        if(__builtin_popcount(mask)!=n/2){
            continue;
        }
        if(check(mask,n)<=k){
            int curr = 0;
            vector<int>temp;
            for(int i = 0;i<n;i++){
                if((1<<i)&mask){

                }
                else{
                    temp.push_back(i);
                }
            }
            for(int i = 0;i<n/2;i++){
                curr+=abs(as[i]-temp[i]);
            }
            ans=min(ans,curr);
        }
    }
    cout << ans;
    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13