oj.uz

Submission #917356

# Submission time Handle Problem Language Result Execution time Memory
917356 2024-01-27T23:32:47 Z NK_ Boarding Passes (BOI22_passes) C++17
25 / 100
 2000 ms 6180 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;
template<class T> using V = vector<T>;
using vi = V<int>;
using vd = V<db>;

const db EPS = 1e-14;
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];
	};

	auto EXP = [&](int N) { return db(N) / db(2); };

	cout << fixed << setprecision(10);

	V<db> 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) {
			db all = dp[msk];

			for(auto& x : oc[g]) {
				db F = EXP(qry(g, 0, x - 1)), B = EXP(qry(g, x + 1, N - 1));

				for(int c = 0; c < G; c++) if ((msk >> c) & 1) {
					F += qry(c, 0, x), B += qry(c, x, N - 1);
				}
				// cout << x << " ======> " << F << " " << B << endl;

				all += min(F, B);
			}

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

			int nmsk = msk | (1 << g);
			if (dp[nmsk] > all + EPS) dp[nmsk] = all;
		}
	}

	cout << dp[(1 << G) - 1] << nl;

	exit(0-0);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 1052 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 5 ms 860 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 5 ms 988 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 7 ms 984 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 311 ms 1060 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2045 ms 6180 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 38 ms 980 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 42 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 41 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 38 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 12 ms 1224 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 42 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 19 ms 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 21 ms 964 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 20 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 20 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 22 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 21 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 20 ms 992 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 20 ms 1012 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 20 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 20 ms 860 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 38 ms 980 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 42 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 41 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 38 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 12 ms 1224 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 42 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 19 ms 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 21 ms 964 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 20 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 20 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 22 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 21 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 20 ms 992 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 20 ms 1012 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 20 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 20 ms 860 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 8 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 37 ms 860 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 42 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 46 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 39 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 11 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 41 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 19 ms 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 20 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 20 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 20 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 19 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 20 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 20 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 19 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 19 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 20 ms 1060 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Execution timed out 2086 ms 1884 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 1052 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 5 ms 860 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 5 ms 988 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 7 ms 984 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 311 ms 1060 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2045 ms 6180 KB Time limit exceeded
7 Halted 0 ms 0 KB -