Submission #740305

#TimeUsernameProblemLanguageResultExecution timeMemory
740305stevancvBoarding Passes (BOI22_passes)C++14
Compilation error
0 ms0 KiB
/*#include <bits/stdc++.h> #define ll long long #define ld long double #define sp ' ' #define en '\n' #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) using namespace std; const int N = 1e5 + 2; const int M = 15; const int K = 1 << M; const ll linf = 1e18; vector<ll> pref[M][M], suff[M][M]; vector<int> pos[M]; ll dp[K]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); string s; cin >> s; int n = s.size(); for (int i = 0; i < n; i++) pos[s[i] - 'A'].push_back(i); for (int i = 0; i < M; i++) { for (int j = 0; j < M; j++) { if (i == j) continue; pref[i][j].resize(pos[i].size()); int jj = 0; for (int ii = 0; ii < pos[i].size(); ii++) { while (jj < pos[j].size() && pos[j][jj] < pos[i][ii]) jj += 1; pref[i][j][ii] = 2 * jj; if (ii > 0) pref[i][j][ii] += pref[i][j][ii - 1]; } } } for (int i = 0; i < M; i++) { for (int j = 0; j < M; j++) { if (i == j) continue; suff[i][j].resize(pos[i].size()); int jj = pos[j].size() - 1; for (int ii = pos[i].size() - 1; ii >= 0; ii--) { while (jj >= 0 && pos[j][jj] > pos[i][ii]) jj += 1; suff[i][j][ii] = 2 * (pos[j].size() - jj - 1); if (ii < pos[i].size() - 1) suff[i][j][ii] += suff[i][j][ii + 1]; } } } for (int mask = 1; mask < K; mask++) { dp[mask] = linf; for (int i = 0; i < M; i++) { if (!((1 << i) & mask)) continue; int uk = pos[i].size(); auto F = [&] (ll kol) { ll ans = kol * (kol - 1) / 2; ans += (uk - kol) * (uk - kol - 1) / 2; for (int j = 0; j < M; j++) { if (i != j && ((1 << j) & mask)) { if (kol > 0) ans += pref[i][j][kol - 1]; if (kol < uk) ans += suff[i][j][uk - kol - 1]; } } return ans; }; int l = 0, r = uk - 1, ans = uk; while (l <= r) { int mid = l + r >> 1; if (F(mid) < F(mid + 1)) { ans = mid; r = mid - 1; } else l = mid + 1; } smin(dp[mask], dp[mask ^ (1 << i)] + F(ans)); } } cout << dp[K - 1] / 2; if (dp[K - 1] % 2 == 1) cout << ".5" << en; return 0; } */

Compilation message (stderr)

/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/crt1.o: in function `_start':
(.text+0x24): undefined reference to `main'
collect2: error: ld returned 1 exit status