oj.uz

Submission #917359

# Submission time Handle Problem Language Result Execution time Memory
917359 2024-01-28T00:49:52 Z NK_ Boarding Passes (BOI22_passes) C++17
100 / 100
 234 ms 31052 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

using str = string;
using db = long double;
using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
using vl = V<ll>;

const int G = 15;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	str S; cin >> S;
	int N = sz(S);
 
	V<vi> P(G, {0}); V<vi> oc(G);
	for(int i = 0; i < N; i++) {
		int c = S[i] - 'A'; oc[c].pb(i);
		for(int g = 0; g < G; g++) P[g].pb(P[g].back() + (g == c));
	}

	auto qry = [&](int g, int l, int r) {
		return P[g][r + 1] - P[g][l];
	};


	V<V<vl>> F(G, V<vl>(G)), B(G, V<vl>(G));
	for(int x = 0; x < G; x++) for(int y = 0; y < G; y++) {
		F[x][y].assign(sz(oc[y]), 0);
		B[x][y].assign(sz(oc[y]), 0);

		for(int i = 0; i < sz(oc[y]); i++) {
			if (i - 1 >= 0) F[x][y][i] = F[x][y][i - 1];
			F[x][y][i] += qry(x, 0, oc[y][i] - 1);
		}

		for(int i = sz(oc[y]) - 1; i >= 0; i--) {
			if (i + 1 < sz(oc[y])) B[x][y][i] = B[x][y][i + 1];
			B[x][y][i] += qry(x, oc[y][i] + 1, N - 1);
		}

		// cout << x << " " << y << endl;
		// for(int i = 0; i < sz(oc[y]); i++) cout << i << " => " << F[x][y][i] << " " << B[x][y][i] << endl;
	}

	vl dp(1 << G, 1e10);
	dp[0] = 0;

	for(int msk = 0; msk < (1 << G); msk++) {
		// cout << msk << " => " << dp[msk] << endl;
		for(int g = 0; g < G; g++) if (((msk >> g) & 1) ^ 1) {	

			ll cost = 1e10;
			auto comp = [&](int b) {
				b = min(sz(oc[g]), b);
				int f = b - 1; ll ans = 0;

				if (f > -1) ans += F[g][g][f];
				if (b < sz(oc[g])) ans += B[g][g][b];

				for(int i = 0; i < G; i++) if ((msk >> i) & 1) {
					if (f > -1) ans += 2 * F[i][g][f];
					if (b < sz(oc[g])) ans += 2 * B[i][g][b];
				}
				
				cost = min(ans, cost);

				return ans;
			};

			// cout << "G: " << g << " " << sz(oc[g]) << endl;
			int lo = 0, hi = sz(oc[g]); 
			while(lo < hi) {
				int mid = (lo + hi) / 2;
				if (comp(mid) < comp(mid + 1)) hi = mid - 1; 
				else lo = mid + 1;
			}

			comp(lo);

			// cout << g << " ===> " << cost << endl;

			int nmsk = msk | (1 << g);
			dp[nmsk] = min(cost + dp[msk], dp[nmsk]);
		}
	}

	cout << fixed << setprecision(10);
	cout << db(dp[(1 << G) - 1]) / db(2) << nl;

	exit(0-0);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 860 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 17 ms 600 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 20 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 20 ms 740 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 32 ms 1108 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 60 ms 24360 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 75 ms 28964 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 64 ms 30636 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 64 ms 30756 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 25 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 51 ms 600 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 47 ms 604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 37 ms 600 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 31 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 43 ms 600 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 37 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 38 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 39 ms 600 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 38 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 43 ms 732 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 40 ms 720 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 39 ms 600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 40 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 39 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 38 ms 600 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 25 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 51 ms 600 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 47 ms 604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 37 ms 600 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 31 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 43 ms 600 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 37 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 38 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 39 ms 600 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 38 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 43 ms 732 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 40 ms 720 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 39 ms 600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 40 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 39 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 38 ms 600 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 23 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 27 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 49 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 48 ms 600 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 37 ms 604 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 31 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 43 ms 604 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 37 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 38 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 39 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 41 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 42 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 44 ms 740 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 43 ms 720 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 40 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 39 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 37 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 33 ms 4184 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 32 ms 3932 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 118 ms 3944 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 127 ms 3676 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 51 ms 4044 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 107 ms 3932 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 121 ms 3896 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 115 ms 3676 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 113 ms 3676 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 114 ms 3912 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 121 ms 3888 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 115 ms 3676 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 860 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 17 ms 600 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 20 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 20 ms 740 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 32 ms 1108 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 60 ms 24360 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 75 ms 28964 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 64 ms 30636 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 64 ms 30756 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 23 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 25 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 51 ms 600 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 47 ms 604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 37 ms 600 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 31 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 43 ms 600 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 37 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 38 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 39 ms 600 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 38 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 43 ms 732 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 40 ms 720 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 39 ms 600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 40 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 39 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 38 ms 600 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 23 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 27 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 49 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 48 ms 600 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 37 ms 604 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 31 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 43 ms 604 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 37 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 38 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 39 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 41 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 42 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 44 ms 740 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 43 ms 720 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 40 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 39 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 37 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 33 ms 4184 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 32 ms 3932 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 118 ms 3944 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 127 ms 3676 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 51 ms 4044 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 107 ms 3932 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 121 ms 3896 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 115 ms 3676 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 113 ms 3676 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 114 ms 3912 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 121 ms 3888 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 115 ms 3676 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 32 ms 604 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 34 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 28 ms 860 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 17 ms 744 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 18 ms 748 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 21 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 27 ms 860 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 58 ms 24348 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 61 ms 28952 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 65 ms 30756 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 64 ms 30756 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 23 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 25 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 49 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 47 ms 604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 38 ms 604 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 32 ms 740 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 43 ms 604 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 37 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 38 ms 604 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 39 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 38 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 41 ms 740 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 40 ms 604 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 39 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 41 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 39 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 37 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 33 ms 3932 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 32 ms 3932 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 118 ms 3940 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 116 ms 3932 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 50 ms 4044 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 113 ms 3956 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 115 ms 3676 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 114 ms 3676 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 112 ms 3892 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 115 ms 3676 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 118 ms 3676 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 114 ms 3676 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 224 ms 31004 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 55 ms 604 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 228 ms 30904 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 84 ms 30748 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 39 ms 604 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 212 ms 30848 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 230 ms 30868 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 221 ms 30836 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 217 ms 30852 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 220 ms 30928 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 229 ms 30816 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 224 ms 30784 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 222 ms 30764 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 234 ms 31052 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'