Submission #578274

#	Time	Username	Problem	Language	Result	Execution time	Memory
578274		IvanJ	Boarding Passes (BOI22_passes)	C++17	60 / 100	905 ms	12132 KiB

passes

#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;

int n, M;
string s;
double dp[(1 << 15)];
vector<int> C[maxn];
double E[maxn];

double rek(int mask) {
	if(__builtin_popcount(mask) == M)
		return 0;
	if(dp[mask] != -1) 
		return dp[mask];
	
	
	vector<double> pref(n, 0);
	for(int i = 0;i < n;i++) {
		pref[i] += ((1 << (s[i] - 'A')) & mask) ? 1 : 0;
		if(i) pref[i] += pref[i - 1];
	}
	
	double ret = 1e18;
	for(int i = 0;i < M;i++) {
		if((1 << i) & mask) continue;
		double sum = 0, R = rek(mask | (1 << i));
		int m = C[i].size();
		if(m == 0) {
			ret = min(ret, R);
			continue;
		}
		for(int j : C[i])
			sum += pref[j];
		ret = min(ret, sum + E[m] + R);
		//cout << mask << " " << i << " " << sum + E[m] << "\n";
		for(int j = m - 1;j >= 0;j--) {
			sum -= pref[C[i][j]];
			sum += pref[n - 1];
			if(C[i][j]) sum -= pref[C[i][j] - 1];
			ret = min(ret, sum + E[j] + E[m - j] + R);
			//cout << mask << " " << i << " " << sum + E[j] + E[m - j] << " " << R << "\n";
		}
	}
	
	//cout << mask << " " << ret << " dp\n";
	return dp[mask] = ret;
}

int main() {
	cin >> s;
	n = s.size();
	if(n <= 100) M = 15;
	else M = 10;
	for(int i = 2;i <= n;i++) 
		E[i] = (double)i * (i - 1) / 4;
	/*double sol = 1e18;
	for(int i = 0;i <= n;i++)
		sol = min(sol, E[i] + E[n - i]);
	if(round(sol) != floor(sol)) printf("%.1lf\n", sol);
	else printf("%.0lf\n", sol);
	return 0;*/
	for(int i = 0;i < n;i++)
		C[s[i] - 'A'].pb(i);
		
	for(int i = 0;i < (1 << M);i++) 
		dp[i] = -1.0;
	double ans = rek(0);
	if(round(ans) != floor(ans)) printf("%.1lf\n", ans);
	else printf("%.0lf\n", ans);
	return 0;
}

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