제출 #601793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
601793		CSQ31	Boarding Passes (BOI22_passes)	C++17	60 / 100	2076 ms	2772 KiB

passes

//consider scc graph
//u -> v
//if u bad then v must be bad
//so every ingoing edge into v must be good and sum of sub(tree?graph?) must be >= minimal parent
//i dont even need scc,only scc is if all values are equal okay yes
#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;
//l l = 0.5
//r r = 0.5
//l r = 0
//r l = 1
//always do prefix l and suffix r
const int MAXN = 1e5+5;
int g[MAXN];
ll dp[MAXN],pref[MAXN],suff[MAXN];
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);
	}
	m++;
	for(int mask=0;mask<(1<<m);mask++)dp[mask] = 1e18;
	dp[0] = 0;
	for(int mask=0;mask<(1<<m);mask++){
		for(int j=0;j<m;j++){
			if(mask&(1<<j))continue;
			ll a = 0,b = 0;
			ll cost = 0;
			for(int k=0;k<n;k++){
				if(g[k] == j){
					a++;
					cost+=2*b;
				}
				else if(mask&(1<<g[k]))b++;
				pref[k] = cost + a*(a-1)/2;
			}
			a = 0;
			b = 0;
			cost = 0;
			for(int k=n-1;k>=0;k--){
				if(g[k] == j){
					a++;
					cost+=2*b;
				}
				else if(mask&(1<<g[k]))b++;
				suff[k] = cost + a*(a-1)/2;
			}
			int nmask = mask+(1<<j);
			dp[nmask] = min(dp[nmask],min(pref[n-1],suff[0]) + dp[mask]);
			for(int i=0;i+1<n;i++)dp[nmask] = min(dp[nmask],pref[i]+suff[i+1] + dp[mask]);
		}
	}
	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: 0 / 40