Submission #1094855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094855		_8_8_	Chorus (JOI23_chorus)	C++17	0 / 100	1 ms	596 KiB

chorus

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 5e3 + 12, MOD = (int)1e9 + 7;
 
int n, k, x[N], y[N], pref[ 2 * N], col[N], opt[N], sum[N];
ll dp[N], c[N][N], add = 0;

void make(string &s) {
    string t;
    deque<int> bf;
    int bal = 0;
    for(int i = 0; i < n + n; i++) {
        if(s[i] == 'A') {
            bal++;
            t += 'A';
            if(!bf.empty()) {
                int j = bf[0];
                add += (int)bf.size();
                t += 'B';
                bal--;
                bf.pop_front();
            }
        } else {
            if(bal) {
                bal--;
                t += 'B';
            } else {
                bf.push_back(i);
            }
        }
    }
    s = t;
}
void prec() {
    for(int i = 1; i <= n; i++) {
        for(int j = i; j >= 1; j--) {
            c[j][i] = c[j + 1][i];
            if(y[j] <= x[i]) {
                c[j][i] += pref[x[i]] - pref[y[j] - 1];;
            }
            ll cnt = pref[x[i]] - pref[y[j] - 1], cst = - cnt * (cnt - 1) / 2;
            cst += x[i] * cnt;
            cst -= (sum[x[i]] - sum[y[j] - 1]);
        }
    }
    for(int i = 1; i < n; i++) {
        for(int j = 1; j < n; j++) {
            assert(c[i][j + 1] + c[i + 1][j] >= c[i][j] + c[i + 1][j + 1]);
        }
    }
}
pair<ll, ll> calc_slow(ll pen) {
    for(int i = 1; i <= n; i++) {
        dp[i] = 1e18;
        col[i] = n + 1;
        for(int j = i; j >= 1; j--) {
            if(dp[j - 1] + c[j][i] + pen <= dp[i]) {
                dp[i] = dp[j - 1] + c[j][i] + pen;
                col[i] = col[j - 1] + 1;
                opt[i] = j;
            }
        }
    }
    return {dp[n], col[n]};
}

ll str[N], val[N], str_[N], val_[N];
void dodo(string &s) {
    string t;
    deque<int> c, d;
    for(int i = 0; i < n + n; i++) {
        if(s[i] == 'A') {
            c.push_back(i);
        } else {
            d.push_back(i);
        }
    }
    vector<pair<int, char>> xx;
    for(int i = 0; i < n; ) {
        int j = i + 1, col = 1;
        ll f = d[i] + 1;
        while(j < n && c[j] < d[i]) {
            f += d[j] + 1;
            j++;
            col++;
        }
        str_[d[i] + 1] = col;
        val_[d[i] + 1] = f;
        xx.push_back({c[i], 'A'});
        xx.push_back({d[i], 'B'});
        i = j;
    }
    sort(xx.begin(), xx.end());
    for(int i = 0; i < (int)xx.size(); i++) {
        t += xx[i].second;
        if(xx[i].second == 'B') {
            str[i + 1] = str_[xx[i].first + 1];
            val[i + 1] = val[xx[i].first + 1];
        }
    }
    s = t;
    n = (int)s.size() / 2;
}
void test() {
    cin >> n >> k;
    int _x = 0, _y = 0;
    string s;
    cin >> s;
    // cout << s << '\n';
    make(s);
    // cout << s << '\n';
    dodo(s);
    // cout << s << '\n';
    for(int i = 1; i <= n + n; i++) {
        char a = s[i - 1];
        pref[i] = pref[i - 1];
        sum[i] = sum[i - 1];
        if(a == 'A') {
            x[++_x] = i;
        } else { 
            y[++_y] = i;
            // cout << str[i] << ' ' << val[i] << '\n';
            pref[i] += str[i];
            sum[i] += val[i];
        }
    }
    prec();
    ll l = -1, r = 1e12, res;
    while(r - l > 1) { 
        ll mid = (l + r) / 2;
        auto [val, t] = calc_slow(mid);
        if(t <= k) {
            r = mid;
            res = val - k * 1ll * mid;
        } else {
            l = mid;
        }
    }
    cout << res + add << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    return 0;
}

Compilation message (stderr)

chorus.cpp: In function 'void make(std::string&)':
chorus.cpp:20:21: warning: unused variable 'j' [-Wunused-variable]
   20 |                 int j = bf[0];
      |                     ^
chorus.cpp: In function 'void test()':
chorus.cpp:142:19: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  142 |     cout << res + add << '\n';
      |                   ^~~

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