Submission #884337

#	Time	Username	Problem	Language	Result	Execution time	Memory
884337		TAhmed33	Boarding Passes (BOI22_passes)	C++98	100 / 100	226 ms	48584 KiB

passes

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
string s; int n;
vector <int> pos[26];
ll val[15][15][100001];
ll val2[15][15][100001];
ld dp[(1 << 15)];
int dd[26];
int cnt;
ld f (ll mid, int i, int mask) {
    ld sum = 0;
    for (int j = 0; j < cnt; j++) {
        if (mask & (1 << j)) {
            sum += val[i][j][mid];
            sum += val2[i][j][(int)pos[dd[i]].size() - mid];
        }
    }
    ll x = pos[dd[i]].size();
    sum += 1ll * mid * (mid - 1) * 1.0 / 4 + 1ll * (x - mid) * (x - mid - 1) * 1.0 / 4;
    return sum;
}
ld ans (int mask) {
	ld &ret = dp[mask];
	if (ret == ret) return ret;
	ret = 1e18;
	if (mask == (1 << cnt) - 1) return ret = 0;
	for (int i = 0; i < cnt; i++) {
		if (mask & (1 << i)) continue;
		int m = (int)pos[dd[i]].size();
        ll l = 0, r = m - 1, opt = m;
        while (l <= r) {
            ll mid = (l + r) / 2;
            if (f(mid, i, mask) < f(mid + 1, i, mask)) {
                r = mid - 1; opt = mid;
            } else {
                l = mid + 1;
            }
        }
		ret = min(ret, f(opt, i, mask) + ans(mask ^  (1 << i)));
	}
	return ret;
}
int main () {
	memset(dp, -1, sizeof(dp));
	cin >> s; n = s.length();
	for (int i = 0; i < n; i++) {
		pos[s[i] - 'A'].push_back(i);
	}
	for (int i = 0; i < 26; i++) if (!pos[i].empty()) dd[cnt++] = i;
    for (int i = 0; i < cnt; i++) {
        for (int j = 0; j < cnt; j++) {
            if (i == j) continue;
            int p = 0;
            for (int k = 0; k < (int)pos[dd[i]].size(); k++) {
                while (p < (int)pos[dd[j]].size() && pos[dd[i]][k] > pos[dd[j]][p]) p++;
                val[i][j][k + 1] = p + val[i][j][k];
            }
            p = (int)pos[dd[j]].size() - 1;
            for (int c = 0, k = (int)pos[dd[i]].size() - 1; k >= 0; k--, c++) {
                while (p >= 0 && pos[dd[i]][k] < pos[dd[j]][p]) p--;
                val2[i][j][c + 1] = (int)pos[dd[j]].size() - 1 - p + val2[i][j][c];
            }
        }
    }
	cout << fixed << setprecision(6) << ans(0) << '\n';
}

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