Submission #1156612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156612		Sharky	Chorus (JOI23_chorus)	C++20	40 / 100	7091 ms	190024 KiB

chorus

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long
#define fi first
#define se second

#define L(i, j, k) for (int i = (j); i <= (k); i++)
#define R(i, j, k) for (int i = (j); i >= (k); i--)
#define all(x) x.begin(), x.end()

const int inf = 1e18;

void solve() {
    int n, req;
    string s;
    cin >> n >> req >> s;
    vector<vector<int>> dp(n+1, vector<int> (n+1, inf));
    vector<int> pre(n+1, inf);
    int ca = 0, cb = 0;
    for (int i = 0; i < 2 * n; i++) {
        if (s[i] == 'A') ca++, pre[ca] = cb;
        else if (s[i] == 'B') cb++;
    }
    dp[0][0] = 0;
    for (int k = 0; k <= n; k++) {
        for (int i = 0; i < n; i++) {
            int cur = 0;
            for (int j = 1; j <= n - i; j++) {
                cur += max(0LL, pre[i + j] - i);
                dp[i + j][k + 1] = min(dp[i + j][k + 1], dp[i][k] + cur);
            }
        }
    }
    cout << dp[n][req] << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    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