Submission #578454

#	Time	Username	Problem	Language	Result	Execution time	Memory
578454		8e7	Boarding Passes (BOI22_passes)	C++17	100 / 100	186 ms	14588 KiB

passes

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...); }
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define maxc 15
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
ll dp[1<<maxc];
int pref[maxn], suf[maxn], col[maxn];
vector<int> pos[maxc];
ll cnt[maxc][maxc][maxn];
int main() {
	io
	ll n;
	string s;
	cin >> s;
	n = s.size();
	
	for (int i = 0;i < n;i++) {
		int c = s[i] - 'A';
		pos[c].push_back(i);	
		col[i] = c;
	}
	
	for (int i = 0;i < maxc;i++) {
		for (int j = 0;j < n;j++) {
			pref[j] = suf[j] = (col[j] == i) ? 1 : 0;
			pref[j] += j ? pref[j-1] : 0;
		}
		for (int j = n - 2;j >= 0;j--)suf[j] += suf[j+1];
		for (int p = 0;p < maxc;p++) {
			if (p == i) continue;
			ll cur = 0;
			for (int x:pos[p]) cur += suf[x];
			cnt[p][i][0] = cur;	
			int id = 1;
			for (int x:pos[p]) {
				cur += pref[x] - suf[x];
				cnt[p][i][id++] = cur;
			}
		}
	}
	
	for (int i = 0;i < (1<<maxc);i++) dp[i] = inf;
	
	
	dp[0] = 0;
	for (int i = 0;i < (1<<maxc);i++) {
		vector<int> t;
		for (int j = 0;j < maxc;j++) {
			if ((i >> j) & 1) t.push_back(j);
		}
		auto getval = [&] (int p, int k) {
			ll ret = 0;
			for (int x:t) {
				ret += cnt[p][x][k];	
			}
			return ret * 4 + (ll)k * (k - 1) + (ll)(pos[p].size() - k) * (pos[p].size() - k - 1);
		};
		for (int j = 0;j < maxc;j++) {
			if (!((i >> j) & 1)) {
				int low = 0, up = pos[j].size()+1;
				while (low < up - 2) {
					int m1 = (low * 2 + up) / 3, m2 = (low + up * 2) / 3;
					if (getval(j, m1) <= getval(j, m2)) up = m2;
					else low = m1;
				}
				ll best = min(getval(j, low), getval(j, (low + up) / 2));	
				int to = i + (1<<j);
				dp[to] = min(dp[to], dp[i] + best);
			}
		}
	}
	ll ans = dp[(1<<maxc) - 1];
	ll a0 = ans / 4;
	cout << a0;
	if (ans % 4 == 1) {
		cout << ".25\n";
	} else if (ans % 4 == 2) {
		cout << ".5\n";
	} else if (ans % 4 == 3) {
		cout << ".75\n";
	}
}

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