Submission #1156552

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

chorus

//fucked up.
#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[maxn];

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));
        }
    }

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

    int ans = 0;
    while (merge--) {
        for (int i=0;i<sz;i++) SZ[i] = vec[i].first;
        for (int i=1;i<n;i++) if (sel[i]) SZ[i] += SZ[i-1];
        for (int i=n-2;i>=0;i--) if (sel[i+1]) SZ[i] = SZ[i+1];
        pair<int,int> curans1 = {INF, INF};
        for (int i=1;i<sz;i++) if (!sel[i]) {
            int cost = SZ[i] * SZ[i-1] - vec[i].second;
            curans1 = min(make_pair(cost, i), curans1);
        }
        pair<int,int> curans2 = {INF, INF};
        for (int i=2;i<sz-1;i++) if (!sel[i-1] && sel[i] && !sel[i+1]) {
            int cost = (vec[i-1].first * SZ[i-2] - vec[i-1].second) + (SZ[i+1] * vec[i].first - vec[i+1].second) - (vec[i].first * vec[i-1].first - vec[i].second);
            curans2 = min(make_pair(cost, i), curans2);
        }
        if (curans1.first < curans2.first) {
            ans += curans1.first;
            sel[curans1.second] = 1;
        } else {
            ans += curans2.first;
            int i = curans2.second;
            sel[i-1] = sel[i+1] = 1, sel[i] = 0;
        }
        // cout << ans << endl;
        // for (int i=0;i<sz;i++) cout << sel[i]; cout << endl;
        // for (int i=0;i<sz;i++) cout << SZ[i] << " "; cout << endl;
    }
    cout << ans + init << "\n";
}

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