Submission #963049

#	Time	Username	Problem	Language	Result	Execution time	Memory
963049		RaresFelix	Chorus (JOI23_chorus)	C++17	40 / 100	7104 ms	79452 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;
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>;

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n, k;
    cin >> n >> k;

    string s0, s;
    cin >> s0;
    ll re0 = 0;
    int nrB = 0, sum = 0;
    for(auto it : s0) {
        if(it == 'A') {
            ++sum;
            s += 'A';
            re0 += nrB;
            if(nrB && sum) {
                s += 'B';
                --nrB;
                --sum;
            }
        } else {
            if(sum) {
                s += 'B';
                --sum;
            } else {
                ++nrB;
            }
        }
    }

    vi A, P(n + 1);
    vll SA;
    P[0] = -1;
    for(auto it : s) {
        if(it == 'A'){
            A.push_back(nrB);
            if(SA.empty())
                SA.push_back(A.back());
            else
                SA.push_back(A.back() + SA.back());
        } 
        else {
            ++nrB;
            P[nrB] = (int)A.size() - 1;
        }
    }

    auto cost = [&](ll st, ll dr) {
        ll sa = 0;
        if(P[st] != -1) sa = SA[P[st]];
        return st * P[st] - sa - st * dr + SA[dr];
    };

    const ll INF = 1e18;

    vector<vll> DP(n, vll(k + 1, INF));

    for(int i = 0; i < n; ++i) {
        DP[i][1] = cost(0, i);
        for(int j = 2; j <= k; ++j)
            for(int p = 1; p <= i; ++p)
                DP[i][j] = min(DP[i][j], DP[p - 1][j - 1] + cost(p, i));
    }

    ll re = INF;
    for(auto it : DP[n - 1]) re = min(re, it);

    cout << re + re0 << "\n";
    return 0;
}

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