Submission #961888

#	Time	Username	Problem	Language	Result	Execution time	Memory
961888		RaresFelix	Chorus (JOI23_chorus)	C++17	40 / 100	7045 ms	268864 KiB

chorus

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;

#define int ll

using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;


signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, k;
    string s;
    cin >> n >> k >> s;
    int nrB = 0;
    vi A;
    for(int i = 0; i < 2 * n; ++i) {
        if(s[i] == 'B') ++nrB;
        else A.push_back(nrB);
    }
    const int INF = 1e9;
    vector<vi> Cost(n, vi(n, 0));
    for(int i = 0; i < n; ++i) {
        for(int j = i; j < n; ++j) {
            Cost[i][j] = max(0ll, A[j] - i);
            if(j) Cost[i][j] += Cost[i][j - 1];
        }
    }
    vector<vi> DP(n, vi(k + 1, INF));
    for(int i = 0; i < n; ++i) {
        for(int j = 1; j <= k; ++j) {
            if(j == 1) DP[i][j] = Cost[0][i];
            for(int ant = 1; ant <= i; ++ant) {
                DP[i][j] = min(DP[i][j], DP[ant - 1][j - 1] + Cost[ant][i]);
            }
        }
    }
    cout << DP[n - 1][k] << "\n";
    return 0;
}

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