oj.uz

Submission #668175

# Submission time Handle Problem Language Result Execution time Memory
668175 2022-12-03T07:39:16 Z Sohsoh84 Boarding Passes (BOI22_passes) C++17
100 / 100
 613 ms 359740 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXG = 15;
const ll MAXN = 1e5 + 10;
const ll INF = 4e18;

int ps[MAXG][MAXN], n;
ll tps[MAXG][MAXG][MAXN], tss[MAXG][MAXG][MAXN], dp[1 << MAXG]; // :)
vector<int> ind[MAXG];
string s;

inline ll check(int mask, int x, int ind) {
	ll ans = 0;
	for (int i = 0; i < MAXG; i++)
		if (mask & (1 << i))
			ans += tps[x][i][ind] + tss[x][i][ind + 1];
	
	return ans * 2 + tps[x][x][ind] + tss[x][x][ind + 1];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> s;
	n = s.size();
	s = "." + s;

	for (int i = 0; i < MAXG; i++) ind[i].push_back(0);
	for (int i = 1; i <= n; i++) ind[s[i] - 'A'].push_back(i);

	for (int i = 0; i < MAXG; i++)
		for (int j = 1; j <= n; j++)
			ps[i][j] = ps[i][j - 1] + (int(s[j] - 'A') == i);
	
	for (int i = 0; i < MAXG; i++) {
		for (int j = 0; j < MAXG; j++) {
			for (int k = 1; k <= n; k++) {
				tps[i][j][k] = tps[i][j][k - 1];
				if (int(s[k] - 'A') == i)
					tps[i][j][k] += ps[j][k - 1];
			}

			for (int k = n; k > 0; k--) {
				tss[i][j][k] = tss[i][j][k + 1];
				if (int(s[k] - 'A') == i)
					tss[i][j][k] += ps[j][n] - ps[j][k];
			}
		}
	}

	for (int mask = 1; mask < (1 << MAXG); mask++) {
		dp[mask] = INF;
		for (int i = 0; i < MAXG; i++) {
			if (mask & (1 << i)) {
				int tmask = (mask ^ (1 << i)), l = 0, r = ind[i].size() - 1;
				while (l < r) {
					int mid = (l + r) >> 1;
					if (check(tmask, i, ind[i][mid]) >= check(tmask, i, ind[i][mid + 1])) l = mid + 1;
					else r = mid;	
				}

				dp[mask] = min(dp[mask], dp[tmask] + check(tmask, i, ind[i][l]));	
			}
		}
	}

	int mask = (1 << MAXG) - 1;
	cout << dp[mask] / 2 << "." << (dp[mask] % 2) * 5 << endl;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6372 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 18 ms 3028 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 22 ms 3028 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 23 ms 3132 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 28 ms 6572 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 212 ms 284736 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 258 ms 339220 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 263 ms 359400 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 257 ms 359328 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3084 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 25 ms 3388 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 46 ms 3348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 46 ms 3404 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 33 ms 3456 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 32 ms 3156 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 44 ms 3336 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 38 ms 3228 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 39 ms 3228 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 41 ms 3156 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 37 ms 3184 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 42 ms 3276 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 40 ms 3228 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 38 ms 3148 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 37 ms 3148 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 37 ms 3116 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 38 ms 3212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3084 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 25 ms 3388 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 46 ms 3348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 46 ms 3404 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 33 ms 3456 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 32 ms 3156 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 44 ms 3336 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 38 ms 3228 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 39 ms 3228 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 41 ms 3156 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 37 ms 3184 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 42 ms 3276 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 40 ms 3228 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 38 ms 3148 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 37 ms 3148 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 37 ms 3116 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 38 ms 3212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 23 ms 3148 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 25 ms 3364 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 47 ms 3380 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 44 ms 3436 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 36 ms 3396 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 30 ms 3068 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 41 ms 3292 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 37 ms 3172 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 38 ms 3128 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 40 ms 3232 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 36 ms 3208 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 37 ms 3208 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 38 ms 3184 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 38 ms 3168 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 36 ms 3224 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 37 ms 3220 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 38 ms 3156 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 57 ms 38936 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 54 ms 38940 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 133 ms 38860 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 116 ms 38896 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 66 ms 38904 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 113 ms 38740 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 126 ms 38176 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 127 ms 38172 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 126 ms 38208 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 130 ms 38168 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 135 ms 38156 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 137 ms 38156 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6372 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 18 ms 3028 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 22 ms 3028 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 23 ms 3132 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 28 ms 6572 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 212 ms 284736 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 258 ms 339220 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 263 ms 359400 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 257 ms 359328 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 24 ms 3084 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 25 ms 3388 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 46 ms 3348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 46 ms 3404 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 33 ms 3456 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 32 ms 3156 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 44 ms 3336 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 38 ms 3228 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 39 ms 3228 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 41 ms 3156 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 37 ms 3184 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 42 ms 3276 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 40 ms 3228 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 38 ms 3148 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 37 ms 3148 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 37 ms 3116 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 38 ms 3212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 23 ms 3148 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 25 ms 3364 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 47 ms 3380 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 44 ms 3436 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 36 ms 3396 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 30 ms 3068 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 41 ms 3292 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 37 ms 3172 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 38 ms 3128 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 40 ms 3232 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 36 ms 3208 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 37 ms 3208 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 38 ms 3184 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 38 ms 3168 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 36 ms 3224 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 37 ms 3220 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 38 ms 3156 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 57 ms 38936 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 54 ms 38940 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 133 ms 38860 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 116 ms 38896 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 66 ms 38904 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 113 ms 38740 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 126 ms 38176 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 127 ms 38172 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 126 ms 38208 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 130 ms 38168 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 135 ms 38156 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 137 ms 38156 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 35 ms 3100 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 63 ms 3224 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 30 ms 6368 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 19 ms 3044 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 20 ms 3064 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 19 ms 3028 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 28 ms 6612 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 215 ms 284708 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 245 ms 339228 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 261 ms 359376 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 256 ms 359372 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 23 ms 3060 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 24 ms 3456 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 46 ms 3436 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 46 ms 3372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 33 ms 3404 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 29 ms 3100 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 42 ms 3348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 36 ms 3156 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 39 ms 3160 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 36 ms 3232 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 36 ms 3212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 37 ms 3184 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 38 ms 3156 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 40 ms 3172 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 36 ms 3124 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 46 ms 3160 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 37 ms 3144 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 51 ms 38884 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 52 ms 38880 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 135 ms 38960 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 128 ms 38796 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 67 ms 39120 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 114 ms 38752 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 131 ms 38200 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 139 ms 38172 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 144 ms 38236 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 133 ms 38224 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 127 ms 38228 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 131 ms 38228 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 601 ms 359520 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 58 ms 3184 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 438 ms 359348 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 281 ms 359488 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 44 ms 3196 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 490 ms 359500 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 541 ms 359740 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 530 ms 359536 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 579 ms 359544 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 539 ms 359548 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 521 ms 359456 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 613 ms 359552 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 525 ms 359348 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 529 ms 359528 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'