oj.uz

Submission #672517

# Submission time Handle Problem Language Result Execution time Memory
672517 2022-12-16T12:39:29 Z LittleCube Boarding Passes (BOI22_passes) C++14
100 / 100
 419 ms 356972 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 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 5 ms 2044 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 2292 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 6 ms 2416 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 6 ms 2416 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 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 932 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 944 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 852 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 948 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 948 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 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 932 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 944 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 852 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 948 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 948 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 436 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 432 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 952 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 852 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 948 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 944 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 948 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 8 ms 11220 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 9 ms 11216 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 14 ms 17228 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 14 ms 17188 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 12 ms 17236 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 13 ms 17208 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 14 ms 16980 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 14 ms 16960 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 13 ms 16900 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 16 ms 16980 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 15 ms 16960 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 14 ms 16984 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 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 5 ms 2044 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 2292 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 6 ms 2416 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 6 ms 2416 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 932 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 944 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 852 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 948 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 948 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 436 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 432 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 952 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 852 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 948 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 944 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 948 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 8 ms 11220 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 9 ms 11216 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 14 ms 17228 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 14 ms 17188 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 12 ms 17236 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 13 ms 17208 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 14 ms 16980 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 14 ms 16960 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 13 ms 16900 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 16 ms 16980 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 15 ms 16960 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 14 ms 16984 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 33 ms 6368 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 66 ms 6384 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 304 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 6 ms 2168 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 6 ms 2400 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 6 ms 2544 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 6 ms 2544 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 440 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 436 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 944 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 852 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 944 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 7 ms 11220 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 8 ms 11220 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 14 ms 17236 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 15 ms 17236 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 15 ms 17236 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 14 ms 17236 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 14 ms 16912 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 14 ms 16956 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 14 ms 16992 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 14 ms 16956 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 15 ms 16956 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 14 ms 16980 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 399 ms 356972 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 30 ms 4376 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 407 ms 356780 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 260 ms 356756 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 44 ms 6368 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 397 ms 356840 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 409 ms 356972 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 398 ms 356856 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 419 ms 356960 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 402 ms 356848 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 397 ms 356824 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 400 ms 356904 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 270 ms 309760 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 400 ms 356848 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'