Submission #767418

#TimeUsernameProblemLanguageResultExecution timeMemory
767418PurpleCrayonChorus (JOI23_chorus)C++17
16 / 100
63 ms2900 KiB
#include <bits/stdc++.h> using namespace std; #define sz(v) int(v.size()) #define ar array typedef long long ll; const int N = 5e3+10, MOD = 1e9+7; int n, K, small[N]; int ps[N], l_use[N]; vector<int> one, two; int dp[N][N]; void solve() { cin >> n >> K; for (int i = 0; i < 2 * n; i++) { char c; cin >> c; if (c == 'A') one.push_back(i); else two.push_back(i); } // for (int x : one) cerr << x << ' '; cerr << endl; // for (int x : two) cerr << x << ' '; cerr << endl; for (int i = 0; i < n; i++) { small[i] = lower_bound(two.begin(), two.end(), one[i]) - two.begin(); } for (int i = 0; i < n; i++) { ps[i] = small[i] + (i ? ps[i-1] : 0); l_use[i] = -(i ? ps[i-1] : 0); for (int j = i; j < n; j++) { if (small[j] < i) { l_use[i] -= small[j] - i; } } } // -l * (r - l + 1) + ps_small[r] - other_ps_small[l-1] // other_ps_small[l-1] = (small[r] < l ? // for (int i = 0; i < n; i++) cerr << small[i] << ' '; // cerr << endl; /* for (int l = 0; l < n; l++) { int cur = 0; for (int r = l; r < n; r++) { cur += max(small[r] - l, 0); cost[l][r] = cur; cerr << l << ' ' << r << ' ' << cost[l][r] << ' ' << (ps[r] + l_use[l]) - l * (r - l + 1) << '\n'; } } */ auto COST = [&](int l, int r) { return ps[r] + l_use[l] - l * (r - l + 1); }; for (int i = 0; i < n; i++) for (int j = 0; j <= K; j++) dp[i][j] = MOD; for (int i = 0; i < n; i++) { for (int l = i; l >= 0; l--) { for (int k = 1; k <= K; k++) { int prv = MOD; if (l == 0) prv = (k == 1 ? 0 : MOD); else prv = dp[l-1][k-1]; dp[i][k] = min(dp[i][k], COST(l, i) + prv); } } } cout << dp[n-1][K] << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T = 1; // cin >> T; while (T--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...