Submission #604027

#	Time	Username	Problem	Language	Result	Execution time	Memory
604027		MohamedAhmed04	Boarding Passes (BOI22_passes)	C++14	60 / 100	1248 ms	4212 KiB

passes

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

int arr[MAX] , mark[MAX] ;
int n ;

long double pref[MAX] , suff[MAX] ;

string s ;

vector<int>occ[30] ;

long double dp[MAX] ;
int freq[30] , last[30] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>s ;
	n = s.size() ;
	for(int i = 0 ; i < n ; ++i)
		occ[s[i]-'A'].push_back(i) ;
	for(int mask = 1 ; mask < (1 << 10) ; ++mask)
	{
		dp[mask] = 1e18 ;
		for(int c = 0 ; c < 10 ; ++c)
			freq[c] = 0 , last[c] = -1 ;
		long double cnt = 0 ;
		for(int i = 0 ; i < n ; ++i)
		{
			int c = s[i] - 'A' ;
			if((!(mask & (1 << c))))
				continue ;
			pref[i] = (cnt - freq[c]) + 0.5 * freq[c] ;
			if(last[c] != -1)
				pref[i] += pref[last[c]] ;
			++cnt , freq[c]++ , last[c] = i ;
		}
		for(int c = 0 ; c < 10 ; ++c)
			freq[c] = 0 , last[c] = -1 ;
		cnt = 0 ;
		for(int i = n-1 ; i >= 0 ; --i)
		{
			int c = s[i] - 'A' ;
			if((!(mask & (1 << c))))
				continue ;
			suff[i] = (cnt - freq[c]) + 0.5 * freq[c] ;
			if(last[c] != -1)
				suff[i] += suff[last[c]] ;
			++cnt , freq[c]++ , last[c] = i ;
		}
		for(int c = 0 ; c < 10 ; ++c)
		{
			if((!(mask & (1 << c))))
				continue ;
			if(!occ[c].size())
			{
				dp[mask] = min(dp[mask] , dp[mask ^ (1 << c)]) ;
				continue ;
			}
			int sz = occ[c].size() ;
			long double Min = min(pref[occ[c][sz-1]] , suff[occ[c][0]]) ;
			for(int i = 0 ; i < sz-1 ; ++i)
				Min = min(Min , pref[occ[c][i]] + suff[occ[c][i+1]]) ;
			dp[mask] = min(dp[mask] , dp[mask ^ (1 << c)] + Min) ;
		}
	}
	return cout<<fixed<<setprecision(12)<<dp[(1 << 10)-1]<<"\n" , 0 ;
}

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