Submission #652277

#TimeUsernameProblemLanguageResultExecution timeMemory
652277inksamuraiBoarding Passes (BOI22_passes)C++17
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> #define int ll using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define rng(i,c,n) for(int i=c;i<n;i++) #define fi first #define se second #define pb push_back #define sz(a) (int)a.size() #define vec(...) vector<__VA_ARGS__> #define _3CZAtRo ios::sync_with_stdio(0),cin.tie(0) typedef long long ll; using pii=pair<int,int>; using vi=vector<int>; void print(){cout<<'\n';} template<class h,class...t> void print(const h&v,const t&...u){cout<<v<<' ',print(u...);} const int inf=1e10; void chmin(int&a,const int&b){ a=min(a,b); } signed main(){ _3CZAtRo; int n; vi a; { string s; cin>>s; n=sz(s); vi tmp; rep(i,n){ tmp.pb(s[i]-'A'); } sort(tmp.begin(),tmp.end()); tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end()); rep(i,n){ int v=lower_bound(tmp.begin(),tmp.end(),s[i]-'A')-tmp.begin(); a.pb(v); } } rep(i,n){ cout<<a[i]<<" "; } print(); const int si=sz(set<int>(a.begin(),a.end())); vec(vi) rbts(si); rep(i,n){ rbts[a[i]].pb(i); } vec(vec(vi)) pf(si,vec(vi)(si,vi(n))),sf; sf=pf; rep(s,si){ rep(t,si){ if(s==t) continue; int cnt=0; rep(i,n){ if(i){ pf[s][t][i]=pf[s][t][i-1]; } if(a[i]==t){ pf[s][t][i]+=cnt; }else if(a[i]==s){ cnt+=1; } } cnt=0; per(i,n){ if(i<n-1){ sf[s][t][i]=sf[s][t][i+1]; } if(a[i]==t){ sf[s][t][i]+=cnt; }else if(a[i]==s){ cnt+=1; } } } } auto af1=[&](int v,int msk,int pos)->int{ int res=0; rep(u,si){ if(msk>>u&1){ if(pos!=-1){ res+=pf[u][v][pos]; } if(pos+1<n){ res+=sf[u][v][pos+1]; } } } return res; }; auto af0=[&](int v,int msk){ int sj=sz(rbts[v]); int l=0,r=sj-1; while(r-l>3){ int ml=(2*l+r)/3; int mr=(l+2*r)/3; int fl=af1(v,msk,rbts[v][ml]); int fr=af1(v,msk,rbts[v][mr]); if(fl<fr)r=mr; else l=ml; } int res=2*af1(v,msk,-1)+sj*(sj-1)/2; rng(i,l,r+1){ res=min(res,2*af1(v,msk,rbts[v][i])+((i+1)*i)/2+(sj-i-1)*(sj-i-2)/2); } return res; }; vi dp(1<<si,inf); dp[0]=0; rep(msk,1<<si){ int now=dp[msk]; rep(v,si){ if(!(msk>>v&1)){ int nmsk=msk|(1<<v); int wit=af0(v,msk); // print(msk,v,wit); chmin(dp[nmsk],wit+now); } } } int ans=dp[(1<<si)-1]; cout<<ans/2<<(ans%2?".5":"")<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...