제출 #573950

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
573950		kshitij_sodani	Boarding Passes (BOI22_passes)	C++14	0 / 100	1 ms	340 KiB

passes

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'
 
 
llo dp[1<<16];
llo it[100001];
llo ans[100001];
llo vis[100001];
vector<llo> pre[20];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string s;
	cin>>s;
	llo m=0;
	llo n=s.size();
	for(llo i=0;i<n;i++){
		m=max(m,(llo)(s[i]-'A'+1));
		it[i]=s[i]-'A';
		pre[it[i]].pb(i);
	}
	for(llo i=0;i<(1<<m);i++){
		dp[i]=1e18;
	}
	dp[0]=0;

	for(llo i=0;i<(1<<m);i++){
		for(llo j=0;j<n;j++){
			if((1<<it[j])&i){
				vis[j+1]=2;
			}
			else{
				vis[j+1]=0;
			}
			vis[j+1]+=vis[j];
		}
		for(llo j=0;j<m;j++){
			if((1<<j)&i){
				continue;
			}
			llo le=pre[j].size();
			llo cur2=dp[i];
			llo su=0;
			for(auto jj:pre[j]){
				llo cur3=min(su+vis[jj],le-su-1+vis[n]-vis[jj]);
				cur2+=cur3;
				su++;
			}
			dp[i+(1<<j)]=min(dp[i+(1<<j)],cur2);
		}
	}
	llo aa=dp[(1<<m)-1];
//	cout<<aa<<endl;
	if(aa%2==0){
		cout<<(aa/2)<<endl;
	}
	else{
		long double xx=aa;
		xx/=(long double)2;
		cout<<setprecision(2)<<xx<<endl;
	}



 
 
 
	return 0;
}

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