Submission #591456

#	Time	Username	Problem	Language	Result	Execution time	Memory
591456		tutis	Boarding Passes (BOI22_passes)	C++17	100 / 100	340 ms	23312 KiB

passes

/*input
ABABABAB
*/
#pragma GCC optimize ("O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[1 << 15];
int main()
{
	ios_base::sync_with_stdio(false);
	string s;
	cin >> s;
	for (int i = 0; i < (1 << 15); i++)
		dp[i] = 1e18;
	dp[0] = 0;
	vector<int>p[15];
	for (int i = 0; i < (int)s.size(); i++)
		p[s[i] - 'A'].push_back(i);
	int G = 15;
	while (p[G - 1].empty())
		G--;
	vector<ll>L1[15][15];
	vector<ll>R1[15][15];
	for (int w = 0; w < G; w++)
	{
		for (int v = 0; v < G; v++)
		{
			if (v == w)
				continue;
			L1[w][v] = vector<ll>(p[v].size() + 2, 0);
			R1[w][v] = vector<ll>(p[v].size() + 2, 0);
			vector<ll>&L = L1[w][v];
			vector<ll>&R = R1[w][v];
			auto it = p[v].begin();
			for (int j : p[w])
			{
				while (it != p[v].end() && (*it) <= j)
					it++;
				//auto it = lower_bound(p[v].begin(), p[v].end(), j);
				L[(it - p[v].begin()) + 1] += 4;
				R[(p[v].end() - it) + 1] += 4;
				//cout << ";" << (char)('A' + v) << " " << s[j] << " " << j << " " << (it - p[v].begin()) + 1 << " " << (p[v].end() - it) + 1 << endl;
			}
			for (ll i = 1; i <= (int)p[v].size(); i++)
				L[i] += L[i - 1];
			for (ll i = 1; i <= (int)p[v].size(); i++)
				L[i] += L[i - 1];
			for (ll i = 1; i <= (int)p[v].size(); i++)
				R[i] += R[i - 1];
			for (ll i = 1; i <= (int)p[v].size(); i++)
				R[i] += R[i - 1];
		}
	}
	int l = 0;
	for (int msk = 0; msk < (1 << G); msk++)
	{
		for (int v = 0; v < G; v++)
		{
			if ((msk & (1 << v)) == 0)
			{
				int msk1 = msk ^ (1 << v);
				auto f = [&](ll l)->ll
				{
					ll r = p[v].size() - l;
					ll sum = l * (l - 1) + r * (r - 1);
					for (int w = 0; w < G; w++)
						if ((msk & (1 << w)) != 0)
						{
							sum += L1[w][v][l];
							sum += R1[w][v][(int)p[v].size() - l];
						}
					return sum;
				};
				l = min(l, (int)p[v].size());
				for (int w = p[v].size(); w >= 1; w /= 2)
				{
					while (l - w >= 0 && f(l - w) < f(l))
						l -= w;
					while (l + w <= (int)p[v].size() && f(l + w) < f(l))
						l += w;
				}
				dp[msk1] = min(dp[msk1], dp[msk] + f(l));
			}
		}
	}
	ll ret = dp[(1 << G) - 1];
	cout << ret / 4;
	if (ret % 4 == 2)
	{
		cout << ".5";
	}
	else if (ret % 4 != 0)
	{
		cout << "." << 25 * (ret % 4);
	}
	cout << "\n";
}

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