Submission #1094355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094355		_8_8_	Chorus (JOI23_chorus)	C++17	61 / 100	2427 ms	117876 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];
ll dp[N], c[N][N];
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];;
            }
        }
    }
    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]);
        }
    }
}
ll add[N * 4];
pair<ll, int> t[N * 4];
void inc(int v, int val) {
    add[v] += val;
    t[v].first += val;
}
void push(int v, int tl, int tr) {
    if(add[v]) {
        int tm = (tl + tr) >> 1;
        inc(v + v, add[v]);
        inc(v + v + 1, add[v]);
        add[v] = 0;
    }
}
void upd(int l, int r, int val, int v = 1, int tl = 1, int tr = n) {
    if(l > r || tl > r || l > tr) return;
    if(tl >= l && tr <= r) {
        inc(v, val);
    } else {
        push(v, tl, tr);
        int tm = (tl + tr) >> 1;
        upd(l, r, val, v + v, tl, tm);
        upd(l, r, val, v + v + 1, tm + 1, tr);
        t[v] = min(t[v + v], t[v + v + 1]);
    }
}
void upd1(int pos, ll val, int v = 1, int tl = 1, int tr = n) {
    if(tl == tr) {
        t[v].first += val;
        t[v].second = tl;
    }  else {
        push(v, tl, tr);
        int tm = (tl + tr) >> 1;
        if(pos <= tm) upd1(pos, val, v + v, tl, tm);
        else upd1(pos, val, v + v + 1, tm + 1,tr);
        t[v] = min(t[v + v], t[v + v + 1]);
    }
}
const ll inf = 1e18;
pair<ll, ll> get(int l, int r, int v = 1, int tl = 1, int tr = n) {
    if(l > r || tl > r || l > tr) return {inf, inf};
    if(tl >= l && tr <= r) return t[v];
    push(v, tl, tr);
    int tm = (tl + tr) >> 1;
    return min(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}   
pair<ll, ll> calc1(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;
            }
        }
        assert(opt[i] >= opt[i - 1]);
        // cout << dp[i] << '\n';
    }
    return {dp[n], col[n]};
}
pair<ll, ll> calc(ll pen) {
    for(int i = 1; i <= n * 4; i++) {
        add[i] = 0;
        t[i] = {0, 0};
    }

    int it = 1;
    for(int i = 1; i <= n; i++) {
        dp[i] = 1e18;
        col[i] = n + 1;
        upd1(i, dp[i - 1]);
        while(it <= n && y[it] < x[i]) {
            upd(1, it, 1);
            it++;
        }
        auto [val, j] = get(1, i);
        dp[i] = val - pen;
        col[i] = col[j - 1] + 1;
        // cout << i << ' ' << dp[i] << ' ' << j << '\n';
    }
    return {dp[n], col[n]};
}
void test() {
    cin >> n >> k;
    int _x = 0, _y = 0;
    for(int i = 1; i <= n + n; i++) {
        char a;
        cin >> a;
        pref[i] = pref[i - 1];
        if(a == 'A') {
            x[++_x] = i;
            pref[i]++;
        } else { 
            y[++_y] = i;
        }
    }
    prec();
    // calc(0);
    // calc1(0);
    // return;
    ll l = -1e12, r = 1, res;
    while(r - l > 1) { 
        ll mid = (l + r) / 2;
        auto [val, t] = calc1(mid);
        // cout << mid << ' ' << val << ' ' << t << '\n';
        if(t > k) {
            r = mid;
        } else {
            l = mid;
            res = val + k * 1ll * mid;
        }
    }
    cout << res << '\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 push(int, int, int)':
chorus.cpp:33:13: warning: unused variable 'tm' [-Wunused-variable]
   33 |         int tm = (tl + tr) >> 1;
      |             ^~

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