#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
struct fenwick{
vector<int> tree;
int n;
fenwick(int n):n(n),tree(n+1){}
void add(int k,int x){
while(k<=n){
tree[k]+=x;
k+=k&-k;
}
}
void reset(){
fill(tree.begin(),tree.end(),0ll);
}
int get(int k){
int ans = 0;
while(k){
ans+=tree[k];
k-=k&-k;
}
return ans;
}
};
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,k;
cin >> n >> k;
string s;
cin >> s;
s.insert(s.begin(),'$');
vector<int> posA(n+1);
vector<int> posB(n+1);
int cntA = 0,cntB = 0;
for(int i=1;i<=2*n;i++){
if(s[i]=='A'){
posA[++cntA]=i;
} else {
posB[++cntB]=i;
}
}
fenwick addedA(2*n);
fenwick addedB(2*n);
auto solvemax = [&](int penalty){
vector<pair<int,int>> DP(n+1,{INF,-INF});
DP[0]={0,0};
for(int i=1;i<=n;i++){
int ans = penalty;
addedA.reset();
addedB.reset();
for(int j=i+1;j<=n;j++)addedB.add(posB[j],1);
for(int j=i;j;j--){
ans+=i-j-addedA.get(posB[j]);
addedB.add(posB[j],1);
ans+=addedB.get(posA[j]);
addedA.add(posA[j],1);
DP[i]=min(DP[i],{DP[j-1].first+ans,DP[j-1].second-1});
}
}
DP[n].second*=-1ll;
return DP[n];
};
auto solvemin = [&](int penalty){
vector<pair<int,int>> DP(n+1,{INF,-INF});
DP[0]={0,0};
for(int i=1;i<=n;i++){
int ans = penalty;
addedA.reset();
addedB.reset();
for(int j=i+1;j<=n;j++)addedB.add(posB[j],1);
for(int j=i;j;j--){
ans+=i-j-addedA.get(posB[j]);
addedB.add(posB[j],1);
ans+=addedB.get(posA[j]);
addedA.add(posA[j],1);
DP[i]=min(DP[i],{DP[j-1].first+ans,DP[j-1].second+1});
}
}
return DP[n];
};
auto solve = [&](int penalty){
auto mini = solvemin(penalty);
auto maxi = solvemax(penalty);
if(mini.second>k)return mini;
if(maxi.second<=k)return maxi;
return make_pair(mini.first,k);
};
int best_penalty = -1;
for(int jump=(1ll<<40);jump;jump/=2ll){
if(solve(best_penalty+jump).second>k)best_penalty+=jump;
}
// for(int i=0;i<=10;i++)cout<<solve(i).second<<'\n';
best_penalty++;
cout << solve(best_penalty).first-solve(best_penalty).second*best_penalty << '\n';
}
Compilation message
chorus.cpp: In constructor 'fenwick::fenwick(long long int)':
chorus.cpp:11:6: warning: 'fenwick::n' will be initialized after [-Wreorder]
11 | int n;
| ^
chorus.cpp:10:14: warning: 'std::vector<long long int> fenwick::tree' [-Wreorder]
10 | vector<int> tree;
| ^~~~
chorus.cpp:12:2: warning: when initialized here [-Wreorder]
12 | fenwick(int n):n(n),tree(n+1){}
| ^~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
23 ms |
464 KB |
Output is correct |
18 |
Correct |
192 ms |
344 KB |
Output is correct |
19 |
Correct |
231 ms |
348 KB |
Output is correct |
20 |
Correct |
213 ms |
464 KB |
Output is correct |
21 |
Correct |
217 ms |
348 KB |
Output is correct |
22 |
Correct |
216 ms |
464 KB |
Output is correct |
23 |
Correct |
226 ms |
596 KB |
Output is correct |
24 |
Correct |
185 ms |
344 KB |
Output is correct |
25 |
Correct |
190 ms |
344 KB |
Output is correct |
26 |
Correct |
181 ms |
344 KB |
Output is correct |
27 |
Correct |
196 ms |
344 KB |
Output is correct |
28 |
Correct |
187 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
23 ms |
464 KB |
Output is correct |
18 |
Correct |
192 ms |
344 KB |
Output is correct |
19 |
Correct |
231 ms |
348 KB |
Output is correct |
20 |
Correct |
213 ms |
464 KB |
Output is correct |
21 |
Correct |
217 ms |
348 KB |
Output is correct |
22 |
Correct |
216 ms |
464 KB |
Output is correct |
23 |
Correct |
226 ms |
596 KB |
Output is correct |
24 |
Correct |
185 ms |
344 KB |
Output is correct |
25 |
Correct |
190 ms |
344 KB |
Output is correct |
26 |
Correct |
181 ms |
344 KB |
Output is correct |
27 |
Correct |
196 ms |
344 KB |
Output is correct |
28 |
Correct |
187 ms |
348 KB |
Output is correct |
29 |
Execution timed out |
7039 ms |
604 KB |
Time limit exceeded |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
23 ms |
464 KB |
Output is correct |
18 |
Correct |
192 ms |
344 KB |
Output is correct |
19 |
Correct |
231 ms |
348 KB |
Output is correct |
20 |
Correct |
213 ms |
464 KB |
Output is correct |
21 |
Correct |
217 ms |
348 KB |
Output is correct |
22 |
Correct |
216 ms |
464 KB |
Output is correct |
23 |
Correct |
226 ms |
596 KB |
Output is correct |
24 |
Correct |
185 ms |
344 KB |
Output is correct |
25 |
Correct |
190 ms |
344 KB |
Output is correct |
26 |
Correct |
181 ms |
344 KB |
Output is correct |
27 |
Correct |
196 ms |
344 KB |
Output is correct |
28 |
Correct |
187 ms |
348 KB |
Output is correct |
29 |
Execution timed out |
7039 ms |
604 KB |
Time limit exceeded |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
23 ms |
464 KB |
Output is correct |
18 |
Correct |
192 ms |
344 KB |
Output is correct |
19 |
Correct |
231 ms |
348 KB |
Output is correct |
20 |
Correct |
213 ms |
464 KB |
Output is correct |
21 |
Correct |
217 ms |
348 KB |
Output is correct |
22 |
Correct |
216 ms |
464 KB |
Output is correct |
23 |
Correct |
226 ms |
596 KB |
Output is correct |
24 |
Correct |
185 ms |
344 KB |
Output is correct |
25 |
Correct |
190 ms |
344 KB |
Output is correct |
26 |
Correct |
181 ms |
344 KB |
Output is correct |
27 |
Correct |
196 ms |
344 KB |
Output is correct |
28 |
Correct |
187 ms |
348 KB |
Output is correct |
29 |
Execution timed out |
7039 ms |
604 KB |
Time limit exceeded |
30 |
Halted |
0 ms |
0 KB |
- |