Submission #603258

#	Time	Username	Problem	Language	Result	Execution time	Memory
603258		CSQ31	Boarding Passes (BOI22_passes)	C++17	100 / 100	190 ms	13860 KiB

passes

#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define pb push_back
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int ll;
typedef long double ld;
const int MAXN = 1e5+5;
int g[MAXN];
ll dp[MAXN],pref[MAXN],suff[MAXN];
ll cost[15][15][MAXN];
vector<int>p[15];
ll comp(vector<int>&v,int j,int k){
	int s1 = sz(p[j]);
	ll c = 0;
	for(int x:v)c+=cost[x][j][k];
	c+=k * 1LL *(k-1)/2;
	c+=(s1-k) * 1LL *(s1-k-1)/2;
	return c;
	
}
int main()
{
	string s;
	cin>>s;
	int n = sz(s);
	int m = 0;
	for(int i=0;i<n;i++){
		g[i] = s[i] - 'A';
		m = max(g[i],m);
		p[g[i]].pb(i);
	}
	m++;
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			if(i==j)continue; //j go after i
			int s0 = sz(p[i]);
			int s1 = sz(p[j]);
			//last "l" at here
			int ptr = -1;
			ll a = 0,b = 0;
			for(int k=0;k<s1;k++){
				while(ptr+1<s0 && p[i][ptr+1] < p[j][k]){
					ptr++;
					a+=2;
				}
				b+=a;
				cost[i][j][k+1] = b;
			}
			a = b = 0;
			ptr = s0;
			for(int k=s1-1;k>=0;k--){
				while(ptr-1>=0 && p[i][ptr-1] > p[j][k]){
					ptr--;
					a+=2;
				}
				b+=a;
				cost[i][j][k]+= b;
			}
		}
	}
	for(int mask=0;mask<(1<<m);mask++)dp[mask] = 1e18;
	dp[0] = 0;
	for(int mask=0;mask<(1<<m);mask++){
		vector<int>v;
		for(int j=0;j<m;j++){
			if(mask&(1<<j))v.pb(j);
		}
		for(int j=0;j<m;j++){
			if(mask&(1<<j))continue;
			int l = 0,r = sz(p[j]);
			while(r-l>3){
				int m1 = l+(r-l)/3;
				int m2 = r-(r-l)/3;
				ll a = comp(v,j,m1);
				ll b = comp(v,j,m2);
				if(a == b){
					l = m1;
					r = m2;
				}
				if(a > b)l = m1;
				if(b > a)r = m2;				
			}
			for(int k=l;k<=r;k++){
				dp[mask+(1<<j)] = min(dp[mask+(1<<j)] , dp[mask] + comp(v,j,k));
			}
		}
	}
	ld ans = dp[(1<<m)-1];
	ans/=2;
	cout<<fixed<<setprecision(5)<<ans<<'\n';
	
}

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