제출 #604014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604014		MohamedAhmed04	Boarding Passes (BOI22_passes)	C++14	30 / 100	2072 ms	4624 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 ;

long double calc(int x)
{
	long double sum = 0 ;
	for(int i = 0 ; i < x ; ++i)
		sum += 0.5 * i ;
	return sum ;
}

vector<int>occ[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) ;
	vector<char>v ;
	for(char c = 'A' ; c <= 'Z' ; ++c)
	{
		if(occ[c-'A'].size())
			v.push_back(c) ;
	}
	long double ans = 1e18 ;
	do
	{
		for(int i = 0 ; i < n ; ++i)
			mark[i] = pref[i] = suff[i] = 0 ;
		long double ex = 0 ;
		for(auto &c : v)
		{
			if(!occ[c-'A'].size())
				continue ;
			long double cnt = 0 , cnt2 = 0 ;
			int last = -1 ;
			for(int i = 0 ; i < n ; ++i)
			{
				cnt += mark[i] ;
				if(s[i] != c)
					continue ;
				pref[i] = cnt + 0.5 * cnt2 ;
				if(last != -1)
					pref[i] += pref[last] ;
				++cnt2 , last = i ;
			}
			cnt = 0 , cnt2 = 0 , last = -1 ;
			for(int i = n-1 ; i >= 0 ; --i)
			{
				cnt += mark[i] ;
				if(s[i] != c)
					continue ;
				suff[i] = cnt + 0.5 * cnt2 ;
				if(last != -1)
					suff[i] += suff[last] ;
				++cnt2 , last = i ;
				mark[i] = 1 ;
			}
			int sz = occ[c-'A'].size() ;
			long double Min = min(pref[occ[c-'A'][sz-1]] , suff[occ[c-'A'][0]]) ;
			for(int i = 0 ; i < sz-1 ; ++i)
				Min = min(Min , pref[occ[c-'A'][i]] + suff[occ[c-'A'][i+1]]) ;
			ex += Min ;
		}
		ans = min(ans , ex) ;
	}while(next_permutation(v.begin() , v.end())) ;
	return cout<<fixed<<setprecision(12)<<ans<<"\n" , 0 ;
}

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