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>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#ifndef LOCAL
#define cerr if(0)cerr
#endif
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
int n;
void inc(int& x) {
x = (x+1)%(2*n);
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
string s; cin>>s;
ll best = 0;
int skipped = 0;
for(int i=1; i<2*n; ++i) {
if(s[i]==s[0]) {
skipped++;
continue;
}
if(abs(n/2-skipped)>5) continue;
ll ans = 0;
vector<bool> intersect(2*n, 1);
int cnt = 1;
vector<int> matched(2*n, -1);
matched[0] = matched[i] = 0;
int b = 1, w = i;
inc(w);
int iter = 1;
while(iter<n) {
while(s[b]!=s[0]) {
if(matched[b] != -1) {
intersect[matched[b]] = !intersect[matched[b]];
if(intersect[matched[b]]) {
cnt++;
}
else {
cnt--;
}
}
inc(b);
}
while(s[w]==s[0]) {
if(matched[w] != -1) {
intersect[w] = !intersect[w];
if(intersect[w]) {
cnt++;
}
else {
cnt--;
}
}
inc(w);
}
matched[b] = matched[w] = b;
ans += cnt;
cnt++;
iter++;
inc(b); inc(w);
}
cerr<<ans<<' '<<i<<'\n';
best = max(best, ans);
}
cout<<best;
}
# | 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... |