Submission #294171

#TimeUsernameProblemLanguageResultExecution timeMemory
294171pit4hMonochrome Points (JOI20_monochrome)C++14
4 / 100
1 ms384 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...