Submission #685572

#	Time	Username	Problem	Language	Result	Execution time	Memory
685572		MtSaka	Boarding Passes (BOI22_passes)	C++17	100 / 100	193 ms	48796 KiB

passes

#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(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  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]-1,r+=suffix[j][p]-1;
      }
      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<<(dp.back()&1?".5":"")<<endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40