#include<bits/stdc++.h>
using namespace std;
int n, i, j, k, a, b;
long long ans=0;
char S[400010];
vector<int>A, B;
int tree[400010];
void init(){for(int i=1;i<=2*n;i++)tree[i]=0;}
void update(int pos, int v){while(pos<=2*n)tree[pos]+=v,pos+=(pos&-pos);}
int get(int pos){int res=0;while(pos)res+=tree[pos],pos-=(pos&-pos);return res;}
long long f(int i)
{
init();
vector<pair<int, int> >V;
for(int j=i;j<n;j++)V.push_back({A[j-i], B[j]});
for(int j=0;j<i;j++)V.push_back({A[j+n-i], B[j]});
for(auto &p:V)if(p.first>p.second)swap(p.first, p.second);
sort(V.begin(), V.end());
long long res=0;
for(auto p:V)
{
int a=p.second;
update(a, 1);
res+=get(a-1)-get(p.first);
}
ans=max(ans, res);
return res;
}
main()
{
scanf("%d", &n);
scanf("%s", &S);
for(i=0;i<2*n;i++)
{
if(S[i]=='B')A.push_back(i+1);
else B.push_back(i+1);
}
int a=0, b=n-1;
while(a+3<=b)
{
int m1=(a+a+b)/3, m2=(a+b+b)/3;
if(f(m1)>f(m2))b=m2;
else a=m1;
}
for(i=a;i<=b;i++)f(i);
cout<<ans;
}
Compilation message
monochrome.cpp:29:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
29 | main()
| ^~~~
monochrome.cpp: In function 'int main()':
monochrome.cpp:32:13: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[400010]' [-Wformat=]
32 | scanf("%s", &S);
| ~^ ~~
| | |
| | char (*)[400010]
| char*
monochrome.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
monochrome.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | scanf("%s", &S);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 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 |
204 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 |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 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 |
204 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 |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
1 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
204 KB |
Output is correct |
| 24 |
Correct |
1 ms |
204 KB |
Output is correct |
| 25 |
Correct |
1 ms |
204 KB |
Output is correct |
| 26 |
Correct |
1 ms |
204 KB |
Output is correct |
| 27 |
Correct |
1 ms |
204 KB |
Output is correct |
| 28 |
Correct |
1 ms |
204 KB |
Output is correct |
| 29 |
Correct |
1 ms |
204 KB |
Output is correct |
| 30 |
Correct |
1 ms |
204 KB |
Output is correct |
| 31 |
Correct |
1 ms |
204 KB |
Output is correct |
| 32 |
Correct |
1 ms |
204 KB |
Output is correct |
| 33 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 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 |
204 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 |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
1 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
204 KB |
Output is correct |
| 24 |
Correct |
1 ms |
204 KB |
Output is correct |
| 25 |
Correct |
1 ms |
204 KB |
Output is correct |
| 26 |
Correct |
1 ms |
204 KB |
Output is correct |
| 27 |
Correct |
1 ms |
204 KB |
Output is correct |
| 28 |
Correct |
1 ms |
204 KB |
Output is correct |
| 29 |
Correct |
1 ms |
204 KB |
Output is correct |
| 30 |
Correct |
1 ms |
204 KB |
Output is correct |
| 31 |
Correct |
1 ms |
204 KB |
Output is correct |
| 32 |
Correct |
1 ms |
204 KB |
Output is correct |
| 33 |
Correct |
1 ms |
204 KB |
Output is correct |
| 34 |
Correct |
5 ms |
332 KB |
Output is correct |
| 35 |
Correct |
5 ms |
372 KB |
Output is correct |
| 36 |
Correct |
6 ms |
332 KB |
Output is correct |
| 37 |
Correct |
6 ms |
332 KB |
Output is correct |
| 38 |
Correct |
4 ms |
372 KB |
Output is correct |
| 39 |
Correct |
4 ms |
332 KB |
Output is correct |
| 40 |
Correct |
4 ms |
332 KB |
Output is correct |
| 41 |
Correct |
4 ms |
372 KB |
Output is correct |
| 42 |
Correct |
5 ms |
332 KB |
Output is correct |
| 43 |
Correct |
4 ms |
332 KB |
Output is correct |
| 44 |
Correct |
5 ms |
332 KB |
Output is correct |
| 45 |
Correct |
4 ms |
332 KB |
Output is correct |
| 46 |
Correct |
4 ms |
372 KB |
Output is correct |
| 47 |
Correct |
5 ms |
376 KB |
Output is correct |
| 48 |
Correct |
5 ms |
372 KB |
Output is correct |
| 49 |
Correct |
4 ms |
368 KB |
Output is correct |
| 50 |
Correct |
4 ms |
332 KB |
Output is correct |
| 51 |
Correct |
5 ms |
332 KB |
Output is correct |
| 52 |
Correct |
6 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 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 |
204 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 |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
1 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
204 KB |
Output is correct |
| 24 |
Correct |
1 ms |
204 KB |
Output is correct |
| 25 |
Correct |
1 ms |
204 KB |
Output is correct |
| 26 |
Correct |
1 ms |
204 KB |
Output is correct |
| 27 |
Correct |
1 ms |
204 KB |
Output is correct |
| 28 |
Correct |
1 ms |
204 KB |
Output is correct |
| 29 |
Correct |
1 ms |
204 KB |
Output is correct |
| 30 |
Correct |
1 ms |
204 KB |
Output is correct |
| 31 |
Correct |
1 ms |
204 KB |
Output is correct |
| 32 |
Correct |
1 ms |
204 KB |
Output is correct |
| 33 |
Correct |
1 ms |
204 KB |
Output is correct |
| 34 |
Correct |
5 ms |
332 KB |
Output is correct |
| 35 |
Correct |
5 ms |
372 KB |
Output is correct |
| 36 |
Correct |
6 ms |
332 KB |
Output is correct |
| 37 |
Correct |
6 ms |
332 KB |
Output is correct |
| 38 |
Correct |
4 ms |
372 KB |
Output is correct |
| 39 |
Correct |
4 ms |
332 KB |
Output is correct |
| 40 |
Correct |
4 ms |
332 KB |
Output is correct |
| 41 |
Correct |
4 ms |
372 KB |
Output is correct |
| 42 |
Correct |
5 ms |
332 KB |
Output is correct |
| 43 |
Correct |
4 ms |
332 KB |
Output is correct |
| 44 |
Correct |
5 ms |
332 KB |
Output is correct |
| 45 |
Correct |
4 ms |
332 KB |
Output is correct |
| 46 |
Correct |
4 ms |
372 KB |
Output is correct |
| 47 |
Correct |
5 ms |
376 KB |
Output is correct |
| 48 |
Correct |
5 ms |
372 KB |
Output is correct |
| 49 |
Correct |
4 ms |
368 KB |
Output is correct |
| 50 |
Correct |
4 ms |
332 KB |
Output is correct |
| 51 |
Correct |
5 ms |
332 KB |
Output is correct |
| 52 |
Correct |
6 ms |
332 KB |
Output is correct |
| 53 |
Correct |
1459 ms |
7640 KB |
Output is correct |
| 54 |
Correct |
1390 ms |
7928 KB |
Output is correct |
| 55 |
Correct |
1319 ms |
7708 KB |
Output is correct |
| 56 |
Correct |
1257 ms |
7648 KB |
Output is correct |
| 57 |
Correct |
901 ms |
7812 KB |
Output is correct |
| 58 |
Correct |
1028 ms |
7824 KB |
Output is correct |
| 59 |
Correct |
1203 ms |
7600 KB |
Output is correct |
| 60 |
Correct |
1071 ms |
7660 KB |
Output is correct |
| 61 |
Correct |
1328 ms |
7732 KB |
Output is correct |
| 62 |
Correct |
1164 ms |
7816 KB |
Output is correct |
| 63 |
Correct |
1308 ms |
7692 KB |
Output is correct |
| 64 |
Correct |
1080 ms |
7648 KB |
Output is correct |
| 65 |
Correct |
1317 ms |
7480 KB |
Output is correct |
| 66 |
Correct |
943 ms |
7828 KB |
Output is correct |
| 67 |
Correct |
916 ms |
7576 KB |
Output is correct |
| 68 |
Correct |
1148 ms |
7404 KB |
Output is correct |
| 69 |
Correct |
1079 ms |
8056 KB |
Output is correct |
| 70 |
Correct |
1110 ms |
7448 KB |
Output is correct |
| 71 |
Correct |
779 ms |
7892 KB |
Output is correct |
| 72 |
Correct |
1275 ms |
7832 KB |
Output is correct |
| 73 |
Correct |
1512 ms |
7824 KB |
Output is correct |
