Submission #796795

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
796795	2023-07-28T18:22:35 Z	ToniB	Boarding Passes (BOI22_passes)	C++17	60 / 100	2000 ms	16748 KB

passes

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN = 1e5 + 2;
const int G = 15;

int n, g, cmp[27], pre[MAXN][G], suf[MAXN][G];
bool bio[27];
string s;
ll dp[1 << 15];
vector<int> group[MAXN];

ll f(int x){
	return (ll)x * (x - 1);
}

int cnt_lower(int i, int mask){
	int ret = 0;
	for(int j = 0; j < g; ++j){
		if(mask & 1 << j) ret += pre[i][j];
	}
	return 4 * ret;
}
int cnt_higher(int i, int mask){
	int ret = 0;
	for(int j = 0; j < g; ++j){
		if(mask & 1 << j) ret += suf[i][j];
	}
	return 4 * ret;
}

int main(){
	cin >> s;
	n = s.length();
	for(char c : s) bio[c - 'A'] = 1;
	for(int i = 0; i < 26; ++i){
		if(bio[i]) cmp[i] = g++;
	}
	for(int i = 0; i < n; ++i) group[cmp[s[i] - 'A']].push_back(i);

	pre[0][cmp[s[0] - 'A']] = 1;
	suf[n - 1][cmp[s[n - 1] - 'A']] = 1;
	for(int i = 1; i < n; ++i){
		for(int j = 0; j < g; ++j) pre[i][j] = pre[i - 1][j];
		++pre[i][cmp[s[i] - 'A']];
	}
	for(int i = n - 2; i >= 0; --i){
		for(int j = 0; j < g; ++j) suf[i][j] = suf[i + 1][j];
		++suf[i][cmp[s[i] - 'A']];
	}
	
	dp[0] = 0;
	for(int i = 1; i < (1 << g); ++i){
		dp[i] = 1e18;
		for(int j = 0; j < g; ++j){
			if(i & 1 << j){
				ll cur = 1e18;
				int sz = group[j].size();
				assert(sz);

				vector<ll> lower (sz), higher (sz);
				lower[0] = cnt_lower(group[j][0], i ^ 1 << j);
				higher[sz - 1] = cnt_higher(group[j][sz - 1], i ^ 1 << j);
				for(int idx = 1; idx < sz; ++idx){
					lower[idx] = lower[idx - 1] + cnt_lower(group[j][idx], i ^ 1 << j);
				}
				for(int idx = sz - 2; idx >= 0; --idx){
					higher[idx] = higher[idx + 1] + cnt_higher(group[j][idx], i ^ 1 << j);
				}

				cur = min(higher[0], lower[sz - 1]) + f(sz);
				for(int idx = 0; idx < sz - 1; ++idx){
					cur = min(cur, lower[idx] + higher[idx + 1] + f(idx + 1) + f(sz - idx - 1));
				}
				cur += dp[i ^ 1 << j];
				dp[i] = min(dp[i], cur);
			}
		}
	}
	cout << fixed << setprecision(7) << (long double)dp[(1 << g) - 1] / 4LL;
	return 0;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2772 KB	found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2	Correct	1 ms	2660 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3	Correct	2 ms	2668 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4	Correct	1 ms	2644 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5	Correct	1 ms	2772 KB	found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6	Correct	9 ms	13776 KB	found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7	Correct	10 ms	15828 KB	found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8	Correct	10 ms	16716 KB	found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9	Correct	10 ms	16744 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	2644 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2	Correct	2 ms	2644 KB	found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3	Correct	2 ms	2644 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4	Correct	2 ms	2800 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5	Correct	2 ms	2644 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6	Correct	1 ms	2644 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7	Correct	2 ms	2644 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8	Correct	1 ms	2644 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9	Correct	2 ms	2644 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10	Correct	1 ms	2672 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11	Correct	2 ms	2668 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12	Correct	1 ms	2644 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13	Correct	2 ms	2668 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14	Correct	2 ms	2644 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15	Correct	2 ms	2672 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16	Correct	1 ms	2644 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17	Correct	2 ms	2668 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	2644 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2	Correct	2 ms	2644 KB	found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3	Correct	2 ms	2644 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4	Correct	2 ms	2800 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5	Correct	2 ms	2644 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6	Correct	1 ms	2644 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7	Correct	2 ms	2644 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8	Correct	1 ms	2644 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9	Correct	2 ms	2644 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10	Correct	1 ms	2672 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11	Correct	2 ms	2668 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12	Correct	1 ms	2644 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13	Correct	2 ms	2668 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14	Correct	2 ms	2644 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15	Correct	2 ms	2672 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16	Correct	1 ms	2644 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17	Correct	2 ms	2668 KB	found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18	Correct	2 ms	2808 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19	Correct	2 ms	2644 KB	found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20	Correct	1 ms	2644 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21	Correct	2 ms	2644 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22	Correct	2 ms	2672 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23	Correct	1 ms	2644 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24	Correct	2 ms	2644 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25	Correct	2 ms	2644 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26	Correct	2 ms	2664 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27	Correct	2 ms	2644 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28	Correct	1 ms	2644 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29	Correct	2 ms	2772 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30	Correct	2 ms	2644 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31	Correct	2 ms	2668 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32	Correct	2 ms	2644 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33	Correct	1 ms	2664 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34	Correct	1 ms	2672 KB	found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35	Correct	2 ms	4052 KB	found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36	Correct	2 ms	4052 KB	found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37	Correct	117 ms	3956 KB	found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38	Correct	115 ms	3920 KB	found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39	Correct	121 ms	4260 KB	found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40	Correct	114 ms	3924 KB	found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41	Correct	127 ms	3824 KB	found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42	Correct	118 ms	3936 KB	found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43	Correct	115 ms	3932 KB	found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44	Correct	121 ms	3924 KB	found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45	Correct	115 ms	3924 KB	found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46	Correct	113 ms	3928 KB	found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2772 KB	found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2	Correct	1 ms	2660 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3	Correct	2 ms	2668 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4	Correct	1 ms	2644 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5	Correct	1 ms	2772 KB	found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6	Correct	9 ms	13776 KB	found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7	Correct	10 ms	15828 KB	found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8	Correct	10 ms	16716 KB	found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9	Correct	10 ms	16744 KB	found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10	Correct	1 ms	2644 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11	Correct	2 ms	2644 KB	found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12	Correct	2 ms	2644 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13	Correct	2 ms	2800 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14	Correct	2 ms	2644 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15	Correct	1 ms	2644 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16	Correct	2 ms	2644 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17	Correct	1 ms	2644 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18	Correct	2 ms	2644 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19	Correct	1 ms	2672 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20	Correct	2 ms	2668 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21	Correct	1 ms	2644 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22	Correct	2 ms	2668 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23	Correct	2 ms	2644 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24	Correct	2 ms	2672 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25	Correct	1 ms	2644 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26	Correct	2 ms	2668 KB	found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27	Correct	2 ms	2808 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28	Correct	2 ms	2644 KB	found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29	Correct	1 ms	2644 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30	Correct	2 ms	2644 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31	Correct	2 ms	2672 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32	Correct	1 ms	2644 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33	Correct	2 ms	2644 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34	Correct	2 ms	2644 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35	Correct	2 ms	2664 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36	Correct	2 ms	2644 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37	Correct	1 ms	2644 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38	Correct	2 ms	2772 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39	Correct	2 ms	2644 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40	Correct	2 ms	2668 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41	Correct	2 ms	2644 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42	Correct	1 ms	2664 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43	Correct	1 ms	2672 KB	found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44	Correct	2 ms	4052 KB	found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45	Correct	2 ms	4052 KB	found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46	Correct	117 ms	3956 KB	found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47	Correct	115 ms	3920 KB	found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48	Correct	121 ms	4260 KB	found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49	Correct	114 ms	3924 KB	found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50	Correct	127 ms	3824 KB	found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51	Correct	118 ms	3936 KB	found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52	Correct	115 ms	3932 KB	found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53	Correct	121 ms	3924 KB	found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54	Correct	115 ms	3924 KB	found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55	Correct	113 ms	3928 KB	found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56	Correct	2 ms	2776 KB	found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57	Correct	59 ms	2844 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58	Correct	2 ms	2772 KB	found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59	Correct	1 ms	2644 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60	Correct	1 ms	2644 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61	Correct	1 ms	2672 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62	Correct	1 ms	2772 KB	found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63	Correct	10 ms	13772 KB	found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64	Correct	10 ms	15828 KB	found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65	Correct	10 ms	16716 KB	found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66	Correct	12 ms	16748 KB	found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67	Correct	1 ms	2644 KB	found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68	Correct	1 ms	2644 KB	found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69	Correct	2 ms	2644 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70	Correct	2 ms	2644 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71	Correct	1 ms	2668 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72	Correct	1 ms	2644 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73	Correct	2 ms	2644 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74	Correct	1 ms	2668 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75	Correct	1 ms	2644 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76	Correct	2 ms	2644 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77	Correct	1 ms	2668 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78	Correct	1 ms	2644 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79	Correct	1 ms	2644 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80	Correct	1 ms	2664 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81	Correct	2 ms	2644 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82	Correct	2 ms	2672 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83	Correct	2 ms	2644 KB	found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84	Correct	3 ms	4052 KB	found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85	Correct	2 ms	4052 KB	found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86	Correct	115 ms	3924 KB	found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87	Correct	112 ms	3916 KB	found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88	Correct	114 ms	4128 KB	found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89	Correct	117 ms	4168 KB	found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90	Correct	115 ms	3924 KB	found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91	Correct	120 ms	3928 KB	found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92	Correct	115 ms	3932 KB	found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93	Correct	119 ms	3924 KB	found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94	Correct	117 ms	3924 KB	found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95	Correct	115 ms	3924 KB	found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96	Execution timed out	2083 ms	15188 KB	Time limit exceeded
97	Halted	0 ms	0 KB	-

Submission #796795

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