#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=2e5+5;
int n, cws[N], cbs[N], cwt[N], cbt[N];
bool g[N], h[N];
ll BW(const string &s, const string &t){
int m=s.size();
vector<int>ws, bs, wt, bt;
for(int i=1;i<=m;++i){
cws[i]=cws[i-1];
cbs[i]=cbs[i-1];
cwt[i]=cwt[i-1];
cbt[i]=cbt[i-1];
if(s[i-1]=='W'){
ws.push_back(i);
++cws[i];
}
else{
bs.push_back(i);
++cbs[i];
}
if(t[i-1]=='B'){
bt.push_back(i);
++cbt[i];
}
else{
wt.push_back(i);
++cwt[i];
}
}
/*if(m==16){
for(int i=0;i<=m;++i)
cout<<cws[i]<<' '<<cbs[i]<<' '<<cwt[i]<<' '<<cbt[i]<<'\n';
}*/
ll ans=0;
for(int i=0;i<ws.size();++i){
int x=ws[i], y=bt[bt.size()-i-1];
int xyz=ans;
/*if(m==16){
cout<<x<<' '<<y<<" : ";
}*/
ans+=min(cws[x-1], cbt[m]-cbt[y])+min(cbs[x-1], cwt[m]-cwt[y])+min(cws[m]-cws[x], cbt[y-1])+min(cbs[m]-cbs[x], cwt[y-1]);
/* if(m==16){
cout<<ans-xyz<<'\n';
}*/
}
for(int i=0;i<bs.size();++i){
int x=bs[i], y=wt[wt.size()-i-1];
int xyz=ans;
/*if(m==16){
cout<<x<<' '<<y<<" : ";
}*/
ans+=min(cws[x-1], cbt[m]-cbt[y])+min(cbs[x-1], cwt[m]-cwt[y])+min(cws[m]-cws[x], cbt[y-1])+min(cbs[m]-cbs[x], cwt[y-1]);
/*if(m==16){
cout<<ans-xyz<<"\n";
}*/
}
return ans/2;
}
ll BW(const int &k, const string &s, const string &t){
//cout<<"-------------------------------------\n";
vector<int>ws, bs, wt, bt;
memset(g, 1, sizeof(g));
memset(h, 1, sizeof(h));
for(int i=0;i<n;++i){
//cout<<i<<'\n';
if(ws.size()<k && s[i]=='W'){
ws.push_back(i);
g[i]=0;
}
if(bt.size()<k && t[i]=='B'){
bt.push_back(i);
h[i]=0;
}
}
for(int i=n-1;i>=0;--i){
if(bs.size()<k && s[i]=='B'){
bs.push_back(i);
g[i]=0;
}
if(wt.size()<k && t[i]=='W'){
wt.push_back(i);
h[i]=0;
}
}
//cout<<"ok\n";
reverse(all(bs));
reverse(all(wt));
//cout<<k<<'\n';
if(ws.size()!=k || wt.size()!=k || (k>0 && (ws[k-1]>bs[0] || bt[k-1]>wt[0])))
return 0;
//cout<<"nok\n";
ll ans=-1LL*k*(k-1);
for(int i=0;i<k;++i){
ans+=bs[0]-ws[0]-1;
ans+=wt[0]-bt[0]-1;
}
/* if(k==5){
cout<<"how : \n";
for(int z: ws)
cout<<z<<' ';
cout<<'\n';
for(int z: bs)
cout<<z<<' ';
cout<<'\n';
for(int z: wt)
cout<<z<<' ';
cout<<'\n';
for(int z: bt)
cout<<z<<' ';
cout<<'\n';
}*/
string ss="", tt="";
for(int i=0;i<n;++i){
if(g[i])
ss+=s[i];
if(h[i])
tt+=t[i];
}
//cout<<ans<<" : "<<ss<<" "<<tt<<'\n';
ans+=BW(ss, tt);
//cout<<ans<<'\n';
return ans;
}
int main(){
//ios_base::sync_with_stdio(0); cin.tie(0);
string s, t;
cin>>n>>s;
if(n>3000)
return 0;
t="";
for(int i=n;i<2*n;++i)
t+=s[i];
ll ans=0;
for(int i=0;2*i<=n;++i){
ans=max(ans, BW(i, s, t));
ans=max(ans, BW(i, t, s));
}
cout<<ans<<'\n';
}
Compilation message
monochrome.cpp: In function 'll BW(const string&, const string&)':
monochrome.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i=0;i<ws.size();++i){
| ~^~~~~~~~~~
monochrome.cpp:45:13: warning: unused variable 'xyz' [-Wunused-variable]
45 | int xyz=ans;
| ^~~
monochrome.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=0;i<bs.size();++i){
| ~^~~~~~~~~~
monochrome.cpp:56:13: warning: unused variable 'xyz' [-Wunused-variable]
56 | int xyz=ans;
| ^~~
monochrome.cpp: In function 'll BW(const int&, const string&, const string&)':
monochrome.cpp:75:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
75 | if(ws.size()<k && s[i]=='W'){
| ~~~~~~~~~^~
monochrome.cpp:79:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
79 | if(bt.size()<k && t[i]=='B'){
| ~~~~~~~~~^~
monochrome.cpp:85:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
85 | if(bs.size()<k && s[i]=='B'){
| ~~~~~~~~~^~
monochrome.cpp:89:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
89 | if(wt.size()<k && t[i]=='W'){
| ~~~~~~~~~^~
monochrome.cpp:98:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
98 | if(ws.size()!=k || wt.size()!=k || (k>0 && (ws[k-1]>bs[0] || bt[k-1]>wt[0])))
| ~~~~~~~~~^~~
monochrome.cpp:98:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
98 | if(ws.size()!=k || wt.size()!=k || (k>0 && (ws[k-1]>bs[0] || bt[k-1]>wt[0])))
| ~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
