This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
assert(pref[max(x[i], y[i])] - pref[min(x[j], y[j]) - 1] == i - j + 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:96:19: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
96 | cout << res + add << '\n';
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |