Submission #884337

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
884337	2023-12-07T07:27:03 Z	TAhmed33	Boarding Passes (BOI22_passes)	C++	100 / 100	226 ms	48584 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];
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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2820 KB	found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2	Correct	1 ms	2652 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3	Correct	1 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	2 ms	3540 KB	found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7	Correct	3 ms	3544 KB	found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8	Correct	3 ms	3544 KB	found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9	Correct	4 ms	3544 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	2652 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	3416 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4	Correct	2 ms	3164 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5	Correct	1 ms	3164 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6	Correct	1 ms	3416 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7	Correct	1 ms	3164 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8	Correct	1 ms	2908 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9	Correct	2 ms	3188 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10	Correct	1 ms	3184 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11	Correct	1 ms	3164 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12	Correct	2 ms	3164 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13	Correct	1 ms	3164 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14	Correct	1 ms	3184 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15	Correct	1 ms	3164 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16	Correct	1 ms	3164 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17	Correct	1 ms	3164 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	2652 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	3416 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4	Correct	2 ms	3164 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5	Correct	1 ms	3164 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6	Correct	1 ms	3416 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7	Correct	1 ms	3164 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8	Correct	1 ms	2908 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9	Correct	2 ms	3188 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10	Correct	1 ms	3184 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11	Correct	1 ms	3164 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12	Correct	2 ms	3164 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13	Correct	1 ms	3164 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14	Correct	1 ms	3184 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15	Correct	1 ms	3164 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16	Correct	1 ms	3164 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17	Correct	1 ms	3164 KB	found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18	Correct	1 ms	2652 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	3164 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21	Correct	1 ms	3164 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22	Correct	1 ms	3164 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23	Correct	1 ms	3164 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24	Correct	1 ms	3164 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25	Correct	1 ms	2908 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26	Correct	1 ms	3164 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27	Correct	1 ms	3192 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28	Correct	1 ms	3164 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29	Correct	1 ms	3164 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30	Correct	2 ms	3164 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31	Correct	2 ms	3420 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32	Correct	2 ms	3416 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33	Correct	1 ms	3164 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34	Correct	1 ms	3184 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	1 ms	2652 KB	found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37	Correct	6 ms	7228 KB	found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38	Correct	6 ms	7028 KB	found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39	Correct	6 ms	7036 KB	found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40	Correct	5 ms	7000 KB	found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41	Correct	6 ms	7000 KB	found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42	Correct	5 ms	7004 KB	found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43	Correct	5 ms	7004 KB	found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44	Correct	5 ms	7004 KB	found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45	Correct	5 ms	7000 KB	found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46	Correct	5 ms	7004 KB	found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2820 KB	found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2	Correct	1 ms	2652 KB	found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3	Correct	1 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	2 ms	3540 KB	found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7	Correct	3 ms	3544 KB	found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8	Correct	3 ms	3544 KB	found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9	Correct	4 ms	3544 KB	found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10	Correct	1 ms	2652 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	3416 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13	Correct	2 ms	3164 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14	Correct	1 ms	3164 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15	Correct	1 ms	3416 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16	Correct	1 ms	3164 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17	Correct	1 ms	2908 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18	Correct	2 ms	3188 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19	Correct	1 ms	3184 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20	Correct	1 ms	3164 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21	Correct	2 ms	3164 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22	Correct	1 ms	3164 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23	Correct	1 ms	3184 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24	Correct	1 ms	3164 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25	Correct	1 ms	3164 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26	Correct	1 ms	3164 KB	found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27	Correct	1 ms	2652 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	3164 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30	Correct	1 ms	3164 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31	Correct	1 ms	3164 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32	Correct	1 ms	3164 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33	Correct	1 ms	3164 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34	Correct	1 ms	2908 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35	Correct	1 ms	3164 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36	Correct	1 ms	3192 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37	Correct	1 ms	3164 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38	Correct	1 ms	3164 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39	Correct	2 ms	3164 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40	Correct	2 ms	3420 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41	Correct	2 ms	3416 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42	Correct	1 ms	3164 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43	Correct	1 ms	3184 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	1 ms	2652 KB	found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46	Correct	6 ms	7228 KB	found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47	Correct	6 ms	7028 KB	found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48	Correct	6 ms	7036 KB	found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49	Correct	5 ms	7000 KB	found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50	Correct	6 ms	7000 KB	found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51	Correct	5 ms	7004 KB	found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52	Correct	5 ms	7004 KB	found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53	Correct	5 ms	7004 KB	found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54	Correct	5 ms	7000 KB	found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55	Correct	5 ms	7004 KB	found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56	Correct	1 ms	2908 KB	found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57	Correct	41 ms	4972 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	2652 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	2652 KB	found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63	Correct	2 ms	3544 KB	found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64	Correct	3 ms	3544 KB	found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65	Correct	3 ms	3544 KB	found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66	Correct	4 ms	3544 KB	found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67	Correct	1 ms	2652 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	3164 KB	found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70	Correct	1 ms	3188 KB	found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71	Correct	1 ms	3164 KB	found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72	Correct	2 ms	3164 KB	found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73	Correct	1 ms	3164 KB	found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74	Correct	1 ms	2908 KB	found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75	Correct	1 ms	3164 KB	found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76	Correct	1 ms	3164 KB	found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77	Correct	1 ms	3164 KB	found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78	Correct	1 ms	3160 KB	found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79	Correct	2 ms	3164 KB	found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80	Correct	2 ms	3160 KB	found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81	Correct	1 ms	3160 KB	found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82	Correct	1 ms	3184 KB	found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83	Correct	1 ms	3164 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	7 ms	7004 KB	found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87	Correct	5 ms	7004 KB	found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88	Correct	5 ms	7044 KB	found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89	Correct	5 ms	7204 KB	found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90	Correct	5 ms	7004 KB	found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91	Correct	6 ms	7004 KB	found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92	Correct	5 ms	7004 KB	found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93	Correct	5 ms	7004 KB	found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94	Correct	5 ms	7100 KB	found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95	Correct	5 ms	7004 KB	found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96	Correct	226 ms	46648 KB	found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97	Correct	21 ms	4696 KB	found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98	Correct	223 ms	44880 KB	found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99	Correct	51 ms	31188 KB	found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100	Correct	31 ms	5000 KB	found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101	Correct	174 ms	44624 KB	found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102	Correct	191 ms	44820 KB	found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103	Correct	190 ms	44608 KB	found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104	Correct	185 ms	44372 KB	found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105	Correct	192 ms	42768 KB	found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106	Correct	192 ms	46680 KB	found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107	Correct	210 ms	48584 KB	found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108	Correct	97 ms	46428 KB	found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109	Correct	188 ms	42788 KB	found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'

Submission #884337

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 25.0 / 25.0

Subtask #3 30.0 / 30.0

Subtask #4 40.0 / 40.0

Subtask #1
5.0 / 5.0

Subtask #2
25.0 / 25.0

Subtask #3
30.0 / 30.0

Subtask #4
40.0 / 40.0