제출 #684728

#제출 시각아이디문제언어결과실행 시간메모리
684728alvingogoMonochrome Points (JOI20_monochrome)C++14
100 / 100
36 ms6100 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #define AquA cin.tie(0);ios_base::sync_with_stdio(0); #define fs first #define sc second #define p_q priority_queue #define int long long using namespace std; signed main(){ AquA; int n; cin >> n; string s; cin >> s; int ans=1e14; vector<int> a,b; for(int i=0;i<n;i++){ if(s[i]=='B'){ a.push_back(i); } if(s[i+n]=='W'){ b.push_back(i); } } int nn=n; n=a.size(); vector<int> mp(n,-1); auto f=[&](int i){ if(i>=n || i<0){ return 41232432433ll; } if(mp[i]>=0){ return mp[i]; } int xx=0; for(int j=0;j<n;j++){ xx+=min(abs(b[j]-a[(i+j)%n]),nn-abs(b[j]-a[(i+j)%n])); } ans=min(ans,xx); mp[i]=xx; return xx; }; if(0 && n<=2000){ if(n==0){ ans=0; } for(int i=0;i<n;i++){ f(i); } cout << nn*(nn-1)/2-ans << "\n"; return 0; } int z; if(n){ if(f(0)>f(n-1)){ z=n-1; int l=0,r=n-1; while(r>l){ int m=(l+r)/2; if(f(m)<=f(z)){ r=m; } else{ l=m+1; } } int bl=l,br=n-1; while(br>bl+1){ int m=(bl+br)/2; if(f(m)>f(m+1)){ bl=m; } else{ br=m-1; } } f(bl); f(br); } else{ z=0; int l=0,r=n-1; while(r>l){ int m=(l+r+1)/2; if(f(m)<=f(z)){ l=m; } else{ r=m-1; } } int bl=0,br=l; while(br>bl+1){ int m=(bl+br)/2; if(f(m)>f(m+1)){ bl=m; } else{ br=m-1; } } f(bl); f(br); } } else{ ans=0; } cout << nn*(nn-1)/2-ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...