#include "bits/stdc++.h"
using namespace std;
const int N=400001;
#define all(x) x.begin(), x.end()
int n;
string s;
long long ps[N];
int ind[N];
vector<int> black, white;
void solve(int i){
// cout << "solve " << i << "\n";
auto add=[&](int l, int r, int v){
// cout << "add " << v << " to " << l << "-" << r << "\n";
if(r<l) r+=n;
ps[l]+=v;
ps[r+1]-=v;
};
if(s[i]=='B'){
auto pain=[&](int j)->int{
// cout << ind[i] << "-" << j << "=" << (ind[i]-j+n)%n << "\n";
return (ind[i]-j+n)%n;
};
// (i, i+m)
int cw1=*lower_bound(all(white), i);
int cw2=*--upper_bound(all(white), i+n);
// cout << "er " << cw1 << " " << cw2 << "\n";
if(cw1-i<=n){
int l=ind[cw1%(2*n)], r=ind[cw2%(2*n)];
// cout << "lr " << l << " " << r << "\n";
add(pain(r), pain(l), -i);
if(i>=n && cw2>=2*n){
int k=*white.begin();
add(pain(r), pain(ind[k]), 2*n);
}
}
// (i+m ,i+n)
if(upper_bound(all(white), i+n)==white.end()) return;
int cc1=*upper_bound(all(white), i+n);
int cc2=*--lower_bound(all(white), i+2*n);
if(cc1<i+2*n){
int l=ind[cc1%(2*n)], r=ind[cc2%(2*n)];
add(pain(r), pain(l), i);
if(i<n-1 && cc1<2*n){
int k=*--lower_bound(all(white), 2*n);
add(pain(ind[k]), pain(l), 2*n);
}
}
}
else{
auto pain=[&](int j)->int{
return (j-ind[i]+n)%n;
};
// (i, i+m)
int cw1=*lower_bound(all(black), i);
int cw2=*--lower_bound(all(black), i+n);
if(cw1-i<=n){
int l=ind[cw1%(2*n)], r=ind[cw2%(2*n)];
add(pain(l), pain(r), -i);
// if(i>=n && cw2>=2*n){
// int k=*black.begin();
// add(pain(ind[k]), pain(r), 2*n);
// }
}
// (i+m ,i+n)
int cc1=*lower_bound(all(black), i+n);
int cc2=*--lower_bound(all(black), i+2*n);
if(cc1<i+2*n){
int l=ind[cc1%(2*n)], r=ind[cc2%(2*n)];
add(pain(l), pain(r), i);
// if(i<n-1 && cc1<2*n){
// int k=*--lower_bound(all(black), 2*n);
// add(pain(l), pain(ind[k]), 2*n);
// }
}
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> s;
s+=s;
int w=0, b=0;
for(int i=0; i<2*n; i++){
if(s[i]=='W'){
ind[i]=w;
w++;
}
else{
ind[i]=b;
b++;
}
}
for(int i=0; i<4*n; i++){
if(s[i%(2*n)]=='W') white.push_back(i);
else black.push_back(i);
}
for(int i=0; i<2*n; i++) solve(i);
for(int i=1; i<2*n; i++) ps[i]+=ps[i-1];
long long ans=0;
for(int i=0; i<n; i++){
// cout << ps[i]+ps[i+n]-n << "\n";
ans=max(ans, ps[i]+ps[i+n]);
}
cout << (ans-n)/2;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
320 KB |
Output is correct |
2 |
Correct |
0 ms |
316 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
11 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
320 KB |
Output is correct |
2 |
Correct |
0 ms |
316 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
11 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
320 KB |
Output is correct |
2 |
Correct |
0 ms |
316 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
11 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
320 KB |
Output is correct |
2 |
Correct |
0 ms |
316 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
11 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |