Submission #1094838

#TimeUsernameProblemLanguageResultExecution timeMemory
1094838_8_8_Chorus (JOI23_chorus)C++17
61 / 100
2471 ms117904 KiB
#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], 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(pref[x[i]] - pref[min(x[j], y[j]) - 1] != i - j + 1) { exit(-1); } if(y[j] <= x[i]) { c[j][i] += pref[x[i]] - pref[y[j] - 1];; } } } //monge 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]}; } void test() { cin >> n >> k; int _x = 0, _y = 0; string s; cin >> s; make(s); for(int i = 1; i <= n + n; i++) { char a = s[i - 1]; pref[i] = pref[i - 1]; if(a == 'A') { x[++_x] = i; pref[i]++; } else { y[++_y] = 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:98:19: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     cout << res + add << '\n';
      |                   ^~~
#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...