Submission #685556

#TimeUsernameProblemLanguageResultExecution timeMemory
685556MtSakaBoarding Passes (BOI22_passes)C++17
25 / 100
3 ms2900 KiB
#include<bits/stdc++.h> using ll=long long; #define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;++i) #define rrep(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i) using namespace std; int main(){ string S;cin>>S; vector<int>s; for(auto&e:S)s.push_back(e-'A'); const int n=s.size(); const int g=*max_element(s.begin(),s.end())+1; vector idx(g,vector<int>()); rep(i,0,n)idx[s[i]].push_back(i); vector prefix(g,vector<ll>(n,0)); auto suffix=prefix; vector suml(g,vector<ll>(n,0)); auto sumr=suml; rep(i,0,n){ prefix[s[i]][i]++; suffix[s[i]][i]++; } rep(i,0,g){ rep(j,0,n-1)prefix[i][j+1]+=prefix[i][j]; rrep(j,0,n-1)suffix[i][j]+=suffix[i][j+1]; } vector<int>last(g,-1); rep(i,0,n){ rep(j,0,g)suml[j][i]=prefix[j][i]; if(last[s[i]]!=-1)rep(j,0,g)suml[j][i]+=suml[j][last[s[i]]]; last[s[i]]=i; } last=vector<int>(g,-1); rrep(i,0,n){ rep(j,0,g)sumr[j][i]=suffix[j][i]; if(last[s[i]]!=-1)rep(j,0,g)sumr[j][i]+=sumr[j][last[s[i]]]; last[s[i]]=i; } auto calc1=[&](ll bit,ll i)->int { int ok=-1,ng=idx[i].size(); while(ng-ok>1){ int mid=(ok+ng)>>1; int p=idx[i][mid]; ll l=0,r=0; rep(j,0,g){ if((bit>>j)&1)l+=prefix[j][p]*2,r+=suffix[j][p]*2; else if(i==j)l+=prefix[j][p],r+=suffix[j][p]; } if(l<=r)ok=mid; else ng=mid; } return ok; }; auto calc2=[&](ll bit,ll i,int m)->ll { ll ret=0; if(m!=-1){ int p=idx[i][m]; rep(j,0,g){ if((bit>>j)&1)ret+=suml[j][p]*2; } } if(m!=(int)idx[i].size()-1){ int p=idx[i][m+1]; rep(j,0,g){ if((bit>>j)&1)ret+=sumr[j][p]*2; } } ret+=(ll)m*(m+1)/2; ret+=(ll)(idx[i].size()-m-1)*(idx[i].size()-m-2)/2; return ret; }; vector dp(1<<g,LLONG_MAX>>2); dp[0]=0; rep(bit,0,1<<g){ rep(i,0,g){ if((bit>>i)&1)continue; if(idx[i].empty())dp[bit^(1<<i)]=min(dp[bit^(1<<i)],dp[bit]); else{ int m=calc1(bit,i); ll cost=calc2(bit,i,m); //cerr<<bit<<" "<<i<<" "<<m<<" "<<cost<<endl; dp[bit^(1<<i)]=min(dp[bit^(1<<i)],dp[bit]+cost); } } } //for(auto&i:dp)cerr<<i<<endl; cout<<dp.back()/2.0<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...