Submission #1156688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156688		onbert	Chorus (JOI23_chorus)	C++17	0 / 100	0 ms	328 KiB

chorus

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 5, INF = 1e18;

vector<pair<int,int>> vec;
bool sel[maxn];
int sz, mrge;

pair<int,int> solve(int mn, int mx) {
    pair<int,int> dp[sz+1];
    for (int i=0;i<=sz;i++) dp[i] = {INF, INF};
    dp[0] = {0, 0};
    for (int i=0;i<sz;i++) {
        int cur = 0, val = 0;
        for (int j=i;j<sz;j++) {
            val += cur * vec[j].first;
            if (j != i) val -= vec[j].second;
            cur += vec[j].first;
            if (val > mx || val < mn) continue;
            dp[j+1] = min(make_pair(dp[i].first + 1, dp[i].second + val), dp[j+1]);
            // cout << i << " " << j << " " << cur << " " << val << endl;
        }
        // cout << i << " " << dp[i].first << " " << dp[i].second << endl;
    }
    return dp[sz];
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k;
    cin >> n >> k;
    int cnt[n+2];
    for (int i=0;i<=n+1;i++) cnt[i] = 0;
    int cur = 1;
    for (int i=1;i<=2*n;i++) {
        char x;
        cin >> x;
        if (x == 'B') cur++;
        else cnt[cur]++;
    }
    int init = 0, cum = 0;
    for (int i=1;i<=n;i++) {
        cum += cnt[i];
        if (cum < i) {
            int need = i - cum;
            cnt[i+1] -= need, cnt[i] += need, cum += need;
            init += need;
        }
    }
    int u = 1;
    vec.push_back({cnt[1], 0});
    while (u < n) {
        int v = u + vec.back().first;
        vec.push_back({0, 0});
        for (; u < v; u++) {
            vec.back().first += cnt[u+1];
            vec.back().second += cnt[u+1] * (v - (u + 1));
        }
    }

    sz = vec.size(), mrge = sz - k;
    // cout << sz << endl;
    // for (auto [x, y]:vec) cout << x << " " << y << endl;


    int ans = 0;
    int l = 0, r = 1e18;
    while (l < r) {
        int mid = (l+r)/2;
        if (solve(0, mid).first <= k) r = mid;
        else l = mid+1;
    }
    int MX = l;
    l = 0, r = MX;
    while (l < r) {
        int mid = (l+r+1)/2;
        if (solve(mid, MX).first <= k) l = mid;
        else r = mid-1;
    }
    // cout << l << endl;

    cout << solve(l, MX).second + init << "\n";
}

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