Submission #868028

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
868028	2023-10-30T08:53:36 Z	TAhmed33	Boarding Passes (BOI22_passes)	C++	60 / 100	2000 ms	21844 KB

passes

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
string s; int n;
vector <int> pos[26];
int val[100001][26];
int val2[100001][26];
ld dp[(1 << 15)];
vector <int> dd;
int cnt;
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 = pos[dd[i]].size();
		ld sum = 0;
		for (int j = 0; j < m; j++) {
			int ret1 = 0, ret2 = 0;
			for (int k = 0; k < cnt; k++) {
				if (mask & (1 << k)) {
					ret1 += val[pos[dd[i]][j]][dd[k]];
					ret2 += val2[pos[dd[i]][j]][dd[k]];
				}
			}
			sum += min(ret1 + j * 0.5, ret2 + (m - j - 1) * 0.5);
		}
		ret = min(ret, sum + 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);
	}
	int x = 0;
	for (int i = 1; i < 26; i++) if (!pos[i].empty()) x = i;
	for (int i = 0; i <= x; i++) if (!pos[i].empty()) dd.push_back(i);
	cnt = dd.size();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 26; j++) {
			if (pos[j].empty()) continue;
			if (s[i] - 'A' == j) continue;
			int l = 0, r = (int)pos[j].size() - 1, ans = 0;
			while (l <= r) {
				int m = (l + r) >> 1;
				if (pos[j][m] < i) {
					l = m + 1; ans = m + 1; 
				} else {
					r = m - 1;
				}
			}
			val[i][j] = ans; val2[i][j] = (int)pos[j].size() - ans;
		}
	}
	cout << fixed << setprecision(6) << ans(0) << '\n';
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2652 KB	found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2	Correct	0 ms	2652 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3	Correct	0 ms	2652 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4	Correct	1 ms	2652 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5	Correct	1 ms	2652 KB	found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6	Correct	5 ms	3288 KB	found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7	Correct	4 ms	3288 KB	found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8	Correct	5 ms	3288 KB	found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9	Correct	5 ms	3288 KB	found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4700 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2	Correct	1 ms	2652 KB	found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3	Correct	2 ms	4700 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4	Correct	1 ms	4700 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5	Correct	1 ms	4700 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6	Correct	1 ms	4700 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7	Correct	1 ms	4700 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8	Correct	1 ms	4700 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9	Correct	1 ms	4700 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10	Correct	1 ms	4700 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11	Correct	1 ms	4952 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12	Correct	1 ms	4700 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13	Correct	1 ms	4700 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14	Correct	1 ms	4700 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15	Correct	1 ms	4700 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16	Correct	1 ms	4700 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17	Correct	1 ms	4700 KB	found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4700 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2	Correct	1 ms	2652 KB	found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3	Correct	2 ms	4700 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4	Correct	1 ms	4700 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5	Correct	1 ms	4700 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6	Correct	1 ms	4700 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7	Correct	1 ms	4700 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8	Correct	1 ms	4700 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9	Correct	1 ms	4700 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10	Correct	1 ms	4700 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11	Correct	1 ms	4952 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12	Correct	1 ms	4700 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13	Correct	1 ms	4700 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14	Correct	1 ms	4700 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15	Correct	1 ms	4700 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16	Correct	1 ms	4700 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17	Correct	1 ms	4700 KB	found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18	Correct	1 ms	4696 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19	Correct	1 ms	2652 KB	found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20	Correct	1 ms	4700 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21	Correct	1 ms	4700 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22	Correct	1 ms	4696 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23	Correct	1 ms	4700 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24	Correct	1 ms	4700 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25	Correct	1 ms	4700 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26	Correct	1 ms	4700 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27	Correct	1 ms	4700 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28	Correct	1 ms	4700 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29	Correct	1 ms	4700 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30	Correct	1 ms	4696 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31	Correct	1 ms	4696 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32	Correct	1 ms	4700 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33	Correct	1 ms	4704 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34	Correct	1 ms	4700 KB	found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35	Correct	1 ms	2652 KB	found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36	Correct	2 ms	2652 KB	found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37	Correct	84 ms	4792 KB	found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38	Correct	54 ms	5016 KB	found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39	Correct	54 ms	4832 KB	found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40	Correct	62 ms	4704 KB	found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41	Correct	71 ms	4700 KB	found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42	Correct	70 ms	4800 KB	found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43	Correct	67 ms	4696 KB	found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44	Correct	64 ms	4700 KB	found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45	Correct	74 ms	4700 KB	found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46	Correct	73 ms	4804 KB	found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2652 KB	found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2	Correct	0 ms	2652 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3	Correct	0 ms	2652 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4	Correct	1 ms	2652 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5	Correct	1 ms	2652 KB	found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6	Correct	5 ms	3288 KB	found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7	Correct	4 ms	3288 KB	found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8	Correct	5 ms	3288 KB	found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9	Correct	5 ms	3288 KB	found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10	Correct	1 ms	4700 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11	Correct	1 ms	2652 KB	found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12	Correct	2 ms	4700 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13	Correct	1 ms	4700 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14	Correct	1 ms	4700 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15	Correct	1 ms	4700 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16	Correct	1 ms	4700 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17	Correct	1 ms	4700 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18	Correct	1 ms	4700 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19	Correct	1 ms	4700 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20	Correct	1 ms	4952 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21	Correct	1 ms	4700 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22	Correct	1 ms	4700 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23	Correct	1 ms	4700 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24	Correct	1 ms	4700 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25	Correct	1 ms	4700 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26	Correct	1 ms	4700 KB	found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27	Correct	1 ms	4696 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28	Correct	1 ms	2652 KB	found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29	Correct	1 ms	4700 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30	Correct	1 ms	4700 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31	Correct	1 ms	4696 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32	Correct	1 ms	4700 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33	Correct	1 ms	4700 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34	Correct	1 ms	4700 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35	Correct	1 ms	4700 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36	Correct	1 ms	4700 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37	Correct	1 ms	4700 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38	Correct	1 ms	4700 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39	Correct	1 ms	4696 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40	Correct	1 ms	4696 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41	Correct	1 ms	4700 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42	Correct	1 ms	4704 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43	Correct	1 ms	4700 KB	found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44	Correct	1 ms	2652 KB	found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45	Correct	2 ms	2652 KB	found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46	Correct	84 ms	4792 KB	found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47	Correct	54 ms	5016 KB	found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48	Correct	54 ms	4832 KB	found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49	Correct	62 ms	4704 KB	found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50	Correct	71 ms	4700 KB	found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51	Correct	70 ms	4800 KB	found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52	Correct	67 ms	4696 KB	found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53	Correct	64 ms	4700 KB	found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54	Correct	74 ms	4700 KB	found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55	Correct	73 ms	4804 KB	found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56	Correct	1 ms	4720 KB	found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57	Correct	18 ms	4728 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58	Correct	1 ms	2648 KB	found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59	Correct	1 ms	2676 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60	Correct	1 ms	2652 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61	Correct	1 ms	2652 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62	Correct	1 ms	2664 KB	found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63	Correct	4 ms	3544 KB	found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64	Correct	4 ms	3452 KB	found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65	Correct	5 ms	3544 KB	found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66	Correct	5 ms	3544 KB	found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67	Correct	1 ms	4700 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68	Correct	1 ms	2652 KB	found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69	Correct	1 ms	4700 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70	Correct	1 ms	4700 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71	Correct	1 ms	4700 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72	Correct	1 ms	4700 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73	Correct	1 ms	4700 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74	Correct	1 ms	4700 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75	Correct	1 ms	4700 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76	Correct	1 ms	4700 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77	Correct	1 ms	4700 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78	Correct	1 ms	4700 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79	Correct	1 ms	4700 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80	Correct	1 ms	4700 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81	Correct	1 ms	4700 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82	Correct	1 ms	4696 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83	Correct	1 ms	4700 KB	found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84	Correct	1 ms	2652 KB	found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85	Correct	1 ms	2652 KB	found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86	Correct	70 ms	4700 KB	found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87	Correct	54 ms	4700 KB	found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88	Correct	51 ms	4700 KB	found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89	Correct	65 ms	4776 KB	found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90	Correct	68 ms	4804 KB	found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91	Correct	69 ms	4700 KB	found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92	Correct	68 ms	4696 KB	found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93	Correct	64 ms	4700 KB	found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94	Correct	66 ms	4700 KB	found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95	Correct	87 ms	4696 KB	found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96	Execution timed out	2035 ms	21844 KB	Time limit exceeded
97	Halted	0 ms	0 KB	-

Submission #868028

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 25.0 / 25.0

Subtask #3 30.0 / 30.0

Subtask #4 0 / 40.0

Subtask #1
5.0 / 5.0

Subtask #2
25.0 / 25.0

Subtask #3
30.0 / 30.0

Subtask #4
0 / 40.0