Submission #1149091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149091		_8_8_	Chorus (JOI23_chorus)	C++17	40 / 100	7093 ms	732 KiB

chorus

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int  N = (int)1e6 + 10, MOD = 998244353, inf = (int)1e9;

int n, k, a[N], b[N], px[N * 2], py[N * 2], f[N * 2];
string s;

ll dop = 0;
void make() {
    int bal = 0;
    string ret;
    for(int i = 0, col = 0; i < n + n; ++i) {
        if(s[i] == 'A') {
            ret += s[i];
            dop += col;
            bal++;
        } else {
            if(bal) {
                bal--;
                ret += s[i];
            } else {
                col++;
            }
        }
        while(col && bal) {
            ret += 'B';
            bal--;
            col--;
        }
    }
    s = ret;
}
ll dp[N], col[N], pr[N];
int nxt[N];
pair<ll, int> solve(ll pen) {
    dp[0] = 0;
    col[0] = 0;
    for(int i = 1; i <= n; i++) {
        dp[i] = (ll)1e18;
    }
    int it = 0;
    for(int r = 1; r <= n; r++) {
        while(nxt[it] <= r) {
            it++;
        }
        for(int j = 0; j < r; j++) {
            ll u = dp[j] + pen /*+ (pr[r] - pr[nxt[j]]) - j * (r - nxt[j])*/;
            for(int k = j + 1; k <= r; k++) {
                u += max(0, f[a[k]] - j);
            }
            if(dp[r] > u) {
                dp[r] = u;
                col[r] = col[j] + 1;
            } else if(dp[r] == u) {
                col[r] = min(col[r], col[j] + 1);
            }
        }
    }
    return {dp[n], col[n]};
}
void test() {
    cin >> n >> k;
    cin >> s;
    make();
    int fx = 1, fy = 1;
    for(int i = 1; i <= n + n; i++) {
        if(s[i - 1] == 'A') {
            a[fx++] = i;
        } else {
            b[fy++] = i;
            f[i]++;
        }
    }
    for(int i = 1; i <= n + n; i++) {
        f[i] += f[i - 1];
    }
    for(int i = 1; i <= n; i++) {
        pr[i] = pr[i - 1] + f[a[i]];
    }
    for(int i = 0; i <= n; i++) {
        if(i) {
            nxt[i] = max(i + 1, nxt[i - 1]);
        } else {
            nxt[i] = i + 1;
        }
        while(nxt[i] <= n && f[a[nxt[i]]] < i) {
            nxt[i]++;
        }
    }
    // auto [x, y] = solve(0);
    // cout << x << ' ' << y;
    // return;
    ll l = -1, r = (ll)1e14, res;
    while(r - l > 1) {
        ll mid = (l + r) >> 1;
        auto [val, t] = solve(mid);
        if(t <= k) {
            r = mid;
            res = val - k * 1ll * mid;
        } else {
            l = mid;
        }
    }
    cout << res + dop << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    while(t--) {
        test();
    }
}

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