oj.uz

Submission #968538

# Submission time Handle Problem Language Result Execution time Memory
968538 2024-04-23T14:56:51 Z maxFedorchuk Boarding Passes (BOI22_passes) C++17
100 / 100
 402 ms 357180 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
 
int N, G;
double pref[15][15][100005], suf[15][15][100005], cost[15][1 << 15], dp[1 << 15];
vector<int> place[15];
string s;
 
 
double sum(int i, int mask, int mid)
{
	double res = 0, pre = 0, su = 0;
	for (int j = 0; j < G; j++)
		if (mask & (1 << j))
			res += pref[i][j][mid] + suf[i][j][mid + 1];
 
	res += pref[i][i][mid] + suf[i][i][mid + 1];
 
	return res;
}
 
signed main()
{
	cin >> s;
	N = s.size();
	s = " " + s + " ";
	for (int i = 1; i <= N; i++)
		G = max(G, s[i] - 'A' + 1);
	for (int i = 0; i < G; i++)
		place[i].emplace_back(0);
	for (int i = 1; i <= N; i++)
		place[s[i] - 'A'].emplace_back(i);
	for (int i = 0; i < G; i++)
	{
		int acc[15] = {};
		for (int j = 1; j <= N; j++)
		{
			if (s[j] - 'A' == i)
				for (int k = 0; k < G; k++)
					pref[i][k][j] += (i == k ? 0.5 * acc[k] : 1.0 * acc[k]);
			acc[s[j] - 'A']++;
			for (int k = 0; k < G; k++)
				pref[i][k][j] += pref[i][k][j - 1];
		}
	}
	for (int i = 0; i < G; i++)
	{
		int acc[15] = {};
		for (int j = N; j >= 1; j--)
		{
			if (s[j] - 'A' == i)
				for (int k = 0; k < G; k++)
					suf[i][k][j] += (i == k ? 0.5 * acc[k] : 1.0 * acc[k]);
			acc[s[j] - 'A']++;
			for (int k = 0; k < G; k++)
				suf[i][k][j] += suf[i][k][j + 1];
		}
	}
	for (int i = 0; i < G; i++)
		for (int mask = 0; mask < (1 << G); mask++)
			if ((mask & (1 << i)) == 0)
			{
				cost[i][mask] = 1e10;
				int L = 0, R = place[i].size() - 1;
				while (R > L)
				{
					int mid = (L + R) / 2;
					if (sum(i, mask, place[i][mid]) > sum(i, mask, place[i][mid + 1]))
						L = mid + 1;
					else
						R = mid;
				}
				cost[i][mask] = min(cost[i][mask], sum(i, mask, place[i][L]));
			}
 
	for (int mask = 0; mask < (1 << G); mask++)
	{
		dp[mask] = (mask == 0 ? 0.0 : 1e10);
		for (int i = 0; i < G; i++)
			if (mask & (1 << i))
				dp[mask] = min(dp[mask], dp[mask ^ (1 << i)] + cost[i][mask ^ (1 << i)]);
	}
	cout << fixed << setprecision(10) << dp[(1 << G) - 1] << '\n';
}

Compilation message

passes.cpp: In function 'double sum(int, int, int)':
passes.cpp:17:18: warning: unused variable 'pre' [-Wunused-variable]
   17 |  double res = 0, pre = 0, su = 0;
      |                  ^~~
passes.cpp:17:27: warning: unused variable 'su' [-Wunused-variable]
   17 |  double res = 0, pre = 0, su = 0;
      |                           ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 2 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 4236 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 4604 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 4728 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 4728 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 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 2908 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 2908 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 2908 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 2908 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 2908 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 2 ms 2908 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 2 ms 2908 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 2904 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 2908 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 2908 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 2908 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 2908 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 2908 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 2908 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 2908 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 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 2908 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 2908 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 2908 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 2908 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 2908 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 2 ms 2908 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 2 ms 2908 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 2904 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 2908 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 2908 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 2908 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 2908 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 2908 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 2908 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 2908 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 2648 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 2 ms 2908 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 2908 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 2908 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 2904 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 2908 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 2 ms 2908 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 2908 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 2908 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 2908 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 2908 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 2908 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 2904 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 2 ms 3000 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 3000 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 8 ms 13144 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 7 ms 13148 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 15 ms 19324 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 13 ms 19292 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 10 ms 19292 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 12 ms 19292 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 12 ms 18908 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 14 ms 19036 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 12 ms 19036 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 13 ms 19036 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 13 ms 19036 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 12 ms 19036 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 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 2 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 4236 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 4604 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 4728 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 4728 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 2908 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 2908 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 2908 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 2908 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 2 ms 2908 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 2 ms 2908 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 2 ms 2908 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 2904 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 2908 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 2908 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 2908 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 2908 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 2908 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 2 ms 2908 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 2908 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 2648 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 2 ms 2908 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 2908 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 2908 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 2904 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 2908 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 2 ms 2908 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 2908 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 2908 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 2908 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 2908 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 2908 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 2904 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 2 ms 3000 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 3000 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 8 ms 13144 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 7 ms 13148 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 15 ms 19324 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 13 ms 19292 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 10 ms 19292 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 12 ms 19292 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 12 ms 18908 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 14 ms 19036 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 12 ms 19036 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 13 ms 19036 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 13 ms 19036 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 12 ms 19036 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 43 ms 6484 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 78 ms 6384 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 2396 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 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 4 ms 4236 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 4 ms 4476 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 4 ms 4728 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 6 ms 4724 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 2908 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 2908 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 2904 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 3 ms 2904 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 2908 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 2908 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 2 ms 2904 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 2904 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 2908 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 2904 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 2908 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 2904 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 2908 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 2 ms 3164 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 6 ms 13148 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 6 ms 13148 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 12 ms 19272 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 13 ms 19288 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 11 ms 19292 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 13 ms 19292 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 12 ms 19032 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 12 ms 18912 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 12 ms 19280 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 12 ms 19036 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 13 ms 18868 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 12 ms 19068 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 402 ms 357180 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 35 ms 5460 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 347 ms 356832 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 225 ms 356976 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 52 ms 6480 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 357 ms 356852 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 382 ms 356812 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 360 ms 356920 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 351 ms 356852 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 388 ms 357028 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 357 ms 356852 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 353 ms 356968 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 229 ms 310772 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 397 ms 356852 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'