Submission #1147440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147440		ParsaGolestani	Chorus (JOI23_chorus)	C++20	40 / 100	92 ms	4424 KiB

chorus

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

typedef long long ll;

const int N = 500;
const ll INF = 1'000'000'000'000'000;

int n, k, a[N + 10], id[N + 10];
ll pre[N + 10][N + 10];
ll dp[N + 10][N + 10];
ll base;

void readInput() {
    cin >> n >> k;
    int x = 0, cntA = 0;
    for (int i = 1; i <= n + n; i++) {
        char c;
        cin >> c;
        if (c == 'B')
            x++;
        else {
            id[++cntA] = min(n, x + 1);
            a[min(n, x + 1)]++;
            if (x == n)
                base++;
        }
    }
}

void calcPre() {
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n + 1; j++) {
            pre[i][j] = pre[i][j - 1] + max(0, id[j - 1] - i);
        }
}

void calcDP() {
    for (int i = 2; i <= n + 1; i++) {
        dp[i][0] = INF;
        for (int j = 1; j <= n; j++) {
            dp[i][j] = INF;
            for (int x = 1; x < i; x++)
                dp[i][j] = min(dp[i][j], dp[x][j - 1] + pre[x][i]);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcPre();
    calcDP();
    cout << dp[n + 1][k] + base << flush;
    return 0;
}

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