Submission #915725

#	Time	Username	Problem	Language	Result	Execution time	Memory
915725		efedmrlr	Chorus (JOI23_chorus)	C++17	40 / 100	7100 ms	432 KiB

chorus

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 5e2+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,m,q,K;
string s;
vector<int> a(1), b(1);
vector<int> acnt(2*N, 0);
lli ans = 0;
vector<int> dp, dpn;


inline void solve() {
    cin>>n>>K;
    cin>>s;
    
    for(int i = 0; i<2*n; i++) {
        acnt[i + 1] = acnt[i] + (s[i] == 'A');
        if(s[i] == 'A') {
            a.pb(i + 1);
        }
        else {
            b.pb(i + 1);
        }
    }
    
    for(int i = 1; i<=n; i++) {
        if(a[i] < b[i]) continue;
        int tmp = acnt[a[i]] - acnt[b[i]];
        ans += tmp;
    }
    s.clear(); s.pb('0');
    int cnt = 0;
    for(int i = 1; i<=n; i++) {
        while(cnt < acnt[max(a[i], b[i])]) {
            s.pb('A');
            cnt++;
        }
        s.pb('B');
    }
    a.clear(); b.clear(); a.pb(0); b.pb(0);
    // cout<<s<<"\n";
    // cout<<ans<<"\n";
    for(int i = 1; i<=2*n; i++) {
        acnt[i] = acnt[i - 1] + (s[i] == 'A');
        if(s[i] == 'A') {
            a.pb(i);
        }
        else {
            b.pb(i);
        }
    }
    // for(int i = 1; i<=n; i++) {
    //     cout<<a[i]<<" "<<b[i]<<"\n";
    // }
    dp.assign(n + 1, INF);
    dpn.assign(n + 1, INF);
    dp[0] = 0;
    for(int k = 1; k<=K; k++) {
        for(int i = 1; i<=n; i++) {
            dpn[i] = INF;
            int cost = 0;
            for(int j = i - 1; j >= 0; j--) {
                // cout<<"i:"<<i<<" j:"<<j<<" cost:"<<cost<<"\n";
                if(a[i] > b[j + 1]) {
                    cost += acnt[a[i]] - acnt[b[j + 1]];
                } 
                dpn[i] = min(dpn[i], cost + dp[j]);
            }   
        }
        swap(dp, dpn);
    }
    cout<<dp[n] + ans<<"\n";
}
 
signed main() {

    //fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

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