Submission #583934

#	Time	Username	Problem	Language	Result	Execution time	Memory
583934		cheissmart	Boarding Passes (BOI22_passes)	C++14	100 / 100	208 ms	13016 KiB

passes

#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;
const ll oo = 1e18;

vi G[15];
ll dp[1 << 15];

void cmin(ll& a, ll b) {
	a = min(a, b);
}

ll C2(int n) { return 1LL * n * (n - 1) / 2; }

signed main()
{
	IO_OP;

	string s; cin >> s;
	int n = SZ(s);
	for(int i = 0; i < n; i++)
		G[s[i] - 'A'].PB(i);

	vi groups;
	for(int i = 0; i < 15; i++)
		if(G[i].size())
			groups.PB(i);
	int g = SZ(groups);

	V<V<V<ll>>> aux(g, V<V<ll>>(g));
	for(int i = 0; i < g; i++) {
		for(int j = 0; j < g; j++) if(i != j) {
			vi& gi = G[groups[i]], gj = G[groups[j]];
			aux[i][j].resize(SZ(gj) + 1);

			vi lef(SZ(gj)), rig(SZ(gj));
			for(int k = 0, l = 0; k < SZ(gj); k++) {
				while(l < SZ(gi) && gi[l] < gj[k])
					l++;
				lef[k] = l;
			}
			for(int k = SZ(gj) - 1, l = SZ(gi) - 1; k >= 0; k--) {
				while(l >= 0 && gi[l] > gj[k])
					l--;
				rig[k] =  SZ(gi) - 1 - l;
			}

			for(int k = 1; k < SZ(lef); k++)
				lef[k] += lef[k - 1];
			for(int k = SZ(rig) - 2; k >= 0; k--)
				rig[k] += rig[k + 1];

			for(int k = 0; k < SZ(aux[i][j]); k++) {
				if(k) aux[i][j][k] += lef[k - 1];
				if(k < SZ(gj)) aux[i][j][k] += rig[k];
			}
		}
	}

	for(int i = 1; i < (1 << g); i++) {
		dp[i] = oo;
		for(int j = 0; j < g; j++) {
			if(i >> j & 1) {
				int k = i ^ (1 << j);
				int len = SZ(G[groups[j]]);

				auto go = [&] (int pos) {
					ll res = C2(pos) + C2(len - pos);
					for(int l = 0; l < g; l++) if(k >> l & 1)
						res += aux[l][j][pos] * 2;
					return res;
				};
				int lb = 0, rb = len - 1;
				while(lb <= rb) {
					int mb = (lb + rb) / 2;
					if(go(mb) > go(mb + 1)) lb = mb + 1;
					else rb = mb - 1;
				}
				cmin(dp[i], dp[k] + go(lb));
			}
		}
	}

	ll ans = dp[(1 << g) - 1];
	if(ans & 1) cout << ans / 2 << ".5\n";
	else cout << ans / 2 << '\n';

}

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