Submission #1094350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094350		_8_8_	Chorus (JOI23_chorus)	C++17	Compilation error	0 ms	0 KiB

chorus

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 1e6 + 12, MOD = (int)1e9 + 7;

int n, k, x[N], y[N], pref[2 * N], col[N], opt[N], s[N];
ll dp[N];
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(pref[y[j]] > pref[x[i]] ) continue;
            ll cost = pref[x[i]] * 1ll * (i - j + 1) - s[i] + s[j - 1];
            if(dp[j - 1] + cost + 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]};
}
// pair<ll, ll> calc(ll pen) {
//     for(int i = 1; i <= n; i++) {

//     }
// }
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;
        }
    }
    for(int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + pref[y[i]];
    }
    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 << '\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 'std::pair<long long int, long long int> calc_slow(ll)':
chorus.cpp:18:37: error: 'c' was not declared in this scope
   18 |                 dp[i] = dp[j - 1] + c[j][i] + pen;
      |                                     ^