Submission #1099556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099556		epicci23	Boarding Passes (BOI22_passes)	C++17	100 / 100	559 ms	332808 KiB

passes

#include "bits/stdc++.h"
#define int long long
#define double long double
#define all(v) v.begin() , v.end()
#define sz(a) (int) a.size()
using namespace std;

const int LOG = 15;
const double INF = 1e18;
const int N = 1e5 + 5;
int suf[LOG][LOG][N];
int pre[LOG][LOG][N];
int ar[N],n,G;
vector<double> dp((1LL<<LOG) + 5,INF);
vector<int> pos[LOG];

void calc(){
  for(int i=0;i<G;i++){
  	for(int j=0;j<G;j++){
     if(i==j) continue;
     int res=0,kac=0;
     for(int x=1;x<=n;x++){
       if(ar[x]==j) kac++;
       else if(ar[x]==i) res+=kac;
       pre[i][j][x]=res;
     }
  	}
  }

  for(int i=0;i<G;i++){
  	for(int j=0;j<G;j++){
     if(i==j) continue;
     int res=0,kac=0;
     for(int x=n;x>=1;x--){
       if(ar[x]==j) kac++;
       else if(ar[x]==i) res+=kac;
       suf[i][j][x]=res;
     }
  	}
  }
}

double Get_Cost(int ind,int u,int mask){
  int le = ind + 1, ri = sz(pos[u]) - ind - 1;
  double res = le*(le-1)/4.0L + ri*(ri-1)/4.0L;
  //cout << "ilk: " << res << '\n';
  for(int i=0;i<G;i++){
  	if(ind==-1) break;
  	if(!(mask>>i&1)) continue;
  	res += pre[u][i][pos[u][ind]];
  }
  //cout << "sec: " << res << '\n';
  for(int i=0;i<G;i++){
    if(ind+1>=sz(pos[u])) break;
  	if(!(mask>>i&1)) continue;
  	res += suf[u][i][pos[u][ind+1]];
  }
  //cout << "tri: " << res << '\n';
  return res;
}


void _(){
  string s;
  cin >> s;
  n=sz(s);

  vector<int> zip;
  for(int i=0;i<n;i++) zip.push_back(s[i]-'A');
  sort(all(zip));
  zip.erase(unique(all(zip)),zip.end());
  for(int i=1;i<=n;i++) ar[i]=lower_bound(all(zip),s[i-1]-'A')-zip.begin();
  dp[0] = 0;
  G = sz(zip);
  for(int i=1;i<=n;i++) pos[ar[i]].push_back(i);

  calc();
  
  //cout << Get_Cost(0,ar[2],(1<<ar[1])) << '\n';

  for(int mask=1;mask<(1LL<<G);mask++){
  	for(int u=0;u<G;u++){
  	  if(!(mask>>u&1)) continue;
  	  int l = -1, r = sz(pos[u]) - 1;
  	  while(r-l>4){
        int mid = (l + r) / 2;
        if( Get_Cost(mid,u,mask^(1<<u)) > Get_Cost(mid+1,u,mask^(1<<u)) )
           l=mid;
        else
           r=mid;
  	  } 

  	  // cout << mask << ' ' << u << ' ' << l+1 << '\n';
  	  for(int ll=l;ll<=r;ll++)
  	   dp[mask] = min(dp[mask], dp[mask^(1<<u)] + Get_Cost(ll,u,mask^(1<<u)) );
  	}
  }

  cout << dp[(1LL<<G)-1] << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  cout << fixed << setprecision(16);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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